|
Вычислительные методы в дискретной математике
Implementation of point-counting algorithms on genus $2$ hyperelliptic curves based on the birthday paradox
[Реализация алгоритмов подсчёта точек в якобианах гиперэллиптических кривых рода $2$, основанных на парадоксе дней рождения]
N. S. Kolesnikov Immanuel Kant Baltic Federal University, Kaliningrad, Russia
Аннотация:
Представлена эффективная программная реализация алгоритма Годри — Шоста и его модификации Гэлбрайта — Рупрая для подсчёта точек в якобианах гиперэллиптических кривых. Эти алгоритмы представляют собой версии алгоритма Мацуо — Чао — Цуджия с малым использованием памяти и реализуют стратегию Гельфонда — Шенкса больших и малых шагов. Выводится оптимальный размер памяти, позволяющий минимизировать время работы указанных алгоритмов и получить на практике ожидаемое время их работы, близкое к теоретическим оценкам $2{,}45\sqrt{N}$ и $2{,}38\sqrt{N}$ для алгоритмов Годри — Шоста и Гэлбрайта — Рупрая соответственно. Здесь $N$ — размер двумерной области поиска, равный порядку якобиана кривой, уменьшенному в $m$ раз с помощью других методов. Предлагаемая реализация алгоритмов имеет многопоточный режим работы. Представлена статистическая зависимость времени работы от размера входных данных. Данная реализация алгоритма Гэлбрайта — Рупрая для размерности $2$ является первой опубликованной многопоточной реализацией этого алгоритма с открытым исходным кодом.
Ключевые слова:
гиперэллиптическая кривая, якобиан, подсчёт точек, парадокс дней рождения.
Образец цитирования:
N. S. Kolesnikov, “Implementation of point-counting algorithms on genus $2$ hyperelliptic curves based on the birthday paradox”, ПДМ, 2022, no. 55, 120–128
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm765 https://www.mathnet.ru/rus/pdm/y2022/i1/p120
|
Статистика просмотров: |
Страница аннотации: | 80 | PDF полного текста: | 32 | Список литературы: | 15 |
|