Дата публикации: 2022

Дата публикации в реестре: 2022-10-06T22:40:50Z

Аннотация:

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

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2022. № 55. С. 120-128