Воображаемая гиперэллиптическая кривая

Гиперэллиптическая кривая — это особый вид алгебраической кривой . Существуют гиперэллиптические кривые каждого рода $g\geq 1$. Если род гиперэллиптической кривой равен 1, мы просто называем кривую эллиптической кривой . Следовательно, мы можем рассматривать гиперэллиптические кривые как обобщения эллиптических кривых. Существует известная групповая структура на множестве точек, лежащих на эллиптической кривой над некоторым полем. $K$, которую мы можем описать геометрически с помощью хорд и касательных. Обобщить эту структуру группы на гиперэллиптический случай непросто. Мы не можем определить один и тот же групповой закон для множества точек, лежащих на гиперэллиптической кривой, вместо этого структуру группы можно определить на так называемом якобиане гиперэллиптической кривой. Вычисления различаются в зависимости от количества точек на бесконечности. Мнимые гиперэллиптические кривые — это гиперэллиптические кривые ровно с одной точкой на бесконечности: реальные гиперэллиптические кривые имеют две точки на бесконечности.

Формальное определение

Гиперэллиптические кривые могут быть определены над полями любой характеристики . Поэтому мы рассматриваем произвольное поле $K$ и его алгебраическое замыкание ${\overline {K}}$. (Воображаемая) гиперэллиптическая кривая рода $g$ над $K$ задается уравнением вида $$C:y^{2}+h(x)y=f(x)\in K[x,y]$$где $h(x)\in K[x]$ является многочленом степени не большей, чем $g$ и $f(x)\in K[x]$ является моническим полиномом степени $2g+1$. Кроме того, мы требуем, чтобы кривая не имела особых точек . В наших условиях это означает, что нет смысла $(x,y)\in {\overline {K}}\times {\overline {K}}$ удовлетворяет обоих $y^{2}+h(x)y=f(x)$ и уравнения $2y+h(x)=0$ и $h'(x)y=f'(x)$. Это определение отличается от определения общей гиперэллиптической кривой тем, что $f$ также может иметь степень $2g+2$ в общем случае. В дальнейшем мы оставим прилагательное «мнимый» и будем просто говорить о гиперэллиптических кривых, как это часто делается в литературе. Обратите внимание, что случай $g=1$ соответствует $f$ будучи кубическим полиномом, что соответствует определению эллиптической кривой. Если мы рассматриваем кривую как лежащую в проективной плоскости $\mathbb {P} ^{2}(K)$ с координатами $(X:Y:Z)$, мы видим, что на кривой лежит особая точка, а именно точка , находящаяся на бесконечности $(0:1:0)$ обозначается $O$. Чтобы мы могли написать $C=\{(x,y)\in K^{2}|y^{2}+h(x)y=f(x)\}\cup \{O\}$.

Предположим, что точка $P=(a,b)$ не равен $O$ лежит на кривой и рассмотрим ${\overline {P}}=(a,-b-h(a))$. Как $(-b-h(a))^{2}+h(a)(-b-h(a))$ можно упростить до $b^{2}+h(a)b$, мы видим это ${\overline {P}}$ также является точкой кривой. ${\overline {P}}$ называется противоположностью $P$ и $P$ называется точкой Вейерштрасса, если $P={\overline {P}}$, то есть $h(a)=-2b$. Более того, противоположность $O$ просто определяется как ${\overline {O}}=O$.

Альтернативное определение

Определение гиперэллиптической кривой можно несколько упростить, если потребовать, чтобы характеристика $K$ не равно 2. Чтобы убедиться в этом, рассмотрим замену переменных $x\rightarrow x$ и $y\rightarrow y-{\frac {h(x)}{2}}$, что имеет смысл, если char $(K)\not =2$. При этой замене переменных перепишем $y^{2}+h(x)y=f(x)$ к ${\textstyle \left(y-{\frac {h(x)}{2}}\right)^{2}+h(x)\left(y-{\frac {h(x)}{2}}\right)=f(x)}$ которое, в свою очередь, можно переписать в $y^{2}=f(x)+{\frac {h(x)^{2}}{4}}$. Как $\deg(h)\leq g$ мы знаем это $\deg(h^{2})\leq 2g$ и, следовательно, $f(x)+{\frac {h(x)^{2}}{4}}$ является моническим полиномом степени $2g+1$. Это означает, что над полем $K$ с чарсом $(K)\not =2$ каждая гиперэллиптическая кривая рода $g$ изоморфно уравнению вида $C:y^{2}=f(x)$ где $f$ является моническим полиномом степени $2g+1$ и кривая не имеет особых точек. Заметим, что для кривых такого вида легко проверить выполнение критерия невырожденности. точка $P=(a,b)$ на кривой сингулярна тогда и только тогда, когда $b=0$ и $f'(a)=0$. Как $b=0$ и $b^{2}=f(a)$, должно быть так, что $f(a)=0$ и таким образом $a$ является кратным корнем $f$. Делаем вывод, что кривая $C:y^{2}=f(x)$ не имеет особых точек тогда и только тогда, когда $f$ не имеет кратных корней. Хотя определение гиперэллиптической кривой довольно просто, если char $(K)\not =2$, не следует забывать о полях характеристики 2, поскольку в криптографии гиперэллиптических кривых такие поля широко используются.

Пример

Рисунок 1. Пример гиперэллиптической кривой.

В качестве примера рассмотрим $C:y^{2}=f(x)$ где $f(x)=x^{5}-2x^{4}-7x^{3}+8x^{2}+12x=x(x+1)(x-3)(x+2)(x-2)$ над $\mathbb {R}$. Как $f$ имеет степень 5 и все корни различны, $C$ представляет собой кривую рода $g=2$. Его график изображен на рисунке 1.

Из этой картинки сразу становится ясно, что мы не можем использовать метод хорд и касательных для определения группового закона на множестве точек гиперэллиптической кривой. Групповой закон эллиптических кривых основан на том, что прямая, проходящая через две точки, лежащие на эллиптической кривой, имеет единственную третью точку пересечения с кривой. Обратите внимание, что это всегда верно, поскольку $O$ лежит на кривой. Из графика $C$ ясно, что это не обязательно должно выполняться для произвольной гиперэллиптической кривой. Действительно, теорема Безу утверждает, что прямая и гиперэллиптическая кривая рода 2 пересекаются в 5 точках. Итак, прямая, проходящая через две точки, лежащие на $C$ не имеет уникальной третьей точки пересечения, у него есть три другие точки пересечения.

Координатное кольцо

Координатное кольцо C над K определяется как

$K[C]=K[x,y]/(y^{2}+h(x)y-f(x)).$

Полином ​ $r(x,y)=y^{2}+h(x)y-f(x)$ является неприводимым над ${\overline {K}}$, так

${\overline {K}}[C]={\overline {K}}[x,y]/(y^{2}+h(x)y-f(x))$

является целостной областью .

Доказательство

Если бы r ( x , y ) были приводимы по ${\overline {K}}$, это будет факторизовано как ( y − u ( x ))⋅ ( y − v ( x )) для некоторых $u,v\in {\overline {K}}$. Но тогда u ( x )⋅ v ( x ) = f ( x ) поэтому он имеет степень 2 g + 1 , и u ( x ) + v ( x ) = h ( x ) поэтому он имеет степень меньше g , что невозможный.

Заметим, что любая полиномиальная функция $G(x,y)\in {\overline {K}}[C]$ можно записать однозначно как

$G(x,y)=u(x)-v(x)y$   с $u(x),v(x)\in {\overline {K}}[x]$

Норма и степень

Сопряженная полиномиальная функция G ( x , y ) знак равно u ( x ) - v ( x ) y в ${\overline {K}}[C]$ определяется как

${\overline {G}}(x,y)=u(x)+v(x)(h(x)+y).$

Нормой G является полиномиальная функция $N(G)=G{\overline {G}}$. Обратите внимание, что N ( G ) знак равно ты ( Икс ) ² + ты ( Икс ) v ( Икс ) час ( Икс ) - v ( Икс ) ² f ( x ) , поэтому N ( G ) является полиномом только от одной переменной .

Если G ( Икс , y ) знак равно ты ( Икс ) - v ( Икс ) ⋅ y , то степень G определяется как

$\deg(G)=\max[2\deg(u),2g+1+2\deg(v)].$

Характеристики:

$\deg(G)=\deg _{x}(N(G))$

$\deg(GH)=\deg(G)+\deg(H)$

$\deg(G)=\deg({\overline {G}})$

Поле функции

Функциональное поле K(C) оператора C над K является полем частных K [C] , а функциональное поле ${\overline {K}}(C)$ C ​ более ${\overline {K}}$ это поле дробей ${\overline {K}}[C]$. Элементы ${\overline {K}}(C)$ называются рациональными функциями на C .Для R — такой рациональной функции, а P — конечной точки на C , R называется определённым в P, если существуют полиномиальные функции G, H такие, что R = G/H и H(P) ≠ 0 , и тогда значение R ​ в P точке

$R(P)=G(P)/H(P).$

Для P точка на C не является конечной, т. е. P = $O$, мы определяем R(P) как:

Если $\deg(G)<\deg(H)$  затем $R(O)=0$, т.е. R имеет ноль в O. точке

Если $\deg(G)>\deg(H)$  затем $R(O)$  не определен, т. е. R имеет полюс в точке O .

Если $\deg(G)=\deg(H)$  затем $R(O)$  отношение коэффициентов G — и H. старших

Для $R\in {\overline {K}}(C)^{*}$ и $P\in C$,

Если $R(P)=0$ тогда говорят, что R имеет нуль в точке P ,

Если R не определен в P , то говорят, что R имеет полюс в P , и мы пишем $R(P)=\infty$.

Порядок полиномиальной функции в точке

Для $G=u(x)-v(x)\cdot y\in {\overline {K}}[C]^{2}$ и $P\in C$, порядок G в P определяется как:

$\mathrm {ord} _{P}(G)=r+s$ если P = ( a , b ) — конечная точка, не являющаяся Вейерштрассом. Здесь r — высшая степень числа ( x − a ) , которая делит u ( x ) и v ( x ) . Запишите G ( Икс , y ) знак равно ( Икс - а ) ^р ( ты ₀ (x) - v ₀ ( x ) y ) и если u ₀ ( a ) - v ₀ ( a ) b знак равно 0 , то s - высшая степень ( x - a ), которая делит N ( u ₀ ( Икс ) - v ₀ ( Икс ) y ) знак равно ты ₀ ² + ты ₀ v ₀ час - v ₀ ² f , в противном случае s = 0 .

$\mathrm {ord} _{P}(G)=2r+s$ если P = ( a , b ) — конечная точка Вейерштрасса с r и s , как указано выше.

$\mathrm {ord} _{P}(G)=-\deg(G)$ если П = О. ​

Дивизор и якобиан

Чтобы определить якобиан, нам сначала понадобится понятие дивизора. Рассмотрим гиперэллиптическую кривую $C$ над каким-то полем $K$. Затем мы определяем делитель $D$ быть формальной суммой баллов в $C$, то есть ${\textstyle D=\sum _{P\in C}{c_{P}[P]}}$ где $c_{P}\in \mathbb {Z}$ и более того $\{c_{P}\mid c_{P}\neq 0\}$ является конечным множеством. Это означает, что делитель представляет собой конечную формальную сумму скалярных кратных точек. Обратите внимание, что никакого упрощения $c_{P}[P]$ заданной одной точкой (как и следовало ожидать по аналогии с эллиптическими кривыми). Кроме того, мы определяем степень $D$ как ${\textstyle \deg(D)=\sum _{P\in C}{c_{P}}\in \mathbb {Z} }$. Множество всех делителей $\mathrm {Div} (C)$ кривой $C$ образует абелеву группу , в которой сложение определяется поточечно следующим образом: ${\textstyle \sum _{P\in C}{c_{P}[P]}+\sum _{P\in C}{d_{P}[P]}=\sum _{P\in C}{(c_{P}+d_{P})[P]}}$. Это легко увидеть ${\textstyle 0=\sum _{P\in C}{0[P]}}$ действует как элемент идентичности и что обратный элемент ${\textstyle \sum _{P\in C}{c_{P}[P]}}$ равно ${\textstyle \sum _{P\in C}{-c_{P}[P]}}$. Набор $\mathrm {Div} ^{0}(C)=\{D\in \mathrm {Div} (C)\mid \deg(D)=0\}$ легко проверить, что все делители степени 0 подгруппой являются $\mathrm {Div} (C)$.
Доказательство . Рассмотрите карту $\varphi :\mathrm {Div} (C)\rightarrow \mathbb {Z}$ определяется $\varphi (D)=\deg(D)$, Обратите внимание, что $\mathbb {Z}$ образует группу при обычном сложении. Затем ${\textstyle \varphi (\sum _{P\in C}{c_{P}[P]}+\sum _{P\in C}{d_{P}[P]})=\varphi (\sum _{P\in C}{(c_{P}+d_{P})[P]})=\sum _{P\in C}{c_{P}+d_{P}}=\sum _{P\in C}{c_{p}}+\sum _{P\in C}{d_{p}}=\varphi (\sum _{P\in C}{c_{P}[P]})+\varphi (\sum _{P\in C}{d_{P}[P]})}$ и, следовательно, $\varphi$ является групповым гомоморфизмом . Сейчас, $\mathrm {Div} ^{0}(C)$ является ядром этого гомоморфизма и, следовательно, является подгруппой $\mathrm {Div} (C)$.

Рассмотрим функцию $f\in {\overline {K}}(C)^{*}$, то мы можем посмотреть на формальную сумму div ${\textstyle (f)=\sum _{P\in C}{\mathrm {ord} _{P}(f)[P]}}$. Здесь $\mathrm {ord} _{P}(f)$ обозначает порядок $f$ в $P$. У нас есть такой порядок $_{P}(f)<0$ если $f$ имеет полюс порядка $-\mathrm {ord} _{P}(f)$ в $P$, $\mathrm {ord} _{P}(f)=0$ если $f$ определено и не равно нулю в $P$ и $\mathrm {ord} _{P}(f)>0$ если $f$ имеет нулевой порядок $\mathrm {ord} _{P}(f)$ в $P$. Можно показать, что $f$ имеет лишь конечное число нулей и полюсов, и, таким образом, только конечное число порядка $_{P}(f)$ ненулевые. Это означает, что div $(f)$ является делителем. Более того, как ${\textstyle \sum _{P\in C}{\mathrm {ord} _{P}(f)}=0}$, это тот случай, что $\operatorname {div} (f)$ является делителем степени 0. Такие делители, т.е. делители, происходящие от некоторой рациональной функции $f$, называются главными делителями, а совокупность всех главных делителей $\mathrm {Princ} (C)$ является подгруппой $\mathrm {Div} ^{0}(C)$.
Доказательство . Элемент идентификации ${\textstyle 0=\sum _{P\in C}{0[P]}}$ происходит от постоянной функции, которая не равна нулю. Предполагать ${\textstyle D_{1}=\sum _{P\in C}{\mathrm {ord} _{P}(f)[P]},D_{2}=\sum _{P\in C}{\mathrm {ord} _{P}(g)[P]}\in \mathrm {Princ} (C)}$ два главных делителя, происходящие из $f$ и $g$ соответственно. Затем ${\textstyle D_{1}-D_{2}=\sum _{P\in C}{(\mathrm {ord} _{P}(f)-\mathrm {ord} _{P}(g))[P]}}$ происходит из функции $f/g$, и таким образом $D_{1}-D_{2}$ также является главным делителем. Мы заключаем, что $\mathrm {Princ} (C)$ замкнута относительно сложения и инверсии, превращая ее в подгруппу.

Теперь мы можем определить факторгруппу $J(C):=\mathrm {Div} ^{0}(C)/\mathrm {Princ} (C)$ которая называется якобианом или группой Пикара . $C$. Два делителя $D_{1},D_{2}\in \mathrm {Div} ^{0}(C)$ называются эквивалентными, если они принадлежат одному и тому же элементу $J(C)$, это так тогда и только тогда, когда $D_{1}-D_{2}$ является главным делителем. Рассмотрим, например, гиперэллиптическую кривую $C:y^{2}+h(x)y=f(x)$ над полем $K$ и точка $P=(a,b)$ на $C$. Для $n\in \mathbb {Z} _{>0}$ рациональная функция $f(x)=(x-a)^{n}$ имеет нулевой порядок $n$ в обоих $P$ и ${\overline {P}}$ и у него есть полюс порядка $2n$ в $O$. Поэтому мы находим $\operatorname {div} (f)=nP+n{\overline {P}}-2nO$ и мы можем упростить это до $\operatorname {div} (f)=2nP-2nO$ если $P$ является точкой Вейерштрасса.

Пример: якобиан эллиптической кривой.

Для эллиптических кривых якобиан оказывается просто изоморфным обычной группе на множестве точек этой кривой, это, по сути, следствие теоремы Абеля-Якоби . Чтобы убедиться в этом, рассмотрим эллиптическую кривую $E$ над полем $K$. Первый шаг - связать делитель $D$ в каждую точку $P$ на кривой. В точку $P$ на $E$ мы связываем делитель $D_{P}=1[P]-1[O]$, в частности $O$ в связи с элементом идентификации $O-O=0$. Теперь мы можем напрямую связать элемент $J(E)$ в каждую точку $P$ связав $P$ в класс $D_{P}$, обозначенный $[D_{P}]$. Тогда карта $\varphi :E\to J(E)$ из группы точек на $E$ к якобиану $E$ определяется $\varphi (P)=[D_{P}]$ является групповым гомоморфизмом. В этом можно убедиться, рассмотрев три точки на $E$ добавляя к $O$, то есть мы берем $P,Q,R\in E$ с $P+Q+R=O$ или $P+Q=-R$. Теперь мы свяжем закон сложения якобиана с законом геометрической группы на эллиптических кривых. Добавление $P$ и $Q$ геометрически означает проведение прямой линии через $P$ и $Q$, эта линия пересекает кривую еще в одной точке. Затем мы определяем $P+Q$ как противоположность этому пункту. Следовательно, в случае $P+Q+R=O$ мы имеем, что эти три точки лежат на одной прямой, следовательно, существует некоторая линейная $f\in K[x,y]$ такой, что $P$, $Q$ и $R$ удовлетворить $f(x,y)=0$. Сейчас, $\varphi (P)+\varphi (Q)+\varphi (R)=[D_{P}]+[D_{Q}]+[D_{R}]=[[P]+[Q]+[R]-3[O]]$ который является элементом идентичности $J(E)$ как $[P]+[Q]+[R]-3[O]$ является делителем рациональной функции $f$ и, таким образом, это главный делитель. Мы заключаем, что $\varphi (P)+\varphi (Q)+\varphi (R)=\varphi (O)=\varphi (P+Q+R)$.

Теорема Абеля-Якоби утверждает, что дивизор ${\textstyle D=\sum _{P\in E}{c_{P}[P]}}$ является главным тогда и только тогда, когда $D$ имеет степень 0 и ${\textstyle \sum _{P\in E}{c_{P}P}=O}$ по обычному закону сложения точек кубических кривых. Как два делителя $D_{1},D_{2}\in \mathrm {Div} ^{0}(E)$ эквивалентны тогда и только тогда, когда $D_{1}-D_{2}$ является главным, заключаем, что ${\textstyle D_{1}=\sum _{P\in E}{c_{P}[P]}}$ и ${\textstyle D_{2}=\sum _{P\in E}{d_{P}[P]}}$ эквивалентны тогда и только тогда, когда ${\textstyle \sum _{P\in E}{c_{P}P}=\sum _{P\in E}{d_{P}P}}$. Теперь каждый нетривиальный дивизор степени 0 эквивалентен дивизору вида $[P]-[O]$, это означает, что мы нашли способ приписать точку $E$ в каждый класс $[D_{P}]$. А именно, чтобы $[D_{P}]=[1[P]-1[O]]$ мы приписываем точку $(P-O)+O=P$. Это отображение распространяется на нейтральный элемент 0, который отображается на $0+O=O$. Как таковая карта $\psi :J(E)\rightarrow E$ определяется $\psi ([D_{P}])=P$ является обратным $\varphi$. Так $\varphi$ на самом деле является групповым изоморфизмом , доказывая, что $E$ и $J(E)$ изоморфны.

Якобиан гиперэллиптической кривой

Общий гиперэллиптический случай немного сложнее. Рассмотрим гиперэллиптическую кривую $C:y^{2}+h(x)y=f(x)$ рода $g$ над полем $K$. Делитель $D$ из $C$ называется приведенным, если он имеет вид ${\textstyle D=\sum _{i=1}^{k}{[P_{i}]}-k[O]}$ где $k\leq g$, $P_{i}\not =O$ для всех $i=1,\dots ,k$ и $P_{i}\not ={\overline {P_{j}}}$ для $i\not =j$. Обратите внимание, что приведенный делитель всегда имеет степень 0, также возможно, что $P_{i}=P_{j}$ если $i\not =j$, но только если $P_{i}$ не является точкой Вейерштрасса. Можно доказать, что для каждого делителя $D\in \mathrm {Div} ^{0}(C)$ существует единственный приведенный делитель $D'$ такой, что $D$ эквивалентно $D'$. Следовательно, каждый класс факторгруппы $J(C)$ имеет ровно один приведенный делитель. Вместо того, чтобы смотреть на $J(C)$ таким образом, мы можем взглянуть на множество всех приведенных делителей.

Приведенные дивизоры и их представление Мамфорда

Удобный способ взглянуть на приведенные делители — через их представление Мамфорда. Дивизор в этом представлении состоит из пары многочленов $u,v\in K[x]$ такой, что $u$ моник, $\deg(v)<\deg(u)\leq g$ и $u|v^{2}+vh-f$. Каждый нетривиальный приведенный дивизор можно представить единственной парой таких многочленов. Это можно увидеть, факторизовав ${\textstyle u(x)=\prod _{i=1}^{k}{(x-x_{i})}}$ в ${\overline {K}}$ что можно сделать как например $u$ моник. Последнее условие на $u$ и $v$ тогда подразумевается, что точка $P_{i}=(x_{i},v(x_{i}))$ лежит на $C$ для каждого $i=1,...,k$. Таким образом ${\textstyle D=\sum _{i=1}^{k}{[P_{i}]}-k[O]}$ является делителем, и фактически можно показать, что он является приведенным делителем. Например, условие $\deg(u)\leq g$ гарантирует, что $k\leq g$. Это дает соответствие 1-1 между приведенными делителями и делителями в представлении Мамфорда. В качестве примера: ${\textstyle 0=\sum _{P\in C}{0[P]}}$ – уникальный приведенный делитель, принадлежащий единичному элементу $J(C)$. Его представление в Мамфорде $u(x)=1$ и $v(x)=0$. Переход между приведенными делителями и их представлением Мамфорда теперь стал простой задачей. Например, рассмотрим гиперэллиптическую кривую $C:y^{2}=x^{5}-4x^{4}-14x^{3}+36x^{2}+45x=x(x+1)(x-3)(x+3)(x-5)$ рода 2 над действительными числами. Мы можем найти следующие точки на кривой $P=(1,8)$, $Q=(3,0)$ и $R=(5,0)$. Тогда мы можем определить приведенные делители $D=[P]+[Q]-2[O]$ и $D'=[P]+[R]-2[O]$. Представление Мамфорда $D$ состоит из многочленов $u$ и $v$ с $\deg(v)<\deg(u)\leq g=2$ и мы знаем, что первые координаты $P$ и $Q$, т.е. 1 и 3, должны быть нулями $u$. Следовательно, мы имеем $u(x)=(x-1)(x-3)=x^{2}-4x+3$. Как $P=(1,v(1))$ и $Q=(3,v(3))$ должно быть так, что $v(1)=8$ и $v(3)=0$ и таким образом $v$ имеет степень 1. Существует ровно один многочлен степени 1 с этими свойствами, а именно $v(x)=-4x+12$. Таким образом, представление Мамфорда $D$ является $u(x)=x^{2}-4x+3$ и $v(x)=-4x+12$. Аналогичным образом мы можем найти представление Мамфорда. $(u',v')$ из $D'$, у нас есть $u'(x)=(x-1)(x-5)=x^{2}-6x+5$ и $v(x)=-2x+10$. Если точка $P_{i}=(x_{i},y_{i})$ появляется с кратностью n , полином v должен удовлетворять ${\textstyle \left.\left({\frac {d}{dt}}\right)^{j}\left[v(x)^{2}+v(x)h(x)-f(x)\right]\right|_{x=x_{i}}=0}$для $0\leq j\leq n_{i}-1$.

Алгоритм Кантора

Существует алгоритм , который принимает два приведенных делителя. $D_{1}$ и $D_{2}$ в их представлении Мамфорда и дает уникальный приведенный делитель $D$, опять же в представлении Мамфорда, такой, что $D$ эквивалентно $D_{1}+D_{2}$. Поскольку каждый элемент якобиана может быть представлен одним содержащимся в нем приведенным делителем, алгоритм позволяет выполнять групповую операцию над этими приведенными делителями, заданными в их представлении Мамфорда. Первоначально алгоритм был разработан Дэвидом Г. Кантором (не путать с Георгом Кантором ), что и объясняет название алгоритма. Кантор только рассмотрел дело $h(x)=0$общий случай принадлежит Коблицу . Входные данные — два уменьшенных делителя. $D_{1}=(u_{1},v_{1})$ и $D_{2}=(u_{2},v_{2})$ в их Мамфордовском представлении гиперэллиптической кривой $C:y^{2}+h(x)y=f(x)$ рода $g$ над полем $K$. Алгоритм работает следующим образом

1. Используя расширенный алгоритм Евклида, вычислите полиномы $d_{1},e_{1},e_{2}\in K[x]$ такой, что $d_{1}=\gcd(u_{1},u_{2})$ и $d_{1}=e_{1}u_{1}+e_{2}u_{2}$.
2. Снова с использованием расширенного алгоритма Евклида вычислите полиномы $d,c_{1},c_{2}\in K[x]$ с $d=\gcd(d_{1},v_{1}+v_{2}+h)$ и $d=c_{1}d_{1}+c_{2}(v_{1}+v_{2}+h)$.
3. Помещать $s_{1}=c_{1}e_{1}$, $s_{2}=c_{1}e_{2}$ и $s_{3}=c_{2}$, что дает $d=s_{1}u_{1}+s_{2}u_{2}+s_{3}(v_{1}+v_{2}+h)$.
4. Набор $u={\frac {u_{1}u_{2}}{d^{2}}}$ и $v={\frac {s_{1}u_{1}v_{2}+s_{2}u_{2}v_{1}+s_{3}(v_{1}v_{2}+f)}{d}}\mod u$.
5. Набор $u'={\frac {f-vh-v^{2}}{u}}$ и $v'=-h-v\mod u'$.
6. Если $\deg(u')>g$, затем установите $u=u'$ и $v=v'$ и повторяйте шаг 5, пока $\deg(u')\leq g$.
7. Делать $u'$ monic путем деления на его ведущий коэффициент.
8. Выход $D=(u',v')$.

Доказательство корректности алгоритма можно найти здесь.

Пример

В качестве примера рассмотрим кривую

$C:y^{2}=x^{5}-4x^{4}-14x^{3}+36x^{2}+45x=x(x+1)(x-3)(x+3)(x-5)$

рода 2 над действительными числами. Для очков

$P=(1,8)$, $Q=(3,0)$ и $R=(5,0)$

и приведенные делители

$D_{1}=[P]+[Q]-2[O]$ и $D_{2}=[P]+[R]-2[O]$

мы знаем это

$(u_{1}=x^{2}-4x+3,v_{1}=-4x+12)$, и

$(u_{2}=x^{2}-6x+5,v_{2}=-2x+10)$

являются представлениями Мамфорда $D_{1}$ и $D_{2}$ соответственно.

Мы можем вычислить их сумму, используя алгоритм Кантора. Начинаем с вычисления

$d_{1}=\gcd(u_{1},u_{2})=x-1$, и

$d_{1}=e_{1}u_{1}+e_{2}u_{2}$

для $e_{1}={\frac {1}{2}}$, и $e_{2}=-{\frac {1}{2}}$.

На втором этапе мы находим

$d=\gcd(d_{1},v_{1}+v_{2}+h)=\gcd(x-1,-6x+22)=1$ и

$1=c_{1}d_{1}+c_{2}(v_{1}+v_{2}+h)$

для $c_{1}={\frac {3}{8}}$ и $c_{2}={\frac {1}{16}}$.

Теперь мы можем вычислить

$s_{1}=c_{1}e_{1}={\frac {3}{16}}$,

$s_{2}=c_{1}e_{2}=-{\frac {3}{16}}$ и

$s_{3}=c_{2}={\frac {1}{16}}$.

Так

$u={\frac {u_{1}u_{2}}{d^{2}}}=u_{1}u_{2}=x^{4}-10x^{3}+32x^{2}-38x+15$ и

${\begin{aligned}v&={\frac {s_{1}u_{1}v_{2}+s_{2}u_{2}v_{1}+s_{3}(v_{1}v_{2}+f)}{d}}\mod u\\&={\frac {1}{16}}(x^{5}-4x^{4}-8x^{3}-10x^{2}+119x+30)\mod u\\&={\frac {1}{4}}(5x^{3}-41x^{2}+83x-15).\end{aligned}}$

Наконец мы находим

$u'={\frac {f-v^{2}}{u}}={\frac {1}{16}}(-25x^{2}+176x-15)$ и

$v'=-v\mod u'=-{\frac {72}{125}}(17x-5)$.

После создания $u'$ моник, мы приходим к выводу, что

$D=(-25x^{2}+176x-15,-{\frac {72}{125}}(17x-5))$

эквивалентно $D_{1}+D_{2}$.

Подробнее об алгоритме Кантора

Представленный здесь алгоритм Кантора имеет общий вид: он справедлив для гиперэллиптических кривых любого рода и над любым полем. Однако алгоритм не очень эффективен. Например, для этого требуется использование расширенного алгоритма Евклида. Если мы зафиксируем род кривой или характеристику поля (или и то, и другое), мы сможем сделать алгоритм более эффективным. Для некоторых особых случаев мы даже получаем явные формулы сложения и удвоения, которые работают очень быстро. Например, существуют явные формулы для гиперэллиптических кривых рода 2 и род 3.

Для гиперэллиптических кривых также довольно легко представить себе добавление двух приведенных делителей. Предположим, что у нас есть гиперэллиптическая кривая рода 2 над действительными числами вида

$C:y^{2}=f(x)$

и два приведенных делителя

$D_{1}=[P]+[Q]-2[O]$ и

$D_{2}=[R]+[S]-2[O]$.

Предположим, что

$P,Q\not ={\overline {R}},{\overline {S}}$,

этот случай следует рассматривать отдельно. Существует ровно 1 кубический многочлен

$a(x)=a_{0}x^{3}+a_{1}x^{2}+a_{2}x+a_{3}$

пройдя через четыре точки

$P,Q,R,S$.

Обратите внимание, что возможно, что, например, $P=Q$, следовательно, мы должны принять во внимание кратности . положить $y=a(x)$ мы находим это

$y^{2}=f(x)=a^{2}(x)$

и, следовательно,

$f(x)-a^{2}(x)=0$.

Как $f(x)-a^{2}(x)$ является полиномом шестой степени, то имеем $f(x)-a^{2}(x)$ имеет шесть нулей и, следовательно, $a(x)$ кроме того имеет $P,Q,R,S$ еще две точки пересечения с $C$, позвони им $T$ и $U$, с $T\not ={\overline {U}}$. Сейчас, $P,Q,R,S,T,U$ являются точками пересечения $C$ с алгебраической кривой. Таким образом, мы знаем, что делитель

$D=[P]+[Q]+[R]+[S]+[T]+[U]-6[O]$

является главным, что означает, что делитель

$[P]+[Q]+[R]+[S]-4[O]$

эквивалентен делителю

$-([T]+[U]-2[O])$.

Кроме того, делитель

$[P]+[{\overline {P}}]-2[O]$

является главным для каждой точки $P=(a,b)$ на $C$ как это следует из рациональной функции $b(x)=x-a$. Это дает то, что $-([P]-[O])$ и $[{\overline {P}}]-[O]$ эквивалентны. Объединив эти два свойства, мы приходим к выводу, что

$D_{1}+D_{2}=([P]+[Q]-2[O])+([R]+[S]-2[O])$

эквивалентно приведенному делителю

$[{\overline {T}}]+[{\overline {U}}]-2[O]$.

На рисунке это выглядит как на рисунке 2. Можно явно вычислить коэффициенты $a(x)$, таким образом мы можем прийти к явным формулам сложения двух приведенных делителей.

Рисунок 2: Пример сложения двух элементов якобиана