Implementation of point-counting algorithms on genus 2 hyperelliptic curves based on the birthday paradox N. S. Kolesnikov
Material type:
ArticleContent type: Текст Media type: электронный Other title: Реализация алгоритмов подсчета точек в якобианах гиперэллиптических кривых рода 2, основанных на парадоксе дней рождения [Parallel title]Subject(s): гиперэллиптическая кривая | якобиан | подсчет точек | парадокс дней рожденияGenre/Form: статьи в журналах Online resources: Click here to access online
In:
Прикладная дискретная математика № 55. С. 120-128Abstract: Представлена эффективная программная реализация алгоритма Годри — Шоста и его модификации Гэлбрайта — Рупрая для подсчёта точек в якобианах гипе-рэллиптических кривых. Эти алгоритмы представляют собой версии алгоритма Мацуо — Чао — Цуджия с малым использованием памяти и реализуют стратегию Гельфонда — Шенкса больших и малых шагов. Выводится оптимальный размер памяти, позволяющий минимизировать время работы указанных алгоритмов и получить на практике ожидаемое время их работы, близкое к теоретическим оценкам 2;45pN и 2;38pN для алгоритмов Годри — Шоста и Гэлбрайта — Рупрая соответственно. Здесь N — размер двумерной области поиска, равный порядку якобиана кривой, уменьшенному в m раз с помощью других методов. Предлагаемая реализация алгоритмов имеет многопоточный режим работы. Представлена статистическая зависимость времени работы от размера входных данных. Данная реализация алгоритма Гэлбрайта — Рупрая для размерности 2 является первой опубликованной многопоточной реализацией этого алгоритма с открытым исходным кодом.
Библиогр.: 10 назв.
Представлена эффективная программная реализация алгоритма Годри — Шоста и его модификации Гэлбрайта — Рупрая для подсчёта точек в якобианах гипе-рэллиптических кривых. Эти алгоритмы представляют собой версии алгоритма Мацуо — Чао — Цуджия с малым использованием памяти и реализуют стратегию Гельфонда — Шенкса больших и малых шагов. Выводится оптимальный размер памяти, позволяющий минимизировать время работы указанных алгоритмов и получить на практике ожидаемое время их работы, близкое к теоретическим оценкам 2;45pN и 2;38pN для алгоритмов Годри — Шоста и Гэлбрайта — Рупрая соответственно. Здесь N — размер двумерной области поиска, равный порядку якобиана кривой, уменьшенному в m раз с помощью других методов. Предлагаемая реализация алгоритмов имеет многопоточный режим работы. Представлена статистическая зависимость времени работы от размера входных данных. Данная реализация алгоритма Гэлбрайта — Рупрая для размерности 2 является первой опубликованной многопоточной реализацией этого алгоритма с открытым исходным кодом.
There are no comments on this title.