Implementation of point-counting algorithms on genus $2$ hyperelliptic curves based on the birthday paradox

Представлена эффективная программная реализация алгоритма Годри — Шоста и его модификации Гэлбрайта — Рупрая для подсчёта точек в якобианах гиперэллиптических кривых. Эти алгоритмы представляют собой версии алгоритма Мацуо — Чао — Цуджия с малым использованием памяти и реализуют стратегию Гельфонда — Шенкса больших и малых шагов. Выводится оптимальный размер памяти, позволяющий минимизировать время работы указанных алгоритмов и получить на практике ожидаемое время их работы, близкое к теоретическим оценкам $2{,}45\sqrt{N}$ и $2{,}38\sqrt{N}$ для алгоритмов Годри — Шоста и Гэлбрайта — Рупрая соответственно. Здесь $N$ — размер двумерной области поиска, равный порядку якобиана кривой, уменьшенному в $m$ раз с помощью других методов. Предлагаемая реализация алгоритмов имеет многопоточный режим работы. Представлена статистическая зависимость времени работы от размера входных данных. Данная реализация алгоритма Гэлбрайта — Рупрая для размерности $2$ является первой опубликованной многопоточной реализацией этого алгоритма с открытым исходным кодом.