Montgomerykromme

De montegomerykromme is een type elliptische kromme dat is geïntroduceerd in 1987 door Peter L. Montgomery.^[1] Dit type werd oorspronkelijk ontwikkeld om het factoriseren met behulp van het algoritme van Lenstra en de Pollards p-1-methode te versnellen. Tegenwoordig wordt de montegomerykromme ook voor andere cryptographische doeleinden gebruikt, zoals de elliptische kromme Curve25519.

Een montegomerykromme over een lichaam (Ned) / veld (Be) ${\displaystyle K}$ wordt gegeven door de vergelijking:

${\displaystyle B\,y^{2}=x^{3}+A\,x^{2}+x}$

waarin ${\displaystyle A}$ en ${\displaystyle B}$ vaste constanten in ${\displaystyle K}$ zijn die voldoen aan

${\displaystyle B(A^{2}-4)\neq 0}$

In het algemeen worden montgomerykrommen beschouwd over een eindig lichaam/veld met karakteristiek ongelijk aan 2 of over de rationale getallen.

Bijzonderheden van de montgomerykromme zijn:

• Het punt(0, 0) ligt op iedere kromme en heeft een orde van 2
• In een eindig lichaam is de orde van de kromme altijd deelbaar door 4

Net als bij elke elliptische krommen is het bij de montegomerykromme mogelijk een aantal operaties hierop uit te voeren, zoals optellen en verdubbelen.^[2]

De som van twee punten ${\displaystyle (x_{3},y_{2})=(x_{1},y_{1})+(x_{2},y_{2})}$ op een montegomerykromme kan berekend worden met de formule:

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

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

De verdubbeling van een punt ${\displaystyle (x_{2},y_{2})=2(x_{1},y_{1})}$ op een montegomerykromme kan berekend worden met de formule:

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

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

De montgomerykromme en de edwardskromme gegeven door:

${\displaystyle a\,u^{2}+v^{2}=1+d\,u^{2}v^{2}}$

zijn birationaal gelijkwaardig. De ene kromme kan dus in de andere vorm worden omgezet via de relaties:

${\displaystyle A={\frac {2(a+d)}{a-d}}}$

${\displaystyle B={\frac {4}{a-d}}}$

Een punt ${\displaystyle (u,v)}$ van de edwardskromme komt overeen met het punt ${\displaystyle (x,y)}$ van de montgomerykromme bepaald door:

${\displaystyle x={\frac {1+v}{1-v}}}$

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

Punten van de montgomerykromme ${\displaystyle (x,y)}$ kunnen worden omgezet naar de edwardskromme ${\displaystyle (u,v)}$ met de formule:

Een punt ${\displaystyle (x,y)}$ van de montgomerykromme komt overeen met het punt ${\displaystyle (u,v)}$ van de edwardskromme bepaald door:

${\displaystyle u={\frac {x}{y}}}$

${\displaystyle v={\frac {x-1}{x+1}}}$

De montgomerykromme kan ook beschreven worden met de zogeheten montgomerycoördinaten ${\displaystyle (X:Z)}$, projectieve coördinaten met ${\displaystyle Z\neq 0}$, waarvoor geldt:

${\displaystyle x=X/Z}$

en

${\displaystyle B\,y^{2}=x^{3}+Ax^{2}+x}$

Met behulp van montgomerycoördinaten is het mogelijk de berekening op de x-coördinaat te versnellen. Hiervoor zijn er verschillende snelle algoritmes om berekening als verdubbelen, optellen en vermenigvuldigen in montgomerycoördinaten te doen.^[3]