Curva de Montgomery

En matemàtiques, la curva de Montgomery és una forma de curva elíptica introduïda per Peter L. Montgomery en 1987, diferent de la curva cúbica plana usual. S'utilisa per a certs càlculs, i en particular en diverses aplicacions de criptografia.

Definició

Una curva de Montgomery sobre un cos $K$ es definix per l'equació

M_{A, B} : B y^{2} = x^{3} + A x^{2} + x

per a $A, B \in K$ tal que $B (A 2 - 4) \neq 0$ .

Generalment, esta curva es considera sobre un cos finito K (per eixemple, sobre un cos finito de $q$ element, $K = F q$ ) en characteristic distint de 2 i en $A \neq \pm2$ i $B \neq 0$ . Sobre dits cossos, l'orde de grup de la curva sempre és divisible per 4. Les curves de Montgomery també es consideren sobre rationals en les mateixes restriccions per a $A$ i $B$ .

Tota curva de Montgomery té un punt en $(0, 0)$ .

Aritmètica de Montgomery

És possible realisar algunes operacions entre els punts d'una curva elíptica: sumar dos punts $P, Q$ consistix en trobar un tercer punt $R$ tal que $R = P + Q$ ; duplicar un punt consistix en calcular $[2] P = P + P$ (para més informació sobre operacions, vore curva elíptica i més avall).

Un punt $P = (x, y)$ en la curva elíptica en forma de Montgomery $B y^{2} = x^{3} + A x^{2} + x$ pot representar-se en coordenades de Montgomery $P = (X : Z)$ , a on $P = (X : Z)$ són les coordenades proyectivas i $x = X / Z$ per a $Z \neq 0$ .

Note's que este tipo de representació d'un punt pert informació: de fet, en este cas, no hi ha distinció entre punts afins, $(x, y)$ i $(x, - y)$ perque abdós estan donats pel punt $(X : Z)$ . No obstant, en esta representació és possible obtindre múltiples de punts, és dir, dau $P = (X : Z)$ , calcular $[n] P = (X_{n} : Z_{n})$ .

Ara be, considerant els dos punts $P_{n} = [n] P = (X_{n} : Z_{n})$ i $P_{m} = [m] P = (X_{m} : Z_{m})$ : el seu suma ve donada pel punt $P_{m + n} = P_{m} + P_{n} = (X_{m + n} : Z_{m + n})$ que els seus coordenades són:

X_{m + n} = Z_{m - n} ((X_{m} - Z_{m}) (X_{n} + Z_{n}) + (X_{m} + Z_{m}) (X_{n} - Z_{n}))^{2}

Z_{m + n} = X_{m - n} ((X_{m} - Z_{m}) (X_{n} + Z_{n}) - (X_{m} + Z_{m}) (X_{n} - Z_{n}))^{2}

Si $m = n$ , l'operació es convertix en una duplicació. Les coordenades de $[2] P_{n} = P_{n} + P_{n} = P_{2 n} = (X_{2 n} : Z_{2 n})$ vénen donades per les següents equacions:

4 X_{n} Z_{n} = (X_{n} + Z_{n})^{2} - (X_{n} - Z_{n})^{2}

X_{2 n} = (X_{n} + Z_{n})^{2} (X_{n} - Z_{n})^{2}

Z_{2 n} = (4 X_{n} Z_{n}) ((X_{n} - Z_{n})^{2} + ((A + 2) / 4) (4 X_{n} Z_{n}))

La primera operació considerada anteriorment (l'adició) té un cost en temps d'eixecució de 3M+2S, a on M denota la multiplicació entre dos elements generals del cos sobre el que es definix la curva elíptica, mentres que S denota el quadrat d'un element general del cos.

La segona operació (duplicació) té un cost en temps d'eixecució de 2M + 2S + 1D, a on D denota la multiplicació d'un element general per una constant. Note's que la constant és $(A + 2) / 4$ , per lo que es pot elegir $A$ per a obtindre un D menut.

Vore també

Curve25519
Anex:Cost en temps d'eixecució d'operacions en curves elíptiques, en informació sobre el temps d'eixecució requerit en cada cas específic

Referències

Bibliografia

Este artícul conté una traducció derivada de «Curva de Montgomery» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.