кривая Монтгомери

В математике кривая Монтгомери — это форма эллиптической кривой, введенная Питером Л. Монтгомери в 1987 году ^[1] , отличная от обычной формы Вейерштрасса . Она используется для определенных вычислений, в частности, в различных криптографических приложениях.

Кривая Монтгомери над полем K определяется уравнением

${\displaystyle M_{A,B}:By^{2}=x^{3}+Ax^{2}+x}$

для некоторых A , B ∈ K и при этом B ( A ² − 4) ≠ 0 .

Обычно эта кривая рассматривается над конечным полем K (например, над конечным полем из q элементов , K = F _q ) с характеристикой , отличной от 2, и с A ≠ ±2 и B ≠ 0 , но они также рассматриваются над рациональными числами с теми же ограничениями для A и B .

Между точками эллиптической кривой можно выполнять некоторые «операции» : «сложение» двух точек заключается в нахождении третьей такой, что ; «удвоение» точки заключается в вычислении (для получения дополнительной информации об операциях см. Групповой закон ) и ниже.${\displaystyle P,Q}$${\displaystyle R}$${\displaystyle R=P+Q}$${\displaystyle [2]P=P+P}$

Точку на эллиптической кривой в форме Монтгомери можно представить в координатах Монтгомери , где — проективные координаты и для .${\displaystyle P=(x,y)}$${\displaystyle By^{2}=x^{3}+Ax^{2}+x}$${\displaystyle P=(X:Z)}$${\displaystyle P=(X:Z)}$${\displaystyle x=X/Z}$${\displaystyle Z\neq 0}$

Обратите внимание, что этот вид представления для точки теряет информацию: действительно, в этом случае нет различия между аффинными точками и поскольку они обе заданы точкой . Однако с помощью этого представления можно получить кратные точек, то есть, учитывая , вычислить .${\displaystyle (x,y)}$${\displaystyle (x,-y)}$${\displaystyle (X:Z)}$${\displaystyle P=(X:Z)}$${\displaystyle [n]P = (X_ {n}:Z_ {n})}$

Теперь рассмотрим две точки и : их сумма дается точкой, координаты которой :${\displaystyle P_{n}=[n]P=(X_{n}:Z_{n})}$${\displaystyle P_{м}=[м]P=(X_{м}:Z_{м})}$${\displaystyle P_{m+n}=P_{m}+P_{n}=(X_{m+n}:Z_{m+n})}$

${\displaystyle X_{m+n}=Z_{mn}((X_{m}-Z_{m})(X_{n}+Z_{n})+(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}}$

${\displaystyle Z_{m+n}=X_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})-(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}}$

Если , то операция становится «удвоением»; координаты задаются следующими уравнениями:${\displaystyle m=n}$${\displaystyle [2]P_{n}=P_{n}+P_{n}=P_{2n}=(X_{2n}:Z_{2n})}$

${\displaystyle 4X_{n}Z_{n}=(X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2}}$

${\displaystyle X_{2n}=(X_{n}+Z_{n})^{2}(X_{n}-Z_{n})^{2}}$

${\displaystyle Z_{2n}=(4X_{n}Z_{n})((X_{n}-Z_{n})^{2}+((A+2)/4)(4X_{n}Z_{n}))}$

Первая операция, рассмотренная выше ( сложение ), имеет временные затраты 3 M +2 S , где M обозначает умножение двух общих элементов поля, на котором определена эллиптическая кривая, а S обозначает возведение в квадрат общего элемента поля.

Вторая операция (удвоение) имеет временные затраты 2 M  + 2 S  + 1 D , где D обозначает умножение общего элемента на константу ; обратите внимание, что константа равна , поэтому ее можно выбрать так, чтобы получить небольшое  D .${\displaystyle (A+2)/4}$${\displaystyle A}$

Следующий алгоритм представляет собой удвоение точки на эллиптической кривой в форме Монтгомери.${\displaystyle P_{1}=(X_{1}:Z_{1})}$

Предполагается, что . Стоимость этой реализации составляет 1M + 2S + 1*A + 3add + 1*4. Здесь M обозначает требуемые умножения, S обозначает возведения в квадрат, а a относится к умножению на A.${\displaystyle Z_{1}=1}$

${\displaystyle XX_{1}=X_{1}^{2}\,}$

${\displaystyle X_{2}=(XX_{1}-1)^{2}\,}$

${\displaystyle Z_{2}=4X_{1}(XX_{1}+aX_{1}+1)\,}$

Пусть будет точкой на кривой . В координатах , причем , .${\displaystyle P_{1}=(2,{\sqrt {3}})}$${\displaystyle 2y^{2}=x^{3}-x^{2}+x}$${\displaystyle (X_{1}:Z_{1})}$${\displaystyle x_{1}=X_{1}/Z_{1}}$${\displaystyle P_{1}=(2:1)}$

Затем:

${\displaystyle XX_{1}=X_{1}^{2}=4\,}$

${\displaystyle X_{2}=(XX_{1}-1)^{2}=9\,}$

${\displaystyle Z_{2}=4X_{1}(XX_{1}+AX_{1}+1)=24\,}$

Результатом является точка такая, что .${\displaystyle P_{2}=(X_{2}:Z_{2})=(9:24)}$${\displaystyle P_{2}=2P_{1}}$

Даны две точки на кривой Монтгомери в аффинных координатах, точка представляет геометрически третью точку пересечения между и прямой, проходящей через и . Координаты можно найти следующим образом:${\displaystyle P_{1}=(x_{1},y_{1})}$${\displaystyle P_{2}=(x_{2},y_{2})}$${\displaystyle M_{A,B}}$${\displaystyle P_{3}=P_{1}+P_{2}}$${\displaystyle M_{A,B}}$${\displaystyle P_{1}}$${\displaystyle P_{2}}$${\displaystyle (x_{3},y_{3})}$${\displaystyle P_{3}}$

1) рассмотрим общую прямую в аффинной плоскости и пропустим ее через и (наложим условие), таким образом, получим и ;${\displaystyle ~y=lx+m}$${\displaystyle P_{1}}$${\displaystyle P_{2}}$${\displaystyle l={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}$${\displaystyle m=y_{1}-\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)x_{1}}$

2) пересекаем линию с кривой , заменяя переменную в уравнении кривой на ; получаем следующее уравнение третьей степени :${\displaystyle M_{A,B}}$${\displaystyle ~y}$${\displaystyle ~y=lx+m}$

${\displaystyle x^{3}+(A-Bl^{2})x^{2}+(1-2Blm)x-Bm^{2}=0.}$

Как уже было отмечено ранее, это уравнение имеет три решения, которые соответствуют координатам , и . В частности, это уравнение можно переписать как:${\displaystyle ~x}$${\displaystyle P_{1}}$${\displaystyle P_{2}}$${\displaystyle P_{3}}$

${\displaystyle (x-x_{1})(x-x_{2})(x-x_{3})=0}$

3) Сравнивая коэффициенты двух одинаковых уравнений, приведенных выше, в частности коэффициенты при членах второй степени, получаем:

${\displaystyle -x_{1}-x_{2}-x_{3}=A-Bl^{2}}$.

Итак, можно записать в терминах , , , , как:${\displaystyle x_{3}}$${\displaystyle x_{1}}$${\displaystyle y_{1}}$${\displaystyle x_{2}}$${\displaystyle y_{2}}$

${\displaystyle x_{3}=B\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)^{2}-A-x_{1}-x_{2}.}$

4) Для нахождения координаты точки достаточно подставить значение в строку . Обратите внимание, что это не даст точку напрямую. Действительно, с помощью этого метода можно найти координаты точки такие, что , но если нужна результирующая точка суммы между и , то необходимо заметить, что: тогда и только тогда, когда . Итак, имея точку , необходимо найти , но это можно легко сделать, изменив знак на координату . Другими словами, необходимо будет изменить знак координаты, полученной подстановкой значения в уравнение строки.${\displaystyle ~y}$${\displaystyle P_{3}}$${\displaystyle x_{3}}$${\displaystyle ~y=lx+m}$${\displaystyle P_{3}}$${\displaystyle ~R}$${\displaystyle R+P_{1}+P_{2}=P_{\infty }}$${\displaystyle P_{1}}$${\displaystyle P_{2}}$${\displaystyle R+P_{1}+P_{2}=P_{\infty }}$${\displaystyle -R=P_{1}+P_{2}}$${\displaystyle ~R}$${\displaystyle ~-R}$${\displaystyle ~y}$${\displaystyle ~R}$${\displaystyle ~y}$${\displaystyle x_{3}}$

Подводя итог, координаты точки :${\displaystyle P_{3}=(x_{3},y_{3})}$${\displaystyle P_{3}=P_{1}+P_{2}}$

${\displaystyle x_{3}={\frac {B(y_{2}-y_{1})^{2}}{(x_{2}-x_{1})^{2}}}-A-x_{1}-x_{2}}$

${\displaystyle y_{3}={\frac {(2x_{1}+x_{2}+A)(y_{2}-y_{1})}{x_{2}-x_{1}}}-{\frac {B(y_{2}-y_{1})^{3}}{(x_{2}-x_{1})^{3}}}-y_{1}}$

Если задана точка на кривой Монтгомери , то геометрически эта точка представляет собой третью точку пересечения кривой и касательной к ; поэтому, чтобы найти координаты точки, достаточно следовать тому же методу, который приведен в формуле сложения; однако в этом случае линия y  =  lx  +  m должна быть касательной к кривой в точке , поэтому, если при${\displaystyle P_{1}}$${\displaystyle M_{A,B}}$${\displaystyle [2]P_{1}}$${\displaystyle P_{1}}$${\displaystyle P_{3}=2P_{1}}$${\displaystyle P_{1}}$${\displaystyle M_{A,B}:f(x,y)=0}$

${\displaystyle f(x,y)=x^{3}+Ax^{2}+x-By^{2},}$

тогда значение l , представляющее наклон линии, определяется по формуле:

${\displaystyle l=-\left.{\frac {\partial f}{\partial x}}\right/{\frac {\partial f}{\partial y}}}$

по теореме о неявной функции .

Итак , координаты точки :${\displaystyle l={\frac {3x_{1}^{2}+2Ax_{1}+1}{2By_{1}}}}$${\displaystyle P_{3}}$${\displaystyle P_{3}=2P_{1}}$

${\displaystyle {\begin{aligned}x_{3}&=Bl^{2}-A-x_{1}-x_{1}={\frac {B(3x_{1}^{2}+2Ax_{1}+1)^{2}}{(2By_{1})^{2}}}-A-x_{1}-x_{1}\\y_{3}&=(2x_{1}+x_{1}+A)l-Bl^{3}-y_{1}\\&={\frac {(2x_{1}+x_{1}+A)(3{x_{1}}^{2}+2Ax_{1}+1)}{2By_{1}}}-{\frac {B(3{x_{1}}^{2}+2Ax_{1}+1)^{3}}{(2By_{1})^{3}}}-y_{1}.\end{aligned}}}$

Пусть — поле с характеристикой, отличной от 2.${\displaystyle K}$

Пусть — эллиптическая кривая в форме Монтгомери:${\displaystyle M_{A,B}}$

${\displaystyle M_{A,B}:Bv^{2}=u^{3}+Au^{2}+u}$

с ,${\displaystyle A\in K\smallsetminus \{-2,2\}}$${\displaystyle B\in K\smallsetminus \{0\}}$

и пусть будет эллиптической кривой в скрученной форме Эдвардса:${\displaystyle E_{a,d}}$

${\displaystyle E_{a,d}\ :\ ax^{2}+y^{2}=1+dx^{2}y^{2},\,}$

с${\displaystyle a,d\in K\smallsetminus \{0\},\quad a\neq d.}$

Следующая теорема показывает бирациональную эквивалентность между кривыми Монтгомери и скрученной кривой Эдвардса : ^[2]

Теорема (i) Каждая скрученная кривая Эдвардса бирационально эквивалентна кривой Монтгомери над . В частности, скрученная кривая Эдвардса бирационально эквивалентна кривой Монтгомери, где , и .${\displaystyle K}$${\displaystyle E_{a,d}}$${\displaystyle M_{A,B}}$${\displaystyle A={\frac {2(a+d)}{a-d}}}$${\displaystyle B={\frac {4}{a-d}}}$

Карта :​

${\displaystyle \psi \,:\,E_{a,d}\rightarrow M_{A,B}}$

${\displaystyle (x,y)\mapsto (u,v)=\left({\frac {1+y}{1-y}},{\frac {1+y}{(1-y)x}}\right)}$

является бирациональной эквивалентностью из в , с обратным:${\displaystyle E_{a,d}}$${\displaystyle M_{A,B}}$

${\displaystyle \psi ^{-1}}$:${\displaystyle M_{A,B}\rightarrow E_{a,d}}$

${\displaystyle (u,v)\mapsto (x,y)=\left({\frac {u}{v}},{\frac {u-1}{u+1}}\right),a={\frac {A+2}{B}},d={\frac {A-2}{B}}}$

Обратите внимание, что эта эквивалентность между двумя кривыми не действительна везде: действительно , отображение не определено в точках или .${\displaystyle \psi }$${\displaystyle v=0}$${\displaystyle u+1=0}$${\displaystyle M_{A,B}}$

Любую эллиптическую кривую можно записать в форме Вейерштрасса. В частности, эллиптическую кривую в форме Монтгомери

${\displaystyle M_{A,B}}$: ${\displaystyle By^{2}=x^{3}+Ax^{2}+x,}$

можно преобразовать следующим образом: разделить каждый член уравнения на и заменить переменные x и y на и соответственно, чтобы получить уравнение${\displaystyle M_{A,B}}$${\displaystyle B^{3}}$${\displaystyle u={\frac {x}{B}}}$${\displaystyle v={\frac {y}{B}}}$

${\displaystyle v^{2}=u^{3}+{\frac {A}{B}}u^{2}+{\frac {1}{B^{2}}}u.}$

Чтобы получить отсюда короткую форму Вейерштрасса, достаточно заменить u на переменную :${\displaystyle t-{\frac {A}{3B}}}$

${\displaystyle v^{2}=\left(t-{\frac {A}{3B}}\right)^{3}+{\frac {A}{B}}\left(t-{\frac {A}{3B}}\right)^{2}+{\frac {1}{B^{2}}}\left(t-{\frac {A}{3B}}\right);}$

Наконец, это дает уравнение:

${\displaystyle v^{2}=t^{3}+\left({\frac {3-A^{2}}{3B^{2}}}\right)t+\left({\frac {2A^{3}-9A}{27B^{3}}}\right).}$

Следовательно, отображение задается как

${\displaystyle \psi }$:${\displaystyle M_{A,B}\rightarrow E_{a,b}}$

${\displaystyle (x,y)\mapsto (t,v)=\left({\frac {x}{B}}+{\frac {A}{3B}},{\frac {y}{B}}\right),a={\frac {3-A^{2}}{3B^{2}}},b={\frac {2A^{3}-9A}{27B^{3}}}}$

Напротив, эллиптическая кривая над базовым полем в форме Вейерштрасса${\displaystyle \mathbb {F} }$

${\displaystyle E_{a,b}}$:${\displaystyle v^{2}=t^{3}+at+b}$

может быть преобразована в форму Монтгомери тогда и только тогда, когда имеет порядок, делящийся на четыре, и удовлетворяет следующим условиям: ^[3]${\displaystyle E_{a,b}}$

1. ${\displaystyle z^{3}+az+b=0}$имеет по крайней мере один корень ; и${\displaystyle \alpha \in \mathbb {F} }$
2. ${\displaystyle 3\alpha ^{2}+a}$является квадратичным вычетом в .${\displaystyle \mathbb {F} }$

Когда эти условия выполнены, то для нас имеет место отображение${\displaystyle s=({\sqrt {3\alpha ^{2}+a}})^{-1}}$

${\displaystyle \psi ^{-1}}$:${\displaystyle E_{a,b}\rightarrow M_{A,B}}$

${\displaystyle (t,v)\mapsto (x,y)=\left(s(t-\alpha ),sv\right),A=3\alpha s,B=s}$.

• Кривая25519
• Таблица стоимости операций на эллиптических кривых – информация о времени выполнения, необходимом в конкретном случае

• Питер Л. Монтгомери (1987). «Ускорение методов Полларда и эллиптической кривой факторизации». Математика вычислений . 48 (177): 243–264. doi : 10.2307/2007888 . JSTOR  2007888.
• Дэниел Дж. Бернштейн , Питер Биркнер, Марк Джой, Таня Ланге и Кристиан Питерс (2008). «Искаженные кривые Эдвардса». Прогресс в криптологии – AFRICACRYPT 2008 . Конспекты лекций по информатике. Том. 5023. Шпрингер-Верлаг Берлин Гейдельберг. стр. 389–405. дои : 10.1007/978-3-540-68164-9_26. ISBN 978-3-540-68159-5.{{cite book}}: CS1 maint: multiple names: authors list (link)
• Воутер Кастрик; Стивен Гэлбрейт; Реза Резаиан Фарашахи (2008). «Эффективная арифметика на эллиптических кривых с использованием смешанного представления Эдвардса-Монтгомери» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )

• Кривые рода 1 над полями с большими характеристиками