Подсчет числа точек на гиперэллиптических кривых с геометрически разложимым якобианом

Первая глава посвящена описанию предварительных сведений и методов, кото­
рые используются в последующих главах для получения результатов. Пусть C ––
гиперэллиптическая кривая рода g над конечным полем Fq характеристики p, за­
даваемая уравнением y 2 = f (x). Для получения разложения якобиана кривой в
работе использовались следующие две теоремы и основанные на них методы.

Теорема (Клайман­Серр). Если существует неконстантный морфизм кри­
вых C → D, определённый над Fq , то LD,q (T ) делит LC,q (T ).

Данная теорема позволяет получить разложение якобиана в случае нали­
чия морфизма кривых. Так как по теореме Тэйта [21] многочлен LD,q (T ) де­
лит LC,q (T ) тогда и только тогда, когда JacC ∼ JacD ×A. В случае если группа
авторфизмов кривой C нетривиальна, т. е. помимо гиперэллиптической инволю­
ции есть другие автоморфизмы, то может применяться следующая теорема.

Теорема (Кани­Роузен). Пусть G ≤ Aut(C) –– (конечная) подгруппа, для кото­
рой выполняется G = H1 ∪ . . . ∪ Ht , где подгруппы Hi ≤ G удовлетворяют
условию Hi ∩ Hj = 1, i 6= j. Тогда имеет место изогения
g
C × JacC/G ∼ JacC/H1 × . . . × JacC/Ht ,
h1ht
Jact−1

где g = |G|, hi = |Hi | и Jacn обозначает Jacn = Jac × . . . × Jac (n­раз).

Помимо разложения якобиана для подсчёта точек на кривой и получения
списка всех возможных характеристических многочленов кривой по модулю p
мы используем метод подсчёта точек на основе оператора Картье. Обозначим
p−1
через ci –– коэффициенты при xi в f (x) 2 . Тогда матрицей Картье­Манина на­
зывается матрица W = (cip−j )i,j , для 1 ≤ i,j ≤ g, а матрица H = W t называется
n−1i
матрицей Хассе­Витта. Введём матрицу Wp = H · H (p) · … · H (p ) , где H (p )
i
обозначает возведение каждого элемента матрицы H в степень p . Тогда харак­
теристический многочлен χC,q (T ) кривой C связан с матрицей Wp формулой
Манина [47––49]: χC,q (T ) ≡ (−1)g T g det(Wp − T I) (mod p).
Вторая глава содержит в себе основные общие теоретические результаты,
состоит из 4­х подразделов.
Первый подраздел посвящён задаче восстановления характеристическо­
го многочлена эндоморфизма Фробениуса χA,q (T ) абелева многообразия A по
известному многочлену χA,qk (T ). Предлагаемый метод решения задачи пред­
ставляет собой обобщение метода из работы Сато [37] для якобианов кривых
вида y 2 = x5 + ax3 + bx на случай любых абелевых многообразий. Он пред­
ставляет собой спуск по относительным расширениям конечных полей, исполь­
зуя разложение k = k1 · . . . · km и соответствующую башню конечных по­
лей Fq ⊂ Fqk1 ⊂ Fqk1 k2 ⊂ . . . ⊂ Fqk с последовательным вычислением цепочки
характеристических многочленов χA,qk 7→ . . . 7→ χA,qk1 k2 7→ χA,qk1 7→ χA,q . В
худшем случае при простом k метод ведёт к следующей оценке сложности реше­
ния задачи.
Теорема 1. Пусть A –– абелево многообразие размерности g над конечным
полем Fq . Вычисление характеристического многочлена χA,q (T ) по заданно­
му χA,qk (T ) занимает эвристическое вероятностное время

Oe 22g g2 kϵ log2 q + Cgw (g, β) + R + 22g g log2 (gk)ϵ′ S log q

битовых операций, где ϵ = 3.545, ϵ′ = 1.766, R –– сложность выбора случайной
точки, S –– сложность группового закона, Cgw –– сложность выполнения кон­
вертации базиса Грёбнера из grevlex порядка в lex для системы из многочленов
2
2g−1
степени β = 2 (gk)2+ gkот g –– неизвестных. В случае, если соответ­
ствующая система уравнений имеет размерность 0, полагаем Cgw = 0.
Получение точных оценок для Cgw в случае положительной размерно­
сти является открытой проблемой теории сложности. Однако, в наших вычис­
лениях такой случай не встречался. Более точные оценки доказываем для случа­
ев g = 3, k = 2r 3s и g = 4, k = 2s , используя вместо базисов Грёбнера метод
результантов.
Теорема 2. Пусть A –– абелево многообразие размерности 3 над конечным по­
лем Fq . Тогда задача нахождения характеристического многочлена χA,q (T ) по
известному χA,qk (T ) для k = 2r 3s , где r, s ≥ 0, имеет эвристическую вероят­
ностную сложность O(2 e 2r−4 32s−4 log2 q(R+2r−1 3s+1 S log q)) битовых опера­
ций. Здесь R –– сложность выбора случайной точки из A(Fq2r−1 3s ), а S –– слож­
ность группового закона.
Теорема 3. Пусть A –– абелево многообразие размерности 4 над конечным по­
лем Fq . Тогда задача нахождения характеристического многочлена χA,q (T ) по
известному χA,qk (T ), где k = 2r , имеет эвристическую вероятностную слож­
e 2r log2 q(R + 2r+1 S log q)) битовых операций. Здесь R –– сложность
ность O(2
выбора случайной точки из A(Fq2r−1 ), а S –– сложность группового закона.
Так как для якобианов гиперэллиптических кривых задача выбора случай­
ной точки (в данном случае класса дивизоров) и групповой закон имеют поли­
номиальную сложность от log q, получаем следующие оценки.
Следствие 3.1. Пусть C –– гиперэллиптическая кривая рода 3 над конечным
полем Fq . Тогда задача нахождения характеристического многочлена χC,q (T )
по известному χC,qk (T ), где k = 2r 3s , имеет эвристическую вероятностную
сложность O(2e 4r 34s log4 q) битовых операций.

Следствие 3.2. Пусть C –– гиперэллиптическая кривая рода 4 над конечным по­
лем Fq . Тогда задача нахождения характеристического многочлена χC,q (T ) по
известному χC,qk (T ), где k = 2r , имеет эвристическую вероятностную слож­
e 4r log4 q) битовых операций.
ность O(2
Применяя полученные оценки сложности нахождения χA,q (T ) по извест­
ному χA,qk (T ) к геометрически приводимым абелевым многообразиям, получа­
ем во втором подразделе второй главы следующие теоремы.

Теорема 4. Пусть A –– абелево многообразие размерности 3 над конечным по­
лем Fq и k = 2r 3s . Тогда характеристический многочлен χA,q (T ), а значит,
и #A(Fq ), может быть найден за эвристическое вероятностное время (в би­
товых операциях):
e 4 log4 q + OD )), если A(Fqk ) ∼ E1 × E2 × E3 .
1. O(k
e ∆ log∆ q + OD )), если A(Fqk ) ∼ E1 × A2 .
2. O(k
e 8 log8 q + OD )), если A(Fqk ) ∼ E1 × A2 и A2 –– якобиан гиперэллип­
3. O(k
тической кривой рода 2.
Здесь OD = O(2 e 2r 32s log2 q(R + 2r 3s S log q)) –– сложность спуска. В случае,
если A –– якобиан гиперэллиптической кривой рода 3, то имеем:
e 4 log4 q), если A(Fqk ) ∼ E1 × E2 × E3 .
1. O(k
e ∆ log∆ q)), если A(Fqk ) ∼ E1 × A2 .
2. O(k
e 8 log8 q), если A(Fqk ) ∼ E1 × A2 и A2 –– якобиан гиперэллиптиче­
3. O(k
ской кривой рода 2.
Здесь ∆ –– экспонента из алгоритма Пилэ для абелевой поверхности A2 , R ––
сложность выбора случайной точки на A, S –– сложность группового закона
на A.

Теорема 5. Пусть A –– абелево многообразие размерности 4 над конечным по­
лем Fq такое, что A ∼ A1 × . . . × Am над Fqk , где k = 2r и A1 , . . . , Am ––
абелевы многообразия размерности g1 , . . . , gm . Тогда характеристический мно­
гочлен χA,q (T ), а значит, и число точек на A, может быть найден за эвристи­
ческое вероятностное время

e
O(logq + . . . + log∆(gm ) q k + OD )
∆(g1 ) k

битовых операций. Здесь OD = 22r log2 q(R + 2r+1 S log q), ∆(gi ) –– экспонен­
ты из алгоритма Пилэ для абелевых многообразий Ai , R –– сложность выбора
случайной точки на A(Fq2r−1 ), S –– сложность группового закона.

Третий подраздел второй главы посвящен исследованию специального
класса гиперэллиптических кривых с геометрически разложимым якобианом,
задаваемых уравнением C : y 2 = x2g+1 + axg+1 + bx. Данные кривые име­
ют длинную историю изучения, которую можно проследить от работ Лежандра.
Поэтому сначала даётся обзор известных результатов по данному классу кри­
вых. Затем мы находим разбиение якобиана данной кривой, на основе частич­
ных результатов из [33; 41; 42] и метода Кани­Роузена. Получаем, что JacC ∼
JacC/⟨σ⟩ × JacC/⟨σι⟩ , где уравнения фактор­кривых по автоморфизмам приво­
дим в следующей теореме.
Теорема 6. Пусть C : y 2 = x2g+1 +axg+1 +αg x –– это гиперэллиптическая кри­
вая рода g, определенная над конечным полем Fq , и ι –– гиперэллиптическая ин­
волюция. Тогда кривая C имеет негиперэллиптическую инволюцию σ : (x, y) 7→
g+1
( αx , y αxg+1
) и уравнения фактор­кривых кривой X по модулю инволюций σ и ισ
следующие.
1. Если род g нечётный, то C/ hσi : y 2 = Dg (x,α) + a и C/ hισi : y 2 =
(x2 − 4α)(Dg (x,α) + a).√
2. Если род g чётный,
√то C/ hσi : y 2 = (x+2 α)(Dg (x, α)+a) и C/ hισi :
y 2 = (x − 2 α)(Dg (x, α) + a).
Здесь Dg (x, α) –– многочлен Диксона степени g.
√
Соответственно, якобиан кривой C√раскладывается над полем Fq [ g b] в
случае нечётного рода и над полем Fq [ 2g b] в случае чётного рода. Таким об­
разом, мы знаем точную степень расширения, над которым имеет место раз­
ложение якобиана, и явные уравнения кривых в разложении. Поэтому мы мо­
жем подсчитать характеристические многочлены кривых в разложении и вос­
становить характеристический многочлен кривой C по методам из предыду­
щих подразделовQ или по следующей формуле [50, с. 195] для L­многочленов:
LC,qk (T k ) = ζ k =1 LC,q (ζT ).
Соответствующий алгоритм для рода 2 с разложениями якобиана, полу­
ченными другим методом, представлен в работах [37; 39]. Наш алгоритм и раз­
ложение якобиана работает для любого рода.
Другой метод для подсчёта точек на данных кривых, представленный в гла­
ве 2, основан на операторе Картье и его матрицах действия. Можно показать,
что матрица Картье­Манина кривой C с параметром b = 1 состоит из много­
членов Лежандра. Из свойств многочленов Лежандра следует, что данная мат­
рица –– центросимметрична. Кроме того, в работах [51; 52] было замечено, что
данная матрица является ещё и мономиальной (обобщенной перестановочной)
при p ∤ g. Данные свойства также можно частично распространить и на матри­
цу Картье­Манина кривой C в случае b 6= 1. Перечисленные свойства позволя­
ют перебрать все характеристические многочлены кривой C, используя формулу
Манина и разложение на циклы перестановки, которая соответствует нашей мо­
номиальной матрице. В итоге получается список из g возможных многочленов,
выраженных через многочлены Лежандра.
На основе данного метода нами были составлены списки характеристиче­
ских многочленов (mod p) для родов 1 − 7. Но их можно получить для любого
рода. Заметим, что для эллиптических кривых известны [53––55] сопоставления
следов Фробениуса с многочленами Лежандра P p−1 , P p−1 , P p−1 , P p−1 . Поэтому
2346
данные многочлены в полученных нами списках характеристических многочле­
нов можно рассчитать за время O(log e4
q) по эффективному алгоритму Схоофа­
Элкиса­Аткина, что даёт нам эффективный алгоритм подсчёта точек для рода 3.
В остальных случаях соответствие многочленов Лежандра коэффициентам ха­
рактеристического многочлена кривых рода 2 и выше можно получить из раз­
ложения якобиана кривой C, которое мы используем для получения следующих
утверждений в четвёртом подразделе второй главы.
Следствие 6.1. Пусть g –– чётное целое. Для матриц Картье­Манина W ′ =
′
(wi,jf ′ = (w
), W′
ei,j ) гиперэллиптических кривых X2′ : y 2 = (x + 2)(Dg (x) + c) и
e ′
X2 : y = (x − 2)(Dg (x) + c) над конечным полем Fq выполняется:
′
1. wi,j = P ip−j − p−1 (− 2c ) − P (g−i)p−j − p−1 (− 2c );
g2gg2g
′
ei,j
2. w= P ip−j − p−1 (− 2c ) + P (g−i)p−j − p−1 (− 2c ).
g2gg2g
Здесь 1 ≤ i,j ≤ g2 и Pm –– многочлен Лежандра степени m, Dg (x) = Dg (x, 1) ––
многочлен Диксона степени g. При этом в случае m 6∈ Z полагаем Pm = 0.

Следствие 6.2. Пусть g –– нечётное целое. Для матриц Картье­Манина W ′ =
′
(wi,jf ′ = (w
), W′
ei,j ) гиперэллиптических кривых X1′ : y 2 = Dg (x) + c и X3′ : y 2 =
(x − 4)(Dg (x) + c) над конечным полем Fq выполняется:
′
1. wi,j = P ip−j − p−1 (− 2c ) − P (g−i)p−j − p−1 (− 2c ), 1 ≤ i, j ≤ g−1
2 ;
( g2gg2g

P ip−j − p−1 (− 2c ) + P (g−i)p−j − p−1 (− 2c ), 1 ≤ i, j ≤ g−12 ;
′
2. wei,j =g2gg2g
c
P p−1 (− 2 ),g+1
i = 2 или j = g+1 2 .
Здесь Pm –– многочлен Лежандра степени m, Dg (x) = Dg (x, 1) –– многочлен
Диксона степени g. При этом в случае m 6∈ Z полагаем Pm = 0.

Изложенные во второй главе результаты опубликованы в [A1; A2; A5; A6].
Третья глава посвящена специализации общих алгоритмов и методов из
главы 2 к случаю кривых y 2 = x7 +ax4 +bx рода 3 и кривых y 2 = x9 +ax5 +bx ро­
да 4, что позволило получить более точные результаты. В частности, явные фор­
мулы для коэффициентов характеристического многочлена в случае рода 3 вме­
сто алгоритма на основе разложения якобиана. Доказано также, что сложность
e
подсчёта точек на данных кривых равна O(log 4e
q) и O(log 8
q) соответственно.
Изложенные в третьей главе результаты опубликованы в [A1; A2; A7].
Четвертая глава посвящена применению полученных результатов в крип­
тографии и других областях. Представлены алгоритмы для генерации кривых с
заданным числом точек в якобиане. Получены сравнения для многочленов Ле­
жандра. Показано, что полученные результаты делают гиперэллиптические кри­
вые y 2 = x7 + ax4 + bx и y 2 = x9 + ax5 + bx слабыми для использования в
криптографических конструкциях на группах с неизвестным порядком.
В заключении приведены основные результаты работы.