ГлавнаяАрхивРеализация алгоритмов подсчета точек в якобианах гиперэллиптических кривых рода 2, основанных на парадоксе дней рождения

Реализация алгоритмов подсчета точек в якобианах гиперэллиптических кривых рода 2, основанных на парадоксе дней рождения | Прикладная дискретная математика. 2022. № 55. DOI: 10.17223/20710410/55/9

Представлена эффективная программная реализация алгоритма Годри - Шоста и его модификации Гэлбрайта - Рупрая для подсчёта точек в якобианах гиперэллиптических кривых. Эти алгоритмы представляют собой версии алгоритма Мацуо - Чао - Цуджия с малым использованием памяти и реализуют стратегию Гельфонда - Шенкса больших и малых шагов. Выводится оптимальный размер памяти, позволяющий минимизировать время работы указанных алгоритмов и получить на практике ожидаемое время их работы, близкое к теоретическим оценкам 2,45√N и 2,38√N для алгоритмов Годри - Шоста и Гэлбрайта - Рупрая соответственно. Здесь N - размер двумерной области поиска, равный порядку якобиана кривой, уменьшенному в m раз с помощью других методов. Предлагаемая реализация алгоритмов имеет многопоточный режим работы. Представлена статистическая зависимость времени работы от размера входных данных. Данная реализация алгоритма Гэлбрайта - Рупрая для размерности 2 является первой опубликованной многопоточной реализацией этого алгоритма с открытым исходным кодом.
  • Title Реализация алгоритмов подсчета точек в якобианах гиперэллиптических кривых рода 2, основанных на парадоксе дней рождения
  • Headline Реализация алгоритмов подсчета точек в якобианах гиперэллиптических кривых рода 2, основанных на парадоксе дней рождения
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 55
  • Date:
  • DOI 10.17223/20710410/55/9
Ключевые слова
гиперэллиптическая кривая, якобиан, подсчёт точек, парадокс дней рождения
Авторы
Ссылки
Matsuo K., Chao J., and Tsujii S. An improved baby step giant step algorithm for point counting of hyperelliptic curves over finite fields. LNCS, 2002, vol. 2369, pp. 461-474.
Gaudry P. and Schost E. A low-memory parallel version of Matsuo, Chao and Tsujii’s algorithm. LNCS, 2004, vol. 3076, pp. 208-222.
Galbraith S. and Ruprai R. An improvement to the Gaudry - Schost algorithm for multidimensional discrete logarithm problems. LNCS, 2009, vol. 5921, pp. 368-382.
Cohen H., Frey G., Avanzi R., et al. Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, 2005.
Gaudry P. and Schost E. Genus 2 point counting over prime fields. J. Symbolic Comput., 2012, vol. 47, iss. 4, pp. 368-400.
Ruprai R. S. Improvements to the Gaudry - Schost Algorithm for Multidimensional Discrete Logarithm Problems and Applications. PhD Thesis, Department of Mathematics, Royal Holloway University of London, 2010. https://www.math.auckland.ac.nz/~sgal018/Ruprai-thesis.pdf.
Nishimura K. and Sibuya M. Probability to meet in the middle. J. Cryptology, 1990, no. 2, pp.13-22.
Hisil H. and Costello C. Jacobian coordinates on genus 2 curves. J. Cryptology, 2017, vol. 30, iss.2, pp. 572-600. https://doi.org/10.1007/s00145-016-9227-7.
Van Oorschot P. C. and Wiener M. J. Parallel collision search with cryptanalytic applications. J. Cryptology, 2013, vol. 12, pp. 1-28.
Gaudry P. C++ NTLJac2 Library, 2003, http://www.lix.polytechnique.fr/Labo/Pierrick.Gaudry/NTLJac2.
Реализация алгоритмов подсчета точек в якобианах гиперэллиптических кривых рода 2, основанных на парадоксе дней рождения | Прикладная дискретная математика. 2022. № 55. DOI: 10.17223/20710410/55/9
Реализация алгоритмов подсчета точек в якобианах гиперэллиптических кривых рода 2, основанных на парадоксе дней рождения | Прикладная дискретная математика. 2022. № 55. DOI: 10.17223/20710410/55/9