Вычисление идеала 3-кручения для некоторого класса гиперэллиптических кривых | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/3

Вычисление идеала 3-кручения для некоторого класса гиперэллиптических кривых

Рассмотрены гиперэллиптические кривые рода 2, определяемые многочленом Диксона. Для таких кривых представлено вычисление идеала 3-кручения, в частности получены его четыре образующие с использованием представления Мам-форда - Кантора для дивизора 3-кручения и теории 9- и р-функций.

Calculation of 3-torsion ideal for some class of hyperelliptic curves.pdf Введение Модулярные уравнения, связывающие инварианты l-изогенных эллиптических кривых, являются фундаментальным инструментом в арифметической геометрии. Одним из важных приложений модулярных уравнений является вычисление порядка точек эллиптической кривой над конечным полем. Наилучшим методом является алгоритм Шуфа - Элкиса - Аткина [1], в котором широко используются точки l-кручения. На сегодняшний день такие уравнения могут быть эффективно вычислены даже для больших значений l. Однако для кривых рода g ^ 2 информации о вычислении модулярных уравнений крайне мало. Будем рассматривать гиперэллиптические кривые рода 2, определяемые многочленом Диксона [2], и для них представим формулы для вычисления идеала l-кручения в случае l = 3. Следует отметить, что идеал l-кручения является главной составляющей при вычислении модулярного уравнения. В свою очередь, модулярное уравнение можно использовать для исследования изо-гений абелевых многообразий, что является важным инструментом не только для изучения абелевых многообразий, но и для криптографических приложений, основанных на изогениях. Использование специального класса гиперэллиптических кривых на основе многочленов Диксона обусловлено рядом причин. Во-первых, якобиан кривой с уравнением C : y2 = x2g+1 + axg+1 + bx допускает разложение [3] JaCFq [ Г ](C) ^ JaCFq [ Щ (C1) X JaCFq [ Г] ( C2 ) в случае, если g(C) нечётно, и JaCFq [ Г ](C) - JaCFq [ ГЬ] (Fq [ ^b]) X JaCFq [ #Ь] О^ ) , если g(C) чётно. При этом кривые C1,C2,C3, C3 определены многочленами Диксона Dg(x,a). Во-вторых, в [4] мы получили явные формулы для многочленов деления и, как следствие, представление Мамфорда - Кантора для дивизоров 3-кручения. Вычисление точек в якобиане исходной кривой C, таким образом, может быть сведено к более лёгкой задаче, а именно к вычислению числа точек в якобианах соответствующих кривых C1, C2 и C3, C3. 1. Модулярное уравнение Пусть гиперэллиптическая кривая C/Fq рода g(C) = 2 определена уравнением 2g+1 C : Y2 = / (X) = £ /jXj = X5 + /4X4 + /3X3 + /2X2 + /1X + /0. i=0 Обозначим JaCF (C)[l] подгруппу l-кручения элементов якобиана JaCF (C) кривой C, где l - простое число и l = Char(Fq). Далее пусть l = 3 и D Е JaCFq(C)[3] -дивизор 3-кручения веса 2, то есть D = [3](P -rc) + [3](P2 - то), где P1 = (x1,y1) и P2 = (x2,y2) - точки кривой C. Данный дивизор можно записать с помощью представления Мамфорда - Кантора, вычислив прежде многочлены деления: D = (u(X ),v(X)) = (X2 + U1X + U0,V1X + V0). Тогда существует радикальный идеал /3 С Fp[x1,x2,y1,y2], такой, что D Е JaCFq(C)[3] ^ /(x1,x2,y1,y2) = 0, V/ Е /3. По аналогии с эллиптическими многочленами деления идеал /3 называется 3-идеалом деления или идеалом 3-кручения. Согласно гипотезе Манина - Мамфорда [5], все ненулевые дивизоры 3-кручения имеют вес 2, следовательно, степень идеала /3 равна 34 - 1. Определим t3(D) = u1(D), где u1(D) соответствует коэффициенту u1 в представлении Мамфорда - Кантора дивизора D. Необходимо вычислить значение t3(D) по модулю /3. Положим h1,3 Е Fp[x1, x2, y1, y2] -многочлен, принимающий значение u1(D) на дивизоре 3-кручения D. Чтобы получить h1,3, необходимо вычислить координаты Мамфорда - Кантора для дивизора (P1 - то) + (Р2 - то). Тогда х3 = П (T-t3(D)) D€ JacFq (C)[3]\\{0} является характеристическим многочленом h1,3 mod/3. Зная х3, можно вывести модулярное уравнение Ф3, где х3 = Ф2 и degФ3 = (34 - 1)/2. 2. Идеал 3-кручения Напомним, что V/ Е /3 ([3](P - то) = - [3](P2 - то) ^ D Е JaCFq(C)[3] ^ /(x1,x2,y1,y2) = 0) и D = (u(X ),v(X)) = (X2 + U1X + U0,V1X + V0). Идеал 3-кручения /3 является идеалом в кольце Fq [x1, x2, y1, y2] с алгебраическим множеством V(/3) = (JaCFq(C) - ©)[3] = (JaCFq (C) - в) П JaCFq(C)[3]. Здесь в является дополнением к образу a(Z) в JaCFq (C) при отображении a : C2 ^ JaCFq (C) и Z С C2, то есть в = {[P - то]}, где P - точка кривой C. Согласно [6], идеал 3-кручения определён следующим образом: /3 = (F1(p(z), p'(z), p"(z), p'"(z)), F2(p(z), p'(z), p"(z), p'"(z)), F3(p(z), p'(z), p"(z), p'"(z)), Здесь p является ^-функцией Вейерштрасса для гиперэллиптического случая, то есть p(z) = -4D^ (log0[O](z)), " " 1. где 0 Е 2Z2 и 0[O](z) = 0[O](z,r)= £ exp(ni(m + a)V(m + a) + 2ni(m + a)*(z + b)) m£Z2 является классической ^-функцией с характеристикой 0. Для вычисления идеала /3 нам понадобится следующая Теорема 1 [6]. Морфизм ' JaCfc (C) - в ^ ^ : S / ^ (p(z),p'(z),..., p(2g-1)(z)) есть вложение, такое, что p(i)(z) для i Е {0,... , 2g - 1} порождают аффинное кольцо в JaCFq (C) - в. С помощью уравнения кривой C : Y2 = /(X) величины p(i)(z) выражаются через универсальный многочлен с коэффициентами, зависящими от u(t), v(t), w(t) модели JaCFq(C) -в = {(u(t), v(t), w(t)):/(t) -v2(t)=u(t)w(t), degu=g, deg v ^ g- 1, deg w=g+1}. Коэффициенты многочленов u(t), v(t), w(t) выражаются также с помощью универсального многочлена от переменных p(i)(z). Принимая во внимание, что мы работаем с дивизором 3-кручения, являющимся представителем класса [D] Е (JaCFq (C) - в)[3], и что представление Мамфорда- Кантора для дивизоров [3](P1 - то) и [3](P1 - то), сумма которых есть дивизор D = (X2 + u1X + u0, v1X + v0), задано явно в [4], введём следующие обозначения: X1 = - U1(x1 ,x2,y1,y2 ) + 2 /1, X2 = -v1(x1 ,x2,y1,y2 ), 13 X3 = - 2 /2 + /1 ■ u1(x1,x2,y1,y2) - 2 u2(x1 ,x2,y1,y2), X4 = /1 ■ v1(x1,x2,y1,y2) - 3v1(x1 ,x2,y1,y2)U1(x1,x2,y1,y2). Для гиперэллиптической кривой C/Fp рода g = 2 с уравнением Y2 = (X - 2)(D4(X) + c) = X5 - 2X4 - 4aX3 + 8aX2 + (2a2 + c)X - 4a2 - 2c, где D4(X) = X4 - 4aX2 + 2a2 -многочлен Диксона, положим a =1, тогда окончательно уравнение кривой примет вид Y2 = X5 - 2X4 - 4X3 + 8X2 + (c + 2)X + (-2c - 4). Формулы для первых двух образующих F1 и F2 идеала 3-кручения: F\\(XbX2,X3,X4) = -2 - c + 8U1 + 4u2 + 8v2 - 2« - «4 + 11v2 ■ «1, , . 6488065 25362425 2 2 32440325 3 _ 2 F2(X1,X2,X3,X4) : = 2c--u1--u1 + 20v2 +-«3 + 44v2 ■ u1 + A 1 2' 3' 4 294912 1 1179648 1 1 589824 1 1 23789569 4 00 2 2 1Г 5 589825 +--«4 + 33v2 ■ «2 + 15u5--. 393216 1 1 1 1 294912 Формула для F3 слишком объёмная и связана с вычислением 0-констант, поэтому упростим её представление следующим образом: 12 d( F3(X1,X2,X3,X4) = -(3X23+X3X4-X2X5)((X1 - F1)3+2(X22 - F )+2(F -x1)(fP3+X3)), где 5 X5 = -8 + 22«2 (x1,x2,y1 ,y2) + 10«3(x1,x2,y1,y2) + 2 v2(x1,x2,y1,y2); - 27X|X| + 27X^X4 + 18X2X33 X4 - 9X|X3X| - X44 - 18X|X|X5 - 3X23X4X5+ +2X3XIX5 - 2X2X4XI ^ (3X23 + X3X4 - X2X5)2 P 1 4X2X3X4X3 - 60X3X3X4 X52 + 45X22X32X2X5 + 54X22X32X4X5 + 243X^X3X4X5+ F2 ---- 2 2 F = d +36X2 X34X4X5 + 324X26X33 - 81X28X5 + 54X26X52 - 18X35X42 + 27X25X43 - 3X24X53 - -2X22X54 + 54X23X34X4 - 54X24X33X5 - 243X27X3X4 - 27X4X32X2 - 162X24X32X4- -54X2X33X42 - 18X|X|X| + 18X2 XfX| + 9X22X3X44 - 3X23X43X5 + 2X3X^X5- -2X2X43X52 - 2X32 X42X52 - 486dX|X| + 54dX25X43 - 2dX46 - 216dX24X32X2+ +486dX27X3X4 + 324dX23X34X4 + 36dX2X33X43 - 36dX22X3 X44 - 324dX4X|X5- -6dX23X43X5 + 4dX3 X44X5 - 4dX2X43X52 - 54dX25X3X4X5 - 36dX23X3X4X52 (3X23 + X3X4 - X2X5)3 972X210X3X5 - 2754X26X 4 P 1 972X210X3X5 - 2754X26X33X42 - 1512X3X4X43 + 8X2X45X52 - 1944X27X32X52+ F 3 = - ~ + 1620X28X42X5 - 801X26X42X52 + 2916X29X32X5 + 972X4X34X2 + 27X24 X32X44 - -648X4X3X4X52 + 180X2X34X43X5 + 1512X|X32X4X2 + 648X24X33 X42X5 - -6156X27X32X4X5 - 1944X|X|X4X5 + 1944X26X33X4X5 + 324X23X34X2X5+ +5832X29X32X4 + 324X|X|X| - 486X25X3X43X5 + 972X22X36X42 - 8748X28X34 - -729X210X42 + 18X35X44 - 54X35X43 - 108X25 X45 + 6dX48 + 144dX22X3X46+ + 162X28X3X52 - 657X| X3 X53 + 5346X26X33X4 + 1620X23X34 X42 - 972X27X3X42+ + 108X2X33X4 - 486X27X32X5 + 324X25X32X52 - 54X3X32X3 - 18X2X33X45+ +78X24X42 X53 + 168X24X3X54 + 12X32X44X2 + 12X22 X42X54 - X33X2X3 - X22X3X55- -36X22X3X46 + 12X23 X45X5 - 252X2X33X2X2 - 1944X24X33X4X5 + 54X2X34 X42X5+ +54X22X33 X4X2 + 648X25X3X42X5 - 108X23X3X42X2 - 114X3X2X4X53 - -270X2X32X44X5 + 210X3X3X43 X| - 24X2X3XIX3 + 2X2XIX4X4 + 7776dX26X33X42- - 1944dX23X34X3 + 16dX2X45X52 - 2916dX27X3X43 + 1350dX24 X32X44 - 11664dX29X32X4- -7776dX25X35X4 + 7776dX26X34X5 - 144dX2X33X45 - 8X3X6X5 + 1080dX25X32X4X2+ + 10206dX28X34 - 216dX25X45 + 864dX4X33X2X5 - 648dX27X32X4X5 + 540dX25X3X43X5+ +24dX23X45X5 - 16dX3X46X5 - 324dX28X42X5 - 198dX26X42X52 + 648dX4X34X52+ +648dX2X36X2 + 24dX4X2X53 + 8dX32X4X52 + 8dX22X42X4 - 72dX2X32X4X5+ + 192dX3X3X43X52 + 144^X2X4X3X5 + 1458dX210X42 - 1296dX23X35X4X5- -288dX2X33X2X52 + 144dX23X32X4X3 - ШХ2Х3Х3Х3 (3X23 + X3 * X4 - X2 * X5)4 и константа d сопряжена с вычислением в-констант: в : (0), в ^ (0). Четвёртая образующая F4 идеала 3-кручения имеет следующий вид: +6 X1 X23 X3 X4 - 6 X1 X24 X5 + X1 X32 X42 - 2 X1 X2 X3 X4 X5 + X1 X22 X 2 25 1 -27dX24X32 + 27dX25X4 + 18dX2X33X4 - 9dX22X3X42 - dX44- F4 (X1 ,X2 j X3 ,X4) - ^ -18dX22X32X5 - 3dX23X4X5 + 2dX3X42X5 - 2dX2X4X52 + 9XiX26+ + F, (3X3 + X3X4 - X2X5)2 где выражение F4 сопряжено с вычислением р- и в-функций.

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

гиперэллиптическая кривая, многочлен Диксона, идеал I-кручения, дивизор l-кручения, модулярное уравнение, hyperelliptic curve, Dickson polynomial, l-torsion ideal, l-torsion divisor, modular equation

Авторы

ФИООрганизацияДополнительноE-mail
Малыгина Екатерина СергеевнаБалтийский федеральный университет им. И. Кантакандидат физико-математических наук, доцентEkkat@inbox.ru
Всего: 1

Ссылки

Cohen H. and Frey G. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman and Hall/CRC, 2005.
LidlR., Mullen G.L., and Turnwald G. Dickson Polynomials. Chapman and Hall/CRC, 1993.
Novoselov S. A. Counting points on hyperelliptic curves of type y2 = x2g+1 + ax9+1 + bx. arXiv: 1902.05992. 2019.
Malygina E. S. and Novoselov S. A. Division polynomials for hyperelliptic curves defined by Dickson polynomials // Proc. 8th Workshop on Current Trends in Cryptology. Svetlogorsk, Kaliningrad region, June 4-7, 2019. https://ctcrypt.ru/ematerials2019.
Hindry M. and Silverman J. Diophantine Geometry. An Introduction. Graduate Texts in Mathematics. V. 201. Springer Verlag, 2000.
Kampkotter W. Explizite Gleichungen fur Jacobische Varietatenhyperelliptisher Rurven.Ph. D. Thesis, Universitat Gesamthochschule Essen, 1991.
 Вычисление идеала 3-кручения для некоторого класса гиперэллиптических кривых | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/3

Вычисление идеала 3-кручения для некоторого класса гиперэллиптических кривых | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/3