|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
On the complexity of two-dimensional discrete logarithm problem in a finite cyclic group with efficient automorphism
[О сложности двупараметрической задачи дискретного логарифмирования в конечной циклической группе с эффективным автоморфизмом]
M. V. Nikolaev Lomonosov Moscow State University, Moscow
Аннотация:
Двупараметрическая задача дискретного логарифмирования в конечной аддитивной группе $G$ заключается в решении уравнения $Q=n_1P_1+n_2P_2$ относительно $n_1$, $n_2$ для заданных $P_1,P_2,Q\in G$, $0<N_1,N_2<\sqrt{|G|}$ в случае, когда существует такое решение $(n_1,n_2)$, что $|n_1|\le N_1$, $|n_2|\le N_2$. В 2004 г. Gaudry и Schost предложили алгоритм решения этой задачи со сложностью порядка $(c+o(1))\sqrt N$ операций в группе $G$, где $c\approx2.43$, $N=4N_1N_2$, $N\to\infty$. В 2009 г. Galbraith и Ruprai улучшили этот алгоритм, получив $c\approx2.36$. Мы показываем, что если в группе $G$ существует автоморфизм, вычисляемый быстрее групповой операции, то можно улучшить эти алгоритмы и уменьшить оценку $c$.
Ключевые слова:
двупараметрическая задача дискретного логарифмирования, алгоритм Годри–Шоста, эллиптическая кривая, эффективный автоморфизм.
Получено 16.IX.2014
Образец цитирования:
M. V. Nikolaev, “On the complexity of two-dimensional discrete logarithm problem in a finite cyclic group with efficient automorphism”, Матем. вопр. криптогр., 6:2 (2015), 45–57
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mvk144https://doi.org/10.4213/mvk144 https://www.mathnet.ru/rus/mvk/v6/i2/p45
|
Статистика просмотров: |
Страница аннотации: | 460 | PDF полного текста: | 228 | Список литературы: | 60 | Первая страница: | 6 |
|