Factorización de curva elíptica de Lenstra

La factorización de curva elíptica de Lenstra o el método de factorización de curva elíptica (ECM) es un tiempo de ejecución subexponencial rápido, algoritmo para la factorización de enteros, que emplea curvas elípticas. Para el factoraje de propósito general, ECM es el tercer método de factoraje conocido más rápido. La segunda más rápida es la criba cuadrática de polinomios múltiples y la más rápida es la criba de campo numérico general. La factorización de la curva elíptica de Lenstra lleva el nombre de Hendrik Lenstra.

En términos prácticos, ECM se considera un algoritmo de factorización de propósito especial, ya que es más adecuado para encontrar factores pequeños. Actualmente, sigue siendo el mejor algoritmo para divisores que no superan los 50 o 60 dígitos, ya que su tiempo de ejecución está dominado por el tamaño del factor más pequeño p en lugar del tamaño del número n a factorizar. Con frecuencia, ECM se usa para eliminar factores pequeños de un número entero muy grande con muchos factores; si el entero restante sigue siendo compuesto, entonces solo tiene factores grandes y se factoriza utilizando técnicas de propósito general. El factor más grande encontrado usando ECM hasta ahora tiene 83 dígitos decimales y fue descubierto el 7 de septiembre de 2013 por R. Propper. Aumentar el número de curvas probadas mejora las posibilidades de encontrar un factor, pero no son lineales con el aumento del número de dígitos.

Algoritmo

El método de factorización de curvas elípticas de Lenstra para encontrar un factor de un número natural determinado ${displaystyle n}$ trabaja como sigue:

1. Escoge una curva elíptica aleatoria ${displaystyle mathbb {Z} /nmathbb {Z}$, con ecuación de la forma ${displaystyle ¿Qué?$ con un punto no-trivial ${displaystyle P(x_{0},y_{0}}$ en ella.

   Esto se puede hacer por primera vez elegir al azar ${displaystyle x_{0},y_{0},ain mathbb {Z} /nmathbb {Z}$, y luego establecer ${displaystyle B=y_{0}{2}-x_{0} {3}-ax_{0}{pmod {n}}$ para asegurar que el punto está en la curva.

2. Uno puede definir Adición de dos puntos sobre la curva, para definir un Grupo. Las leyes de adición se dan en el artículo sobre curvas elípticas.

   Podemos formar múltiples repetidos de un punto ${displaystyle P}$: ${displaystyle [k]P=P+ldots +P{text{ (k times)}}$. Las fórmulas adicionales implican tomar la pendiente modular de un acorde ${displaystyle P}$ y ${displaystyle Q}$, y por lo tanto división entre clases de residuos modulo ${displaystyle n}$, realizado utilizando el algoritmo de Euclidean extendido. En particular, división por algunos ${displaystyle v{bmod {n}}$ incluye el cálculo del ${displaystyle gcd(v,n)}$.

   Asumiendo que calculamos una pendiente de la forma ${displaystyle u/v}$ con ${displaystyle gcd(u,v)=1}$, entonces si ${displaystyle v=0{bmod {n}}$, el resultado de la adición de punto será ${displaystyle infty }$, el punto "en infinito" correspondiente a la intersección de la línea "vertical" ${displaystyle P(x,y),P'(x,-y)}$ y la curva. Sin embargo, si ${displaystyle gcd(v,n)neq 1,n}$, entonces la adición de punto no producirá un punto significativo en la curva; pero, más importante, ${displaystyle gcd(v,n)}$ es un factor no-trivial ${displaystyle n}$.

3. Computación ${displaystyle [k]P}$ sobre la curva elíptica${displaystyle {bmod {n}}$), donde ${displaystyle k}$ es un producto de muchos números pequeños: digamos, un producto de pequeñas primas elevadas a pequeños poderes, como en el algoritmo p-1, o el factorial ${displaystyle B!}$ para algunos no demasiado grande ${displaystyle B}$. Esto se puede hacer eficientemente, un pequeño factor a la vez. Digamos, para llegar ${displaystyle [B]P}$, primer cálculo ${displaystyle [2]P}$, entonces ${displaystyle [3]([2]P)}$, entonces ${displaystyle [4]([3]P)}$, y así sucesivamente. ${displaystyle B}$ es elegido para ser lo suficientemente pequeño ${displaystyle B}$-la adición de puntos puede ser realizada en tiempo razonable.
   • Si terminamos todos los cálculos anteriores sin encontrar elementos no invertibles (${displaystyle {bmod {n}}$), significa que el orden de curvas elípticas (modulo primes) no es lo suficientemente suave, por lo que necesitamos probar de nuevo con una curva diferente y punto de partida.
   • Si nos encontramos con un ${displaystyle gcd(v,n)neq 1,n}$ hemos terminado: es un factor no-trivial ${displaystyle n}$.

La complejidad del tiempo depende del tamaño del factor primario más pequeño del número y puede ser representado por exp[(√2+ o 1)) √InpInp], donde p es el factor más pequeño de n, o ${displaystyle L_{p}left [{frac {1}{2}} {sqrt {2}right]$En la nota L.

¿Por qué funciona el algoritmo?

Si p y q son dos divisores principales de n, entonces Sí.²=x³+ ax+b(modelo)n) implica la misma ecuación también modulop y moduloq. Estas dos curvas elípticas más pequeñas con las ${displaystyle boxplus }$- La adición son grupos genuinos. Si estos grupos tienen N_p y N_q elementos, respectivamente, para cualquier punto P en la curva original, por el teorema de Lagrange, k■ 0 es mínimo tal que ${displaystyle kP=infty}$ en el modulo curva p implica que k divideciones N_p; además, ${displaystyle N_{p}P=infty$. La declaración analógica sostiene para el modulo curva q. Cuando la curva elíptica es elegida aleatoriamente, entonces N_p y N_q son números aleatorios cercanos p+ 1 y q+ 1, respectivamente (véase infra). Por lo tanto es poco probable que la mayoría de los factores principales N_p y N_q son los mismos, y es muy probable que mientras computación eP, vamos a encontrar algunos kP que es modulop pero no moduloq, o viceversa. Cuando este es el caso, kP no existe en la curva original, y en las computaciones encontramos algunos v con ambos gcd(v,p)p o gcd(v,q)q, pero no ambos. Eso es, gcd(v,n) dio un factor no-trivial den.

ECM es, en esencia, una mejora del antiguo algoritmo p − 1. El algoritmo p − 1 encuentra factores primos p tales que p − 1 es b-powersmooth para valores pequeños de b. Para cualquier e, un múltiplo de p − 1, y cualquier a primo relativo a p, por el pequeño teorema de Fermat tenemos a^e ≡ 1 (modificación p). Entonces gcd(a^e − 1, n) es probable que produzca un factor de n. Sin embargo, el algoritmo falla cuando p - 1 tiene factores primos grandes, como es el caso de los números que contienen números primos fuertes, por ejemplo.

ECM sortea este obstáculo considerando el grupo de una curva elíptica aleatoria sobre el campo finito Z_p, en lugar de considerar el multiplicativo grupo de Z_p que siempre tiene orden p − 1.

El orden del grupo de una curva elíptica sobre Z_p varía (bastante al azar) entre p + 1 − 2√p< /span> y p + 1 + 2√p por el teorema de Hasse, y es probable que sea suave para algunas curvas elípticas. Aunque no hay pruebas de que se encontrará un orden de grupo suave en el intervalo de Hasse, mediante el uso de métodos probabilísticos heurísticos, el teorema de Canfield-Erdős-Pomerance con opciones de parámetros adecuadamente optimizadas y la notación L, podemos esperar intentar < span class="texhtml">L[√2 /2, √2] curvas antes de obtener un orden de grupo suave. Esta estimación heurística es muy fiable en la práctica.

Un ejemplo

El siguiente ejemplo es de Trappe & Washington (2006), con algunos detalles añadidos.

Queremos factorizar n = 455839. Elijamos la curva elíptica y² = x³ + 5x – 5, con el punto P = (1, 1) en él, e intentemos calcular (10!) P.

La pendiente de la recta tangente en algún punto A=(x, y) es < i>s = (3x² + 5)/(2y) (módulo n). Usando s podemos calcular 2A. Si el valor de s es de la forma a/b donde b > 1 y mcd(a,b) = 1, tenemos que encontrar el inverso modular de b. Si no existe, mcd(n,b) es un factor no trivial de n.

Primero calculamos 2P. Tenemos s(P) = s(1,1) = 4, entonces las coordenadas de 2P = (x′, y′) son x′ = s² – 2x = 14 y y′ = s(x – x′) – y = 4(1 – 14) – 1 = –53, todos los números entendidos (mod n). Solo para comprobar que este 2P está realmente en la curva: (–53)² = 2809 = 14³ + 5·14 – 5.

Entonces computamos 3(2)P). Tenemos s(22)P) s(14,-53) = –593/106 (mod n). Usando el algoritmo de Euclidean: 455839 = 4300·106 + 39, entonces 106 = 2·39 + 28, entonces 39 = 28 + 11, entonces 28 = 2·11 + 6, entonces 11 = 6 + 5, entonces 6 = 5 + 1. Por lo tanto gcd(455839, 106) = 1, y trabajando hacia atrás (una versión del algoritmo euclidiano extendido): 1 = 6 – 5 = 2·6 – 11 = 2·28 – 5·11 = 7·28 – 5·39 = 7·106 – 19·39 = 81707·106 – 19·455839. Por lo tanto 106⁻¹ = 81707 (mod 455839), y –593/106 = –133317 (mod 455839). Dado esto s, podemos calcular las coordenadas de 2(2)PAsí como lo hicimos arriba: 4P = (259851, 116255). Sólo para comprobar que este es un punto en la curva: Sí.² = 54514 = x³ + 5x – 5 (mod 455839). Después de esto, podemos calcular ${displaystyle 3(2P)=4Pboxplus 2P}$.

Podemos calcular 4!P de manera similar, y así sucesivamente, pero 8!P requiere invertir 599 (mod 455839).< /span> El algoritmo euclidiano da que 455839 es divisible por 599, y hemos encontrado una factorización 455839 = 599·761.

La razón por la que esto funcionó es que la curva (mod 599) tiene 640 = 2⁷·5 puntos, mientras que (mod 761) tiene 777 = 3·7·37 puntos. Además, 640 y 777 son los enteros positivos más pequeños k tales que kP = ∞ en la curva (mod 599) y (mod 761), respectivamente. Como 8! es múltiplo de 640 pero no de 777, tenemos 8!P = ∞< /span> en la curva (mod 599), pero no en la curva (mod 761), por lo tanto, la adición repetida se rompió aquí abajo, produciendo la factorización.

El algoritmo con coordenadas proyectivas

Antes de considerar el plano proyectivo ${displaystyle (mathbb {Z}/nmathbb {Z}/sim}$ primero considerar un espacio "normal" proyectivo sobre R: En lugar de puntos, se estudian líneas a través del origen. Una línea puede ser representada como un punto no cero ${displaystyle (x,y,z)}$, bajo una relación de equivalencia ~ dada por: ${displaystyle (x,y,z)sim (x',y',z')}$ ⇔ c ل 0 tal que x' = cx, Sí. cSí. y z' = cz. Bajo esta relación de equivalencia, el espacio se llama el plano proyector ${displaystyle mathbb {} {2}}$; puntos, denotados por ${displaystyle (x:y:z)}$, corresponden a líneas en un espacio tridimensional que pasan por el origen. Note que el punto ${displaystyle (0:0:0)}$ no existe en este espacio ya que para dibujar una línea en cualquier dirección posible requiere por lo menos una de x',y' o z' ل 0. Ahora observa que casi todas las líneas pasan por cualquier avión de referencia dado - como el (X,Y,1)-plano, mientras que las líneas precisamente paralelas a este plano, teniendo coordenadas (X,Y,0), especificar direcciones únicas, como 'puntos en el infinito' que se utilizan en el afine (X,YEl plan está arriba.

En el algoritmo, sólo se utiliza la estructura de grupo de una curva elíptica sobre el campo R. Puesto que no necesitamos necesariamente el campo R, un campo finito también proporcionará una estructura de grupo en una curva elíptica. Sin embargo, considerando la misma curva y operación sobre ${displaystyle (mathbb {Z}/nmathbb {Z}/sim }$ con n no un primo no da un grupo. El método Elliptic Curve utiliza los casos de fracaso de la ley de adición.

Ahora declaramos el algoritmo en coordenadas proyectivas. El elemento neutral se da entonces por el punto de infinito ${displaystyle (0:1:0)}$. Vamos n ser un entero (positivo) y considerar la curva elíptica (un conjunto de puntos con alguna estructura en él) ${displaystyle E(mathbb {Z}/nmathbb {Z}={(x:y:z)in mathbb {P} ^{2} ^{2}z=x^{3}+axz^{2}+bz^{3}}}}}} {}}}}}}}}}}$.

1. Pick ${displaystyle x_{P},y_{P},ain mathbb {Z}/nmathbb {Z}$ con a ل 0.
2. Cálculo ${displaystyle B=y_{2}-x_{3}-ax_{P}$. La curva elíptica E es entonces en la forma Weierstrass dada por ${displaystyle ¿Qué?$ y utilizando coordenadas proyectivas la curva elíptica es dada por la ecuación homogénea ${displaystyle ZY^{2}=X^{3}+aZ^{2}X+bZ^{3}$. Tiene el punto ${displaystyle P=(x_{P}:y_{P}:1)}$.
3. Elija un límite superior ${displaystyle Bin mathbb {Z}$ para esta curva elíptica. Observación: Usted sólo encontrará factores p si el orden de grupo de la curva elíptica E sobre ${displaystyle mathbb {Z} /pmathbb {Z}$ (denominado por ${displaystyle #E(Mathbb {Z} /pmathbb {Z}$) es B-smooth, lo que significa que todos los factores principales ${displaystyle #E(Mathbb {Z} /pmathbb {Z}$ tener que ser menos o igual a B.
4. Cálculo ${displaystyle k={rm {lcm}(1,dotsB)}$.
5. Cálculo ${displaystyle kP:=P+P+cdots +P}$ ()k tiempos) en el anillo ${displaystyle E(mathbb {Z}/nmathbb {Z})}$. Note que si ${displaystyle #E(mathbb {Z}/nmathbb {Z}$ es B- moho y n es primo (y por lo tanto ${displaystyle mathbb {Z} /nmathbb {Z}$ es un campo) que ${displaystyle kP=(0:1:0)}$. Sin embargo, si sólo ${displaystyle #E(Mathbb {Z} /pmathbb {Z}$ B-smooth para un divisor p de n, el producto podría no ser (0:1:0) porque la adición y la multiplicación no están bien definidos si n no es la primera. En este caso, se puede encontrar un divisor no-trivial.
6. Si no, entonces vuelve al paso 2. Si esto ocurre, entonces usted notará esto al simplificar el producto ${displaystyle kP.}$

En el punto 5 se dice que bajo las circunstancias adecuadas se puede encontrar un divisor no-trivial. Como se señala en el artículo de Lenstra (Integers con curvas elípticas) la adición necesita la suposición ${displaystyle gcd(x_{1}-x_{2},n)=1}$. Si ${displaystyle P,Q}$ no ${displaystyle (0:1:0)}$ y distinto (otra adición funciona de forma similar, pero es un poco diferente), entonces la adición funciona como sigue:

• Para calcular: ${displaystyle R=P+Q;}$ ${displaystyle P=(x_{1}:y_{1}:1),Q=(x_{2}:y_{2}:1)}$,
• ${displaystyle lambda =(y_{1}-y_{2})(x_{1}-x_{2})^{-1}$,
• ${displaystyle x_{3}=lambda ^{2}-x_{1}-x_{2}$,
• ${displaystyle Y... (x_{1}-x_{3}-y_{1}$,
• ${displaystyle R=P+Q=(x_{3}:y_{3}:1)}$.

Si la adición falla, esto será debido a una falla calculando ${displaystyle lambda.}$ En particular, porque ${displaystyle (x_{1}-x_{2}}{-1}$ no siempre se puede calcular si n no es primo (y por lo tanto ${displaystyle mathbb {Z} /nmathbb {Z}$ no es un campo). Sin hacer uso de ${displaystyle mathbb {Z} /nmathbb {Z}$ ser un campo, uno podría calcular:

• ${displaystyle lambda - Sí.$,
• ${displaystyle x_{3}={lambda ### {2}-x_{1}(x_{1}-x_{2} {2}-x_{2}(x_{1}-x_{2})} {2}$,
• ${displaystyle Y...$,
• ${displaystyle R=P+Q=(x_{3}'(x_{1}-x_{2}:y_{3}':(x_{1}-x_{2})^{3})}$, y simplificar si es posible.

Este cálculo siempre es legal y si el mcd de la Z-coordina con el estilo n ≠ (1 o n), por lo que cuando falla la simplificación, se encuentra un divisor no trivial de n.

Curvas de Edwards retorcidas

El uso de las curvas de Edwards necesita menos multiplicaciones modulares y menos tiempo que el uso de las curvas de Montgomery o las curvas de Weierstrass (otros métodos utilizados). Usando las curvas de Edwards también puedes encontrar más números primos.

Definición. Vamos ${displaystyle k}$ ser un campo en el que ${displaystyle 2neq 0}$, y dejar ${displaystyle a,din ksetminus {0}$ con ${displaystyle aneq d}$. Entonces la curva Edwards torcida ${displaystyle E_{E,a,d}$ es dado por ${displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}$ Una curva Edwards es una curva torcida de Edwards en la que ${displaystyle a=1}$.

Hay cinco formas conocidas de construir un conjunto de puntos en una curva de Edwards: el conjunto de puntos afines, el conjunto de puntos proyectivos, el conjunto de puntos invertidos, el conjunto de puntos extendidos y el conjunto de puntos completos.

El conjunto de puntos afines viene dado por:

${displaystyle {(x,y)in mathbb - ¿Qué?$.

La ley de la suma viene dada por

${displaystyle (e,f),(g,h)mapsto left({frac {eh+fg}{1+degfh}}},{frac {fh-aeg}{1-degfh}right).}}$

El punto (0,1) es su elemento neutral y el inverso de ${displaystyle (e,f)}$ es ${displaystyle (-e,f)}$.

Las otras representaciones se definen de forma similar a cómo la curva proyectiva de Weierstrass se deriva de la afín.

Cualquier curva elíptica en forma Edwards tiene un punto de orden 4. Así que el grupo de torsión de una curva Edwards sobre ${displaystyle mathbb {Q}$ es isomorfo para ambos ${displaystyle mathbb {Z} Mathbb {Z} Mathbb {Z} {Z}mathbb {Z} /2mathbb {Z} times mathbb {Z} /4mathbb {Z}$ o ${displaystyle mathbb {Z} {Z} times mathbb {Z}$.

Los casos más interesantes para ECM son ${displaystyle mathbb {Z} {Z}$ y ${displaystyle mathbb {Z} {Z} times mathbb {Z}$, ya que obligan a las órdenes del grupo de las primas del modulo curva a ser divisible por 12 y 16 respectivamente. Las siguientes curvas tienen un grupo de torsión isomorfa a ${displaystyle mathbb {Z} {Z}$:

• ${displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$ con punto ${displaystyle (a,b)}$ Donde ${displaystyle bnotin {-2,-1/2,0,pm 1},a^{2}=-(b^{2}+2b)}$ y ${displaystyle d=-(2b+1)/(a^{2}b^{2}}$
• ${displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$ con punto ${displaystyle (a,b)}$ Donde ${displaystyle a={frac {u^{2}}{u^{2}+1},b=-{frac {(u-1)}{u}{u^{2}+1}}} {f}}} {f}}} {f}$ y ${displaystyle d={frac {(u^{2}+1)}(u^{2}-4u+1)}{(u-1)^{6}(u+1)}},unotin$