On the order of the frobenius EN-domorphism action on L-torsion subgroup of abelian sur.pdf Введение Построение криптосистем на абелевых многообразиях и, в частности, на гиперэллиптических кривых является в настоящее время альтернативой эллиптической криптографии. Они позволяют обеспечить сравнимый уровень криптостойкости при меньшей длине ключа. Сдерживающим фактором в развитии таких криптосистем является трудоёмкость вычислений в якобианах гиперэллиптических кривых. Кроме того, на практике возникает задача подсчёта точек в якобианах, которая на данный момент решена лишь для некоторых частных случаев. Для эллиптических кривых есть эффективный алгоритм Шуфа - Элкиса - Аткина [1]. Для гиперэллиптических кривых рода 2 есть алгоритм Годри - Шоста [2], который является обобщением алгоритма Шуфа. Обобщение оптимизаций Элкиса и Аткина на случай кривых рода 2 и выше является открытой проблемой. В общем случае для любого абелева многообразия есть теоретический алгоритм подсчёта точек на абелевых многообразиях (обобщение алгоритма Шуфа) [3]. В его основе лежит поиск характеристического многочлена эндоморфизма Фробениуса xi, действующего на группу l-кручения. При этом xi находится простым перебором коэффициентов. Одна из оптимизаций Аткина, в случае эллиптических кривых, заключается в нахождении порядка действия Фробениуса на группу l-кручения и его использование для ускорения перебора xi. При этом сам порядок вычисляется из разложения модулярных многочленов. Для гиперэллиптических кривых рода 2 модулярные многочлены имеют большой размер, что делает их малопригодными для практических вычислений. Поэтому мы изучаем вероятностный подход для нахождения порядка действия Фробениуса. В [4] представлена идея улучшения алгоритма за счёт оценки вероятностного распределения порядка действия эндоморфизма Фробениуса. В настоящей работе получены дополнительные характеристики распределения порядков матриц, соответствующих действию эндоморфизма Фробениуса на группу l-кручения. Вычислены дисперсия распределения и среднеквадратическое отклонение. Исследование выполнено при финансовой поддержке РФФИ, проект № 18-31-00244. 1. Распределение порядков действия эндоморфизма Фробениуса Пусть A - абелева поверхность над конечным полем Fq нечётной характеристики p. Будем рассматривать действие эндоморфизма Фробениуса на группу l-кручения A[l], где l - простое число, такое, что q = 1 mod l. В этом случае действие эндоморфизма Фробениуса на группу l-кручения как линейного оператора может быть представлено симплектической матрицей F} Е PSp2g (Fj), где g = 2 - размерность абелева многообразия. Введём случайную величину £, которая принимает значения порядков r = Ord(FJ) симплектических матриц как элементов группы PSp4(Fj). Отношение подобия разбивает симплектическую группу на классы эквивалентности [Aj], в каждом из которых встречаются матрицы одного порядка r = Ord(Aj). Эти порядки вычислены для каждого класса в [4]. Там же приводится формула для вычисления математического ожидания M(£). Определим числовые характеристики этой случайной величины: р(, = . = #{A Е PSp4(F}) : Ord(A) = rfc} = #[An] + ... + ] Гк) #PSp4(Fj) #PSp4(Fj) ' где Aj1,... , Ais -представители всех классов, таких, что Ord(Aix) = ... = Ord(Ais) = = rk. Из [4] имеем M(£) = Еrk #[Aii] + ... + ] = EOrd(Aj) #[Aii] ^ j=1 k #PSp4(Fj) j=1 v " #PSp4(Fj) n2 2l5 + 16l4 - 48l3 + 65l - 37 1 _ _ _ - - - . 48 l(l2 - 1) log(l) Последнее выражение получено при помощи аппроксимации функции НОД из работы [5]. Теорема 1. Пусть A - абелева поверхность над конечным полем Fq характеристики p и l = p - простое число, такое, что q = 1 mod l. Тогда при q ^ l дисперсия распределения порядков действия эндоморфизма Фробениуса на A [l] и его среднеквад-ратическое отклонение могут быть вычислены по следующим формулам: D(° ~ \\48j l2(l2 - 1)2 log2(l), а(е) = VD(e) ~ 48 l(l2 - 1) log(l), где ^(l) = 2l10 + 56l9 - 316l8 + 1344l7 - 1948l6 - 1770l5 + 6660l4 - 3516l3 - 3831l2 + 4684l - 1369.

Скачать электронную версию публикации