Montgomerykromme

De montegomerykromme is een type elliptische kromme dat is geïntroduceerd in 1987 door Peter L. Montgomery. 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.

Definitie

Een Montgomerykromme met de vergelijking ${\tfrac {1}{4}}y^{2}=x^{3}+2{,}5x^{2}+x$

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

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

waarin $A$ en $B$ vaste constanten in $K$ zijn die voldoen aan

$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

Operaties

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

Optellen

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

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

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

Verdubbeling

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

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

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

Gelijkwaardigheid met edwardskromme

De montgomerykromme en de edwardskromme gegeven door:

$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:

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

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

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

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

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

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

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

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

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

Projectieve coördinaten

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

$x=X/Z$

en

$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.