Математические вопросы криптографии
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. вопр. криптогр.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Математические вопросы криптографии, 2015, том 6, выпуск 2, страницы 45–57
DOI: https://doi.org/10.4213/mvk144
(Mi mvk144)
 

Эта публикация цитируется в 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
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.712.4+519.719.2
Язык публикации: английский
Образец цитирования: 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
Цитирование в формате AMSBIB
\RBibitem{Nik15}
\by M.~V.~Nikolaev
\paper On the complexity of two-dimensional discrete logarithm problem in a~finite cyclic group with efficient automorphism
\jour Матем. вопр. криптогр.
\yr 2015
\vol 6
\issue 2
\pages 45--57
\mathnet{http://mi.mathnet.ru/mvk144}
\crossref{https://doi.org/10.4213/mvk144}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3534199}
\elib{https://elibrary.ru/item.asp?id=23823086}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/mvk144
  • https://doi.org/10.4213/mvk144
  • https://www.mathnet.ru/rus/mvk/v6/i2/p45
  • Эта публикация цитируется в следующих 2 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математические вопросы криптографии
    Статистика просмотров:
    Страница аннотации:460
    PDF полного текста:228
    Список литературы:60
    Первая страница:6
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024