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

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

Определение [ править ]

Кривая Монтгомери уравнения ${\ textstyle {\ frac {1} {4}} y ^ {2} = x ^ {3} + {\ frac {5} {2}} x ^ {2} + x}$

Кривая Монтгомери над полем 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 Р = (х, у)}$${\ 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 (х, у)}$${\ Displaystyle (х, -у)}$${\ 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_{m}=[m]P=(X_{m}:Z_{m})}$${\displaystyle P_{m+n}=P_{m}+P_{n}=(X_{m+n}:Z_{m+n})}$

${\displaystyle X_{m+n}=Z_{m-n}((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}={\frac {B(x_{2}y_{1}-x_{1}y_{2})^{2}}{x_{1}x_{2}(x_{2}-x_{1})^{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}\\&={\frac {(x_{1}^{2}-1)^{2}}{4By_{1}^{2}}}={\frac {(x_{1}^{2}-1)^{2}}{4x_{1}(x_{1}^{2}+Ax_{1}+1)}}\\[8pt]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,}$

можно преобразовать следующим образом: разделить каждый член уравнения для с , и подставить переменные х и у , с , и , соответственно, чтобы получить уравнение${\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 . Springer-Verlag Berlin Heidelberg. С. 389–405. DOI : 10.1007 / 978-3-540-68164-9_26 . ISBN 978-3-540-68159-5.CS1 maint: multiple names: authors list (link)
• Воутер Кастрик; Стивен Гэлбрейт; Реза Резаэян Фарашахи (2008). «Эффективная арифметика эллиптических кривых с использованием смешанного представления Эдвардса-Монтгомери» (PDF) . Cite journal requires |journal= (help)

Внешние ссылки [ править ]

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