En matemàtiques, la corba de Montgomery és una forma de corba el·líptica introduïda per Peter L. Montgomery el 1987, diferent de la forma habitual de Weierstrass. S'utilitza per a certs càlculs, i en particular en diferents aplicacions de criptografia.
Definició miniatura|300x300px|Una corba de Montgomery de l'equació Una corba de Montgomery sobre un cos es defineix per l'equació
per tal que .
Generalment, aquesta corba es considera sobre un cos finit K (per exemple, sobre un camp finit de elements, ) amb característica diferent de 2 i amb i Sobre aquests camps, l'ordre de grup de la corba és sempre divisible per 4. Les corbes de Montgomery també es consideren sobre els racionals amb les mateixes restriccions per a i
Cada corba de Montgomery té un punt a .
Aritmètica de Montgomery És possible fer algunes "operacions" entre els punts d'una corba el·líptica: "sumar" dos punts consisteix a trobar-ne un tercer de tal manera que ; "duplicar" un punt consisteix a calcular (Per a més informació sobre les operacions, vegeu La llei de grup) i a continuació.
Un punt sobre la corba el·líptica en la forma de Montgomery es pot representar en coordenades de Montgomery , on són coordenades projectives i per .
Fixeu-vos que aquest tipus de representació per a un punt perd informació: de fet, en aquest cas, no hi ha cap distinció entre els punts afins i perquè tots dos estan donats pel punt . Tanmateix, amb aquesta representació és possible obtenir múltiples de punts, és a dir, donat , per calcular .
Ara, considerant els dos punts i : la seva suma ve donada pel punt les coordenades del qual són:
Si , aleshores l'operació esdevé una "duplicació"; les coordenades de vénen donats per les equacions següents:
La primera operació considerada anteriorment (suma) té un cost de temps de 3 M + 2 S, on M denota la multiplicació entre dos elements generals del camp sobre els quals es defineix la corba el·líptica, mentre que S denota l'elevació al quadrat d'un element general del camp.
La segona operació (duplicació) té un cost de temps de 2 M + 2 S + 1 D, on D denota la multiplicació d'un element general per una constant; observeu que la constant és , així es pot triar per tenir una petita D.
Algoritme i exemple El següent algorisme representa una duplicació d'un punt sobre una corba el·líptica en forma de Montgomery.
Se suposa que El cost d'aquesta implementació és 1M + 2S + 1*A + 3add + 1*4. Aquí M denota les multiplicacions necessàries, S indica els quadrats i a fa referència a la multiplicació per A.
Exemple Sigui un punt de la corba En coordenades , amb , .
Aleshores:
El resultat és el punt de tal manera que .
Addició Donats dos punts , a la corba de Montgomery en coordenades afins, el punt representa, geomètricament, el tercer punt d'intersecció entre i la línia que passa per i És possible trobar les coordenades de , de la següent manera:
1) considerem una línia genèrica en el pla afí i deixar-lo passar per i (imposar la condició), d'aquesta manera, s'obté i ;
2) intersecció de la línia amb la corba , substituint el variable a l'equació de la corba amb ; s'obté la següent equació de tercer grau:
Com s'ha observat anteriorment, aquesta equació té tres solucions que corresponen a la coordenades de , i En particular, aquesta equació es pot reescriure com:
3) Comparant els coeficients de les dues equacions idèntiques donades anteriorment, en particular els coeficients dels termes de segon grau, s'obté:
.
Així doncs, es pot escriure en termes de , , , , com a:
4) Per trobar la coordenada del punt n'hi ha prou amb substituir el valor a la línia . Tingueu en compte que això no donarà sentit. directament. De fet, amb aquest mètode es troben les coordenades del punt de tal manera que , però si es necessita el punt resultant de la suma entre i , aleshores cal observar que: si i només si Així doncs, donat el punt , cal trobar , però això es pot fer fàcilment canviant el signe a coordenada de En altres paraules, caldrà canviar el signe de la coordenada obtinguda substituint el valor en l'equació de la recta.
Reprenent, les coordenades del punt , són:
Duplicació Donat un punt. a la corba de Montgomery , el punt representa geomètricament el tercer punt d'intersecció entre la corba i la recta tangent a ; per tant, per trobar les coordenades del punt n'hi ha prou amb seguir el mateix mètode que s'indica a la fórmula de la suma; tanmateix, en aquest cas, la recta y = lx + m ha de ser tangent a la corba en , així doncs, si amb
aleshores el valor de l, que representa el pendent de la recta, ve donat per:
pel teorema de la funció implícita.
Així doncs i les coordenades del punt , són:
Equivalència amb corbes d'Edwards retorçades Sigui un camp amb una característica diferent de 2.
Sigui una corba el·líptica en la forma de Montgomery:
amb ,
i sigui una corba el·líptica en la forma retorçada d'Edwards:
amb
Equivalència amb les corbes de Weierstrass Qualsevol corba el·líptica es pot escriure en forma de Weierstrass. En particular, la corba el·líptica en forma de Montgomery
es pot transformar de la següent manera: dividir cada terme de l'equació per per , i substituïm les variables x i y, per i respectivament, per obtenir l'equació
Per obtenir una forma curta de Weierstrass des d'aquí, n'hi ha prou amb substituir u per la variable :
finalment, això dóna l'equació:
Per tant, el mapatge es dóna com
En canvi, una corba el·líptica sobre el camp base en forma de Weierstrass
es pot convertir a la forma de Montgomery si i només si compleix les condicions següents:
has at least one root ; and is a quadratic residue in .
Quan es compleixen aquestes condicions, aleshores per a tenim el mapatge
.
Referències
Categoria:Criptografia