Krzywa Montgomery'ego

W matematyce krzywa Montgomery'ego jest formą krzywej eliptycznej wprowadzonej przez Petera L. Montgomery'ego w 1987 roku, różniącą się od zwykłej postaci Weierstrassa . Jest używany do niektórych obliczeń, w szczególności w różnych kryptograficznych .

Definicja

Krzywa Montgomery'ego równania ${\ textstyle {\ Frac {1} {4}} y ^ {2} = x ^ {3} + {\ Frac {5} {2}}x^{2}+x}$

Krzywa Montgomery'ego nad polem K jest zdefiniowana przez równanie

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

dla pewnego A , B ∈ K i z B ( ZA ² − 4) ≠ 0 .

krzywa ta jest rozpatrywana w skończonym polu K (na przykład w skończonym polu q elementów , K = F _q ) o charakterystyce różnej od 2 oraz z A ≠ ±2 i B ≠ 0 , ale są one również rozpatrywane na wymierne z tymi samymi ograniczeniami dla A i B .

Arytmetyka Montgomery'ego

Możliwe jest wykonanie pewnych „operacji” między punktami ${\ Displaystyle R = P + Q}$ eliptycznej : „dodanie” dwóch punktów $polega$$na$ , że ; „podwojenie” punktu polega na obliczeniu ${\ Displaystyle [2] P = P + P}$ (Aby uzyskać więcej informacji na temat operacji, zobacz Prawo grupowe ) i poniżej.

Punkt $By$${2} = x ^ {3} + Ax ^ {2} + x}$ w postaci Montgomery'ego można przedstawić we współrzędnych Montgomery'ego , gdzie ${\ Displaystyle P =$$)}$$\ Displaystyle Z \ neq 0$${$ są współrzędnymi rzutowymi dla Z }

Zauważ, że ten rodzaj reprezentacji punktu traci informacje: rzeczywiście w tym przypadku nie ma rozróżnienia między punktami $($ i ( $\ Displaystyle$ , ponieważ oba są podane przez punkt ${\ Displaystyle (X: Z)}$ . Jednak przy tej reprezentacji możliwe jest uzyskanie wielokrotności punktów, czyli przy danym ${\ Displaystyle P = (X: Z)}$ , obliczyć ${\ Displaystyle [n] P = (X_ {n}: Z_ {n})}$ .

Teraz, biorąc pod uwagę dwa punkty, ${\ Displaystyle P_ {n} = [n] P = (X_ {n}: Z_ {n})}$ i ${\ Displaystyle P_ {m} = [m] P = (X_ {m}: Z_ {m})}$ : ich suma jest określona przez punkt ${\ Displaystyle P_ {m + n} = P_ {m} + P_ {n} = (X_ {m + n}: Z_ {m + n })}$ którego współrzędne to:

${\ 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_ {mn} ((X_{m}-Z_{m})(X_{n}+Z_{n})-(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2 }}$

Jeśli ${\ displaystyle m = n}$ , to operacja staje się „podwojeniem”; współrzędne ${\ Displaystyle [2] P_ {n} = P_ {n} + P_ {n} = P_ {2n}=(X_{2n}:Z_{2n})}$ są dane następującymi równaniami:

${\ 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}))}$

Pierwsza rozważana powyżej operacja ( dodawanie ) ma koszt czasowy równy 3 M + 2 S , gdzie M oznacza mnożenie między dwoma ogólnymi elementami pola, na którym zdefiniowana jest krzywa eliptyczna, podczas gdy S oznacza kwadraturę ogólnego elementu pole.

Druga operacja (podwojenie) ma koszt czasowy 2 M + 2 S + 1 D , gdzie D oznacza mnożenie elementu ogólnego przez stałą ; $,$$)$ że to więc aby mieć małe re

Algorytm i przykład

$_$ punktu Montgomery'ego

Zakłada się, że ${\ Displaystyle Z_ {1} = 1}$ . Koszt tej implementacji to 1M + 2S + 1*A + 3add + 1*4. Tutaj M oznacza wymagane mnożenia, S oznacza podnoszenie do kwadratu, a a odnosi się do mnożenia przez A.

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

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

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

Przykład

Niech ${\ Displaystyle P_ {1} = (2, {\ sqrt {3}})}$ będzie punktem na krzywej ${\ Displaystyle 2y ^{2}=x^{3}-x^{2}+x}$ . we współrzędnych ${\ Displaystyle (X_ {1}: Z_ {1})}$ z ${\ Displaystyle x_ {1} = X_ {1} / Z_ {1}}$ , ${\ Displaystyle P_ {1} = (2: 1)}$ .

Następnie:

${\ 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\,}$

Rezultatem jest punkt taki, że ${\ Displaystyle P_ {2} = (X_ {2}: Z_ {2}) = (9:24)$${\ Displaystyle P_ {2} = 2 P_ {1}}$ .

Dodatek

${\ Displaystyle P_ {1} = (x_ {1}, y_ {1})}$ , P $\ Displaystyle P_ {2 } = (x_ {2}, y_ {2})}$ na krzywej Montgomery'ego ${\ Displaystyle M_ {A, B}$ współrzędnych afinicznych punkt ${\ Displaystyle P_ {3} = P_ {1} + P_ {2}}$ reprezentuje geometrycznie trzeci punkt przecięcia między ${\ Displaystyle M_ {A, B}}$ a linią przechodzącą przez ${\ displaystyle P_ {1}}$ i ${\ Displaystyle P_ {2}}$ . Możliwe jest znalezienie współrzędnych P. ${3})}$$\ Displaystyle P_ {3}} ( x 3 , y 3 ) {$ , w następujący sposób:

$i$ linię na afinicznej i pozwól jej przejść przez $Displaystyle P_ {1}}$ 2 ${2} }}$ (postaw warunek), w ten sposób uzyskuje się ${\ Displaystyle l = {\ Frac {y_ {2} -y_ {1}} {x_ {2} -x_{1}}}}$ i ${\ Displaystyle m = y_ {1} - \ lewo ({\ Frac {y_ {2} -y_ {1}} {x_ {2} -x_ { 1}}}\prawo)x_{1}}$ ;

$lx+m}$ przecinają linię z krzywą $=$ zastępując zmienną w równaniu krzywej $Displaystyle$${\$ ; otrzymuje się następujące równanie trzeciego stopnia :

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

Jak zaobserwowano wcześniej, to równanie ma trzy rozwiązania, które odpowiadają współrzędnym $\$$Displaystyle P_ {1}}$ , ${\ Displaystyle P_ {2}$ } i ${ \displaystyle P_{3}}$ . W szczególności to równanie można przepisać jako:

${\ Displaystyle (xx_ {1}) (xx_ {2}) (xx_ {3}) = 0}$

3) Porównując współczynniki dwóch identycznych równań podanych powyżej, w szczególności współczynniki wyrazów drugiego stopnia, otrzymujemy:

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

Tak więc ${\ Displaystyle x_ {3}}$ można zapisać w kategoriach ${\ Displaystyle x_ {1}}$ , ${\ Displaystyle y_ {1}}$ , ${\ Displaystyle x_ {2}}$$displaystyle y_ {2}}$ \ jak:

${\ Displaystyle x_ {3} = B \ lewo ({\ Frac {y_ {2} -y_ {1}} {x_ {2} -x_ {1}}} \ prawo) ^ {2} -A-x_ { 1}-x_{2}.}$

$y$$)$ Aby $punktu$ , wystarczy ${\ displaystyle ~ y = lx + m}$ linii . $,$ że nie da to punktu . Rzeczywiście, za pomocą tej metody można znaleźć współrzędne punktu takie, że $\ displaystyle ~ R}$${\ Displaystyle R + P_ {1} + P_ {2} = P_ {\ infty}}$ , ale jeśli ktoś potrzebuje wynikowego punktu sumy między ${\ Displaystyle P_ {1 }}$$Displaystyle$ , należy zauważyć, że: $R + P_ {1} + P_ {2} = P_ {\ infty }}$ wtedy i tylko wtedy, gdy ${\ Displaystyle -R = P_ {1} + P_ {2}}$ . Tak więc, biorąc pod uwagę punkt , konieczne jest znalezienie $\ displaystyle$${\ displaystyle ~ R}$ zmieniając znak na współrzędną $}$$~$ . Innymi $słowy$ , konieczna będzie zmiana znaku uzyskanej przez zastąpienie wartości ${\ displaystyle x_ {3}}$ w równaniu linii.

Kontynuując, współrzędne punktu ${\ Displaystyle P_ {3} = (x_ {3}, y_ {3})}$ , ${\ Displaystyle P_ {3}=P_{1}+P_{2}}$ to:

${\ 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}}$

Podwojenie

Biorąc pod uwagę punkt na krzywej Montgomery'ego $M_ {A, B}}$$Displaystyle$ punkt $] P_ {1}}$ reprezentuje geometrycznie trzeci punkt przecięcia krzywej z linią styczną do ${\ displaystyle P_ {1}}$ ; więc, aby znaleźć współrzędne punktu, ${\ Displaystyle P_ {3} = 2 P_ {1}}$ wystarczy zastosować tę samą metodę, co we wzorze dodawania; jednak w tym przypadku linia y = lx + m musi być styczna do krzywej w $M_{A,B}:f(x,y)=0}$$P_ {1}}$ więc jeśli ${\ Displaystyle$ z

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

wtedy wartość l , która reprezentuje nachylenie linii, jest dana wzorem:

${\ Displaystyle l = - \ lewo. {\ Frac {\ częściowe f} {\ częściowe x}} \ prawo / {\ Frac {\ częściowe f} {\ częściowe y }}}$

przez twierdzenie o funkcji uwikłanej .

więc ${\ Displaystyle l = {\ Frac {3x_ {1} ^ {2} + 2Ax_ {1} + 1} {2By_ {1}}} }$ a współrzędne punktu to: ${\ Displaystyle P_ {3}}$ , ${\ Displaystyle P_ {3} = 2 P_ {1}}$

${\ Displaystyle {\ rozpocząć {wyrównane} 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}}}$

Równoważność ze skręconymi krzywymi Edwardsa

Niech będzie $polem$ charakterystyce różnej od 2.

Niech będzie krzywą eliptyczną w postaci Montgomery'ego: ${\ displaystyle M_ {A, B}}$

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

z ${\ Displaystyle A \ w K \ smallsetminus \ {-2,2 \}}$ , ${\ Displaystyle B \ w K \ smallsetminus \ {0 \} }$

i niech będzie eliptyczną krzywą w skręconej postaci Edwardsa: ${\ Displaystyle E_ {a, d}}$

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

z ${\ Displaystyle a, d \ in K \ smallsetminus \ {0 \}, \ quad a \ neq d.}$

Poniższe twierdzenie pokazuje równoważność biracyjną między krzywymi Montgomery'ego a skręconą krzywą Edwardsa :

Twierdzenie (i) $Każda$ skręcona krzywa Edwardsa jest dwuracjonalnie równoważna krzywej Montgomery'ego . $krzywej$$jest$ krzywa ${\ Displaystyle A = {\ Frac {2 (a + d)} {ad}}}$ równoważna gdzie i ${\ Displaystyle B = {\ Frac {4} {reklama}}}$ .

Mapa : _

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

${\ Displaystyle (x, y) \ mapsto (u, v) = \ lewo ({\ Frac {1 + y} {1-y}}, {\frac {1+y}{(1-y)x}}\right)}$

jest równoważnością birational od do ${\ Displaystyle M_ {A, B} }$ z odwrotnością: mi za , $E_ {a, d}}$

${\ Displaystyle \ psi ^ {- 1}}$ : ${\ Displaystyle M_ {A, B} \ strzałka w prawo E_ {a, d}}$

${\ Displaystyle (u, v) \ mapsto (x, y) = \ lewo ({\ Frac {u} {v}}, {\ Frac {u-1} {u + 1}} \ prawo ),a={\frac {A+2}{B}},d={\frac {A-2}{B}}}$

$displaystyle$$krzywymi$ nie obowiązuje wszędzie: rzeczywiście mapa nie jest zdefiniowana w punktach lub $0}$$u +$${\ Displaystyle M_ {A, B}$ ZA .

Równoważność z krzywymi Weierstrassa

Dowolną krzywą eliptyczną można zapisać w postaci Weierstrassa. W szczególności krzywa eliptyczna w postaci Montgomery'ego

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

$Displaystyle$ każdy wyraz równania na przez i zastąpić zmienne x i y , $M_ {A, B}}$ z odpowiednio ${\ Displaystyle u = {\ Frac {x} {B}}}$ i ${\ Displaystyle v = {\ Frac {y} {B}}}$ , aby uzyskać równanie

${\ Displaystyle v ^ {2} = u ^ {3} + {\ Frac {A} {B}} u ^ {2} + {\ Frac {1} {B ^ {2}}} u.}$

Aby stąd uzyskać krótką formę Weierstrassa, wystarczy zastąpić u zmienną: ${\ displaystyle t- {\ frac {A} {3B}}$ }

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

ostatecznie daje to równanie:

${\ Displaystyle v ^ {2} = t ^ {3} + \ lewo ({\ Frac {3-A ^ {2}} {3B ^ {2}}} \ prawo) t + \ lewo ({\ Frac {2A ^{3}-9A}{27B^{3}}}\prawo).}$

Stąd odwzorowanie jest podane jako

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

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

W przeciwieństwie do tego krzywa eliptyczna nad polem podstawowym w postaci Weierstrassa ${\ displaystyle \ mathbb {F}}$

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

można przekształcić do postaci Montgomery'ego wtedy i tylko wtedy $a, b}}$ następujące warunki: mi za ,

1. ${\ Displaystyle z ^ {3} + az + b = 0}$ ma co najmniej jeden pierwiastek ${\ Displaystyle \ alpha \ in \ mathbb {F}}$ ; I
2. ${\ Displaystyle 3 \ alfa ^ {2} + a}$ jest kwadratową resztą w ${\ Displaystyle \ mathbb {F}}$ .

Gdy $_$ _ mapowanie

${\ Displaystyle \ psi ^ {- 1}}$ : ${\ Displaystyle E_ {a, b} \ strzałka w prawo M_ {A, B}}$

${\ Displaystyle (t, v) \ mapsto (x, y) = \ lewo (s (t- \ alfa), sv \ prawo), A = 3 \ alfa s, B = s}$ .

Zobacz też

• Krzywa25519
• Tabela kosztów operacji na krzywych eliptycznych – informacja o wymaganym czasie pracy w konkretnym przypadku

Notatki

•   Peter L. Montgomery (1987). „Przyspieszenie metod faktoryzacji krzywej Pollarda i krzywej eliptycznej” . Matematyka obliczeń . 48 (177): 243–264. doi : 10.2307/2007888 . JSTOR 2007888 .
•   Daniel J. Bernstein , Peter Birkner, Marc Joye, Tanja Lange i Christiane Peters (2008). „Skręcone krzywe Edwardsa”. Postęp w kryptologii – AFRICACRYPT 2008 . Notatki z wykładów z informatyki. Tom. 5023. Springer-Verlag Berlin Heidelberg. s. 389–405. doi : 10.1007/978-3-540-68164-9_26 . ISBN 978-3-540-68159-5 . {{ cite book }} : CS1 maint: wiele nazwisk: lista autorów ( link )
• Wouter Castryck; Stevena Galbraitha; Reza Rezaeian Farashahi (2008). „Wydajna arytmetyka na krzywych eliptycznych przy użyciu mieszanej reprezentacji Edwardsa-Montgomery'ego” (PDF) . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )

Linki zewnętrzne

• Krzywe Genus-1 na polach o dużej charakterystyce