Характеристические многочлены некоторых гиперэллиптических кривых родов 2,3 и р-ранга 1 | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/5

Характеристические многочлены некоторых гиперэллиптических кривых родов 2,3 и р-ранга 1

Исследуются характеристические многочлены некоторых классов гиперэллиптических кривых рода 2, 3 р-ранга 1 над конечным полем. р-Ранг является важным инвариантом кривой, который накладывает ограничения на характеристический многочлен кривой и, следовательно, на число точек в её якобиане. Получены сравнения (по модулю характеристики) и ограничения на коэффициенты для характеристических многочленов кривых р-ранга 1 с автоморфизмами.

On characteristic polynomials for some genus 2 and 3 curves with p-rank 1.pdf Введение Гиперэллиптическая кривая C рода g над конечным полем Fq задаётся уравнением у2 + h(x)y = f (ж), где h(x),f(ж) G Fq[ж] и degh(x) ^ g + 1, degf(ж) = 2g + 1 или degf(ж) = 2g + 2 и многочлен f (ж) является унитарным. В настоящее время гиперэллиптические кривые изучаются как альтернатива эллиптическим кривым. Гиперэллиптические кривые требуют меньший размер ключа при сравнимом уровне безопасности. Одними из перспективных направлений в криптографии на (гипер)эллиптических кривых являются классическая криптография на дискретном логарифме, криптография на билинейных спариваниях, постквантовая криптография на изогениях. Для криптографии на дискретном логарифме необходимы кривые рода 2 и 3 с большим простым числом точек в якобиане. Для кривых больших родов имеются атаки методом исчисления индексов. Для криптографии на билинейных спариваниях, помимо требований для стойкости дискретного логарифма, необходимы кривые с малой степенью вложения. Ярким примером применения криптосистем на билинейных спариваниях является механизм Zk-Snark, применяемый в криптовалюте Zcash. В основе Zk-Snark лежит редуцированное эйт-спаривание. Криптография на изогениях гиперэллиптических кривых в настоящее время только начинает развиваться. Основной проблемой является отсутствие эффективных формул для вычисления изогений. Множество точек гиперэллиптических кривых рода 2 и 3 не образует группу, в отличие от эллиптических кривых, поэтому для использования таких кривых в криптографии строится ассоциированная с кривой группа - якобиан кривой. Определение 1. Якобианом гиперэллитической кривой C называется факторгруппа Jc = Div0(C )/Pr(C), где Div0(C) -множество дивизоров степени 0; Pr(C) -множество главных дивизоров кривой C. Важным инвариантом гиперэллиптической кривой является р-ранг. Определение 2. Пусть C - гиперэллиптическая кривая. Тогда JC[ре] = (Z/peZ)r для 0 ^ r ^ g и e ^ 1. Число r называется р-рангом кривой C. Хорошо исследованы кривые с р-рангом 0, которые имеют маленькую степень вложения, и р-рангом 2, подавляющее большинство которых имеют большую степень вложения. Для суперсингулярных абелевых многообразий (р-ранг равен 0) известны [1] полные списки возможных характеристических многочленов. Соответственно задача подсчёта точек на суперсингулярных кривых может быть решена простым перебором возможных вариантов. Для кривых р ранга 1 подобных списков в настоящее время не составлено. В данной работе исследуются характеристические многочлены для кривых р-ран-га 1. В силу того, что данные кривые являются промежуточным случаем, мы предполагаем возможность существования как классов кривых с маленькой степенью вложения, так и кривых с большой степенью вложения. Будем рассматривать классы кривых рода 2, чей р-ранг не превосходит 2, и кривые рода 3, чей р-ранг меньше или равен 3. Среди них выделим кривые р-ранга 1. 1. Характеристический многочлен и р-ранг L-многочлен кривой связан с р-рангом посредством следующей теоремы. Теорема 1 (Штихтенот). Пусть L(T) = a0 + aT + a2T2 +... + a2gT2g, тогда р-ранг кривой C равен max{i : a ф 0 (modp)}. Если кривая имеет автоморфизмы, определённые над некоторым расширением конечного поля, то, в силу следующей теоремы, это накладывает дополнительные ограничения на характеристический многочлен данной кривой. Теорема 2 [4]. Пусть k - поле, K - расширение поля k, A - абелево многообразие над полем k и т G EndK(AK), такой, что 1) действие группы Gal(K|k) на EndK(AK) отображает подпространство Q[t] С С EndK (Ak ) в себя; 2) т не определено ни над одним промежуточным полем ^ расширения K|k, где ц С K; 3) Q[t] -поле. Тогда характеристический многочлен эндоморфизма Фробениуса абелева многообразия A имеет вид f (TtK:fc]) для некоторого многочлена f (T) G Z[T] степени 2 dim(A)/[K : k]. Так как якобиан гиперэллиптической кривой является абелевым многообразием, то теорема 2 применима и к гиперэллиптическим кривым. Это позволяет получить следующий результат. Теорема 3. Пусть дана гиперэллиптическая кривая C рода g, такая, что выполняются условия теоремы 2. Тогда rc ^ [K : k]. Кроме того, имеет место следствие для кривых рода g и р-ранга 1. Следствие 1. Кривая C рода g может иметь р-ранг 1 только при условии [K : k] = 1. Заметим, что следствие не гарантирует наличия р-ранга 1 у кривой C, однако это необходимое условие в контексте теоремы 2. Применим эти результаты к некоторым классам гиперэллиптических кривых. 2. Кривые р-ранга 1 и их характеристические многочлены Для кривых рода 3 с нетривиальной группой автоморфизмов р-ранг может быть определён с помощью результатов из [3], что позволяет выделить кривые р-ранга 1. Теорема 4. Пусть гиперэллиптическая кривая C/Fp рода 3 имеет группу автоморфизмов C14. Тогда уравнение кривой имеет вид y2 = x7 + 1. Положим (р - 1)/2 W (р - 1)/2 W (р - 1)/2 \\ w = / (р - 1)/2 \\/ (р - 1)/2 \\ + 5(р - 1)/lV ^3(р -1)/1^ \\(р - 1)Л4/ ,W W - 1)/1V \\3(р - 1)/14/ + / (р - 1)/2 \\/(р - 1)/2\\/ (р - 1)/2 \\/(р - 1)/2\\ \\5(р - 1)/W \\(р - 1)/1V \\3(р - 1)/1^ \\(р - 1)/14/ . Тогда кривая C имеет р-ранг 1, если р ф 1 (mod 7), v ф 0 (mod р) и w ф 0 (mod р). Кроме того, характеристический многочлен эндоморфизма Фробениуса имеет следующий вид: X(A) ф A2g + vA2g-1 (mod р). Теорема 5. Пусть группа автоморфизмов G кривой C равна D12. Тогда кривая имеет модель y2 = x(x6 + ax3 + 1), где a G K. Обозначим c = P(p-1)/2(p), d = P(p-1)/6(p), e = P(p-5)/6(p), где p = -a/2 и Pn - многочлены Лежандра. Тогда если a = 0, то 1) р-ранг кривой равен 1 при р ф 1 (mod 3), c + 2d ф 0 (mod р) и c2 + 2cd ф ф 0 (mod р). В этом случае многочлен Фробениуса по модулю р равен Х(А) ф A2g + (c + 2d)A2g-1 (mod р); 2) р-ранг равен 1 при р ф 2 (mod 3), c ф 0 (mod р) и e ф 0 (mod р). В этом случае многочлен Фробениуса по модулю р равен х(А) ф A2g + cA2g-1 (mod р). Теорема 6. Пусть группа автоморфизмов G кривой C равна Vg. Тогда данная кривая имеет вид y2 = x8 - 1. Пусть = 1 (р - 1)/2 Ч + /(р - 1)/2\\ + /(р - 1)/2 Ч3(р- 1)/^Ч(р -1)/^Ч(Р - 1)/8 t = / (р - 1)/2 \\ /(р - 1)/2\\ / (р - 1)/2 \\ /(р - 1)/2\\ + /(р - 1)/2\\ /(р - 1)/2 ^3(р - 1)/^ ^р - 1)/4У + ^3(р - 1)/^ 1(р - 1)/V + \\(р - 1)/4У 1(р - 1)/8 Тогда 1) если р ф 1 (mod 8), то при s ф 0,t ф 0 (mod р) кривая имеет р-ранг 1. В этом случае многочлен Фробениуса по модулю р равен X(A) ф A2g + wA2g-1 (mod р); 2) если р ф 5 (mod 8) и r = , то при r ф 0 (mod р) кривая имеет р-ранг 1. В этом случае многочлен Фробениуса по модулю р равен X(A) ф A2g + rA29-1 (mod р). Теорема 7. Пусть группа автоморфизмов G кривой C равна D8 х C2. Тогда кривая имеет модель y2 = x8 + ax4 + 1, где a G K. Пусть a = P(p-1)/4(p), b = P(p-3)/4 (p), c = P(p-1)/2(p), где p = -a/2. Тогда 1) если р ф 1 (mod 4), то р-ранг кривой равен 1 при a ф 0, c ф 0 (mod р). В этом случае многочлен Фробениуса по модулю р равен x(A) ф A29 + cA29-1 (mod р); 2) если р ф 3 (mod 4), то р-ранг кривой равен 1 при b ф 0, c ф 0 (mod р). В этом случае многочлен Фробениуса по модулю р равен X(A) ф A29 + cA29-1 (mod р). Заключение В работе получены характеристические многочлены (mod р) гиперэллиптических кривых рода 2, 3 и р-ранга 1 для кривых с автоморфизмами. В дальнейшем на основе полученных результатов планируется построить алгоритм подсчёта числа точек на кривых, изоморфных кривым с автоморфизмами над расширением конечного поля, по аналогии с работой [5] и исследовать их степени вложения с целью анализа возможности применения таких кривых как в классических криптосистемах, так и в криптосистемах на основе билинейных спариваний и изогений.

Ключевые слова

гиперэллиптические кривые, р-ранг, характеристические многочлены, группа автоморфизмов, hyperelliptic curves, p-rank, characteristic polynomial, authomorphism group

Авторы

ФИООрганизацияДополнительноE-mail
Мельничук Евгений МихайловичБалтийский федеральный университет им. И. Кантааспирантemelnichuk39@gmail.com
Новоселов Семен АлександровичБалтийский федеральный университет им. И. Кантаассистентsnovoselov@kantiana.ru
Всего: 2

Ссылки

Singh V., ZatysevA., and McGuire G. On the Characteristic Polynomial of Frobenius of Supersingular Abelian Varieties of Dimension up to 7 over Finite Fields. arXiv preprint arXiv:1011.2257. 2010.
Novoselov S. A. Hyperelliptic curves, Cartier - Manin matrices and Legendre polynomials // Прикладная дискретная математика. 2017. №37. С. 20-31.
Мельничук Е. М., Новоселов С. А. p-Ранги гиперэллиптических кривых рода 3 с нетривиальной группой автоморфизмов // Труды математического центра имени Н. И. Лобачевского. 2018. Т. 56. C. 188-192.
Bouw I.I., Diem C., and Scholten J. Ordinary elliptic curves of high rank over with constant j-invariant // Manuscripta Mathematica. 2004. V. 114. No. 4. P. 487-501.
Novoselov S. A. Counting points on hyperelliptic curves of type y2 = x29+1 + ax9+1 + bx. https://arxiv.org/abs/1902.05992. 2019.
 Характеристические многочлены некоторых гиперэллиптических кривых родов 2,3 и р-ранга 1 | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/5

Характеристические многочлены некоторых гиперэллиптических кривых родов 2,3 и р-ранга 1 | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/5