On construction of maximal genus 3 hyperelliptic curves.pdf Максимальные кривые, т. е. кривые с максимально возможным числом точек, достигающим верхнюю границу Хассе - Вейля - Серра, находят широкое применение как в криптографии, так и в теории алгебраических кодов. Пусть C : y2 = = x7 + ax4 + bx - гиперэллиптическая кривая рода 3 над конечным полем Fq, q = pn, p > 3. В случае, когда b - кубический вычет, якобиан Jc этой кривой допускает декомпозицию на эллиптические кривые, что описывается следующей теоремой, ранее доказанной авторами в [1]. Теорема 1 [1]. Пусть C : y2 = x7 + ax4 + bx - гиперэллиптическая кривая рода 3, определённая над конечным полем Fq, q = pn, p > 3, и b - кубический вычет. Тогда: 1) Если q = 1 (mod 6), то Jc ~ E1 х /2 над Fq и xC,q(T) = (T2 - t1T + q)(T2 - - t2T + q)2, где E1 : y2 = x3 + ax2 + bx, E2 : y2 = x3 - 3^bx + a - эллиптические кривые; t1,t2 -их следы Фробениуса. 2) Если q = 5 (mod 6), то Jc ~ E1 х E2 х /'.2 над Fq и xC,q (T) = (T2 - t1T + q)(T2 - - t2T + q)(T2 + t2T + q), где E2 - скручивание кривой E2. Для установления соотношения между j -инвариантами эллиптических кривых / 1 и / 2 нами доказана следующая теорема. Теорема 2. Пусть заданы две эллиптические кривые над полем K: Ei : y2 = x3 + ax2 + bx, E2 : y2 = x3 - 3v'bx + a. Тогда справедливы следующие соотношения для их j -инвариантов: ) =256(a2 - 3b)3 j( 1) b2(a2 - 4b) ; j(E2) = - 4•1728b a2- 4b ; j(E1) = j(E2) 27 4 1728-г j(E2) 1. Максимальные кривые в случае j(E1) = 0 или j(E1) = 1728 Следствие 1. Справедливы следующие утверждения: 1) j(Ei) = 0 о j(E2) = 4 • 1728; 2) j(Ei) = 1728 о j(E2) = 1728 или j(E2) = -8 • 1728. Замечание 1. Случай j(Ei) = j(E2) = 0 невозможен, так как тогда дискриминант многочлена x7 + ax4 + bx обращается в нуль и кривая C будет не гладкой. Кривая C , заданная над Fq, называется максимальной кривой, если число точек на кривой N = 1 + q + g |_2^/q_|, то есть достигается верхняя граница Хассе - Вейля - Серра: 1 + q - gL2VqJ < N < 1 + q + gL2VqJ. Аналогичная граница известна также для якобианов [2, Theorem 14.15]: (V« - 1)2g « IJcI « (V« +1)2g. Если C - максимальная кривая, то |Jc| = (1 + |_2^/q_| + q)g. Таким образом, порядок якобиана максимальной гиперэллиптической кривой рода 3 равен 1 jc 1 = (1 + A'q. + q)3. Это, в свою очередь, означает, что характеристический многочлен кривой имеет вид Xc,q (T ) = (T2 + L2VijT + q)3. Тогда для гиперэллиптической кривой C : y2 = x7 + ax4 + bx рода 3, определённой над конечным полем Fq, q = pn, p > 3, выполняется JC ~ E1 X E22, где E1 : y2 = x3 + ax2 + bx, E2 : y2 = x3 - 3v'bx + a - эллиптические кривые, заданные над Fq. Их характеристические многочлены: XEi,q(T) = XE2,q(T) = T 2 + L2VqjT + q. Заметим, что в случае рассмотрения суперсингулярных эллиптических кривых над простым полем имеем XEi,p(T) = XE2,p(T) = T 2 + p. Согласно методу Вейля [3] для вычисления числа точек эллиптической кривой, число точек кривой E над произвольным расширением Fq , q = pr , равно Nr = pr + 1 - ar - вг. Здесь a и в - корни характеристического многочлена, который в случае суперсингулярных над полем Fp кривых Е1 и Е2 равен Хе/ fp(T) = T2 + p. Нетрудно видеть, что r = ±1 (mod 4), r = 2 (mod 4), r = 0 (mod 4). [о, ar + в = (iVp)r + .. = -2pr/2, I.-’/'" '• Таким образом, имеем (pr + 1, r = ±1 (mod 4), r = 2 (mod 4), r = 0 (mod 4). N- = }pr + 1 + 2pr/2, [pr + 1 - 2pr/2, Видно, что число точек будет максимально при r = 2 (mod 4), и кривая является максимальной, так как достигается верхняя граница Хассе - Вейля - Серра. Можно заметить, что Nr = pr + 1 + 2pr/2 = 1+ L2^qj + q = Хе(1) Xe(T) = T2 + 2, q T + q. Таким образом, для построения максимальной гиперэллиптической кривой нужно построить суперсингулярные эллиптические кривые E1 и E2 над простым полем Fp и рассмотреть их в расширении степени r = 2 (mod 4). С л у ч а й 1 . Будем искать кривую E2 в виде y2 = x3 + Ax. Заметим, что j-инвариант такой кривой j(E2) = 1728. Согласно следствию 1, получаем j(E1) = 1728. Из [3] известно, что эллиптическая кривая данного вида суперсингулярна над простым полем в случае, когда p = 3 (mod 4). Это равносильно p = 7, 11 (mod 12) при p > 3. Напомним, что E2 : y2 = x3 - 3tfbx + а, тогда из сравнения коэффициентов получим a = 0, b = -A3/27. Имеем искомое уравнение максимальной гиперэллиптической кривой: A3 C : y2 = x7 + ax4 + bx = x7 - - x. 27 Таким образом, перебрав все коэффициенты A G Fp, построим семейство максимальных гиперэллиптических кривых над расширением Fq, соответствующих эллиптической кривой E2 вида y2 = x3 + Ax, где q = pr; p > 3; p = 7, 11 (mod 12); r = 2 (mod 4). С л у ч а й 2 . Будем искать кривую E1, такую, что j(E1) = 1728. По следствию из теоремы 2, j(E2) = 1728 или j(E2) = -8 • 1728. Но случай j(E1) = j(E2) = 1728 мы уже рассмотрели, поэтому теперь рассмотрим случай j(E1) = 1728 и j(E2) = -8 • 1728. По известному методу (например, [4]) находим уравнение кривой E2 по заданному j-инварианту: 2 3 8 16 E2 : y = x--x +--. y 3 9 Отсюда a = 16/9, b = (8/9)3, и получаем уравнение максимальной гиперэллиптической кривой: 2 7 4 7 16 4 83 C : y = x + ax + bx = x +--x +--x. 9 93 Перебором классов изоморфизма кривых E2 мы получили, что кривая E2 суперсингулярна при p = 31, 131, 251, 383, 439, 1459, 1999, 2203, 2999, 3299, 4523, 4759, 5399, 5471 , 8719, 9323, . . . При этом все кривые, изоморфные суперсингулярной кривой E2, будут тоже суперсингулярны. Их можно получить следующим образом: E2 : y2 = x3 - -u4x + - u6, u G Fp. 3 9 p Сравнивая с уравнением y2 = x3 - 3tfbx + a, получаем коэффициенты 16 6 -3 12 a = 9 u ,b =93u . Имеем следующее уравнение для семейства максимальных гиперэллиптических кри вых: C : y2 = x7 + 16u6x4 + -3u12x. 9 93 Кривая E2, являющаяся скручиванием кривой E2, будет суперсингулярной в случае, когда Е2 суперсингулярна. Кроме того, весь класс кривых, изоморфных кривой E2, состоит из суперсингулярных кривых. Уравнение кривых, полученных скручиванием кривой E2, выглядит следующим образом: 2 3 - 2 16 3 E2 : y2 = x - -u x + - и . 39 Сравнивая с уравнением y2 = x3 - 3tfbx + а, получаем коэффициенты 16 3 -3 6 а 9 u b 9 u . Тогда имеем следующее уравнение для семейства максимальных гиперэллиптических кривых: C : y2 = x7 + 16u3x4 + -3u6x. 9 93 С л у ч а й 3 . Будем искать кривую E1 , такую, что j(E1 ) = 0. По следствию из теоремы 2 имеем j(E2) = 4 • 1728. Так как j(E1) = 0, кривая E1 суперсингулярна в случае, когда p = 2 (mod 3), что равносильно p = 5 (mod 6), когдаp > 3. Аналогично случаю 2, по заданному j-инварианту j(E2) находим уравнение кривой E2: 2 3 - E2 : y2 = x3 - 4x + -. 3 Отсюда a = -/3, b = (4/3)3, и уравнение максимальной гиперэллиптической кривой принимает следующий вид: - 43 C : y2 = x7 + 3 x4 + -x. Перебор классов изоморфизма кривых E2 показал, что кривая E2 суперсингулярна при p = 359, 647, 719, 971, 4391, 6263, 69-3, . . . При этом все кривые, изоморфные суперсингулярной кривой E2, будут тоже суперсингулярны. Их можно получить следующим образом: E2 : y2 = x3 - 4u4x + -u6, u G Fp. 3 Имеем следующее уравнение для семейства максимальных гиперэллиптических кривых: 8 4 3 C : y2 = x7 + -u6x4 +-3u12x. 3 3 3 Кривая E2, являющаяся скручиванием кривой E2, будет суперсингулярной в случае, когда Е2 суперсингулярна. Кроме того, весь класс кривых, изоморфных кривой Е2, состоит из суперсингулярных кривых. Уравнение кривых, полученных скручиванием кривой E2, выглядит следующим образом: Е2 : y1 = x3 - 4u2x + -u3. 3 Тогда получаем уравнение для семейства максимальных гиперэллиптических кривых: - 43 C : y1 = x7 +- u3x4 +-3u6x. 3 3 3 Пример 1. Построим семейство максимальных гиперэллиптических кривых рода 3, заданных над полем F31. Они являются максимальными над его расширением степени 2, то есть над полем F961 . Для данного поля якобиан максимальной гиперэллиптической кривой должен иметь порядок (7q + 1)2g = (V961 + 1)6 = (32)6 = 230 = 1073741824. При этом характеристические многочлены всех кривых над полем F961 имеют вид Xc,96i(x) = (x + 31)6, а для этих же кривых, рассматриваемых над полем F31,- Xc,3i(x) = (x1 + 31)3. Далее приведены 20 максимальных гиперэллиптических кривых; кривые в левом столбце построены как в случае 1, в правом - как в случае 2: y1 = 7 x7 + 4x y1 = 7 x7 + 14x4 + 16x y1 = 7 x7 + 2x y1 = 7 x7 + 3x4 + 2x y2 = 7 x7 + 30x y1 = 7 x7 + 19x4 + x y2 = 7 x7 + 27x y1 = 7 x7 + 17x4 + 16x y2 = 7 x7 + 15 x y1 = 7 x7 + 24x4 + 4x y1 = 7 x7 + 29x y1 = 7 x7 + 6x4 + -x y1 = 7 x7 + -x y1 = 7 x7 + 12x4 + x y1 = 7 x7 + 23x y1 = 7 x7 + 25x4 + -x y1 = 7 x7 + x y1 = 7 x7 + 2-x4 + 2x y1 = 7 x7 + 16x y1 = 7 x7 + 7x4 + 4x с помощью матрицы Картье - Манина кривой, так как её ранг равен p-рангу. Структура матриц Картье - Манина нашей кривой описана в [6]. Для кривой над полем Fp2 матрица Картье - Манина имеет вид для случая, когда p = 2 (mod 3). Здесь Pm(x) -многочлен Лежандра степени m. Поэтому p-ранг кривой y2 = x7 + ax4 + x равен 0 тогда и только тогда, когда -а/2 является корнем многочлена L1 (-a/2) = gcd (P(p-1)/2, P(p_i)/6) для p = 1 (mod 3) или L2(-a/2) = gcd P(p-1)/2, P(p-5)/6 для p = 2 (mod 3). Таким образом, для фиксированного p мы можем найти все кривые p-ранга 0 с помощью факторизации многочленов L1,L2 либо доказать, что таких кривых не существует (L1 или L2 в этом случае - константы). P(p-6)/2(-a/6)p+1 ( 0 для случая, когда p = 1 (mod 3), /P(p-5)/2 (-a/6)P+1 ( 0 0 P(p-1)/2(-a/2)p+1 0 0 P(p-1)/2(-a/2)p+1 0 0 ) P(p-1)/6(-a/6)p+1 0 ) P(p-5)/6(-a/6)p+1 Сложность метода. Построить многочлен Лежандра Pm(x) можно по известным / m X рекуррентным формулам за время O i = O(m(m+1)) операций в поле. Нахожде-i=1 ние наибольшего общего делителя для многочленов степени не больше (p - 1)/2 занимает время O((p - 1)/2) операций в поле [7, с. 325]. Факторизация многочленов L1 и L2 может быть выполнена [7, с. 390] за время O( |_p/6_|2 logp) операций в поле, учитывая, что deg L1 (p - 1)/6 и deg L2 (p - 5)/6. Проверка на максимальность занимает время O(log4 q). Предполагая, что количество проверяемых кривых небольшое, получаем в итоге эвристическую сложность в O(p2 log2 p) битовых операций. При этом нахождение всех максимальных кривых простым перебором коэффициентов занимает время O(p2 log4 p). Используя полученный метод, мы построили все максимальные кривые над полем Fp2 с параметром а = 0 (случай а = 0 изучен в [8, § 4]) для p 7151 и определили поля, над которыми таких кривых не существует. Данные по количеству максимальных кривых для p < 200 представлены в таблице. Полные данные с явными уравнениями максимальных кривых можно найти на домашней странице второго автора1. Число максимальных кривых вида y2 = x7 + ax4 + x над Fp2 , 3 < p < 200, a = 0 p Кол-во 5-29, 37-43, 53, 61, 67, 73, 89-101, 107-127, 137-163, 173-181, 193, 197 31,47, 59, 79, 83 71,103,131,167 191,199 0 2 4 6 1http://crypto-kantiana.com/semyon.novoselov/genus3/maximal_curves

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