La factorización de la curva elíptica de Lenstra o el método de factorización de la curva elíptica ( ECM ) es un algoritmo de tiempo de ejecución subexponencial rápido para la factorización de enteros , que emplea curvas elípticas . Para la factorización de propósito general , ECM es el tercer método de factorización conocido más rápido. El segundo más rápido es el tamiz cuadrático polinomial múltiple , y el más rápido es el tamiz 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 el más adecuado para encontrar factores pequeños. Actualmente [actualizar], sigue siendo el mejor algoritmo para divisores que no excedan de 50 a 60 dígitos , ya que su tiempo de ejecución está dominado por el tamaño del factor más pequeño p más que por el tamaño del número n que se va a factorizar. Con frecuencia, ECM se utiliza para eliminar pequeños factores 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. [1] 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 curva elíptica de Lenstra para encontrar un factor de un número natural dado funciona de la siguiente manera:
- Elija una curva elíptica aleatoria sobre, con ecuación de la forma junto con un punto no trivial en eso.
- Esto se puede hacer eligiendo primero al azar , y luego configurar para asegurar que el punto esté en la curva.
- Se puede definir la suma de dos puntos en la curva, para definir un grupo . Las leyes de la adición se dan en el artículo sobre curvas elípticas .
- Podemos formar múltiplos repetidos de un punto : . Las fórmulas de suma implican tomar la pendiente modular de una cuerda que une y , y por lo tanto la división entre clases de residuos módulo , realizado utilizando el algoritmo euclidiano extendido . En particular, la división por algunos incluye el cálculo de la .
- Suponiendo que calculamos una pendiente de la forma con , Entonces sí , el resultado de la suma de puntos será , el punto "en el infinito" correspondiente a la intersección de la línea "vertical" que une y la curva. Sin embargo, si , entonces la suma de puntos no producirá un punto significativo en la curva; pero mas importante, es un factor no trivial de .
- Calcular en la curva elíptica), dónde es un producto de muchos números pequeños: digamos, un producto de pequeños números primos elevados a pequeñas potencias, como en el algoritmo p-1 , o el factorial para algunos no demasiado grandes . Esto se puede hacer de manera eficiente, un pequeño factor a la vez. Decir, para conseguir, primer cálculo , luego , luego , y así. se elige para que sea lo suficientemente pequeño para que La suma de puntos en sentido común se puede realizar en un tiempo razonable.
- Si terminamos todos los cálculos anteriores sin encontrar elementos no invertibles (), significa que el orden de las curvas elípticas (módulo primos) no es lo suficientemente suave , por lo que debemos intentarlo de nuevo con una curva y un punto de partida diferentes.
- Si nos encontramos con un hemos terminado: es un factor no trivial de .
La complejidad del tiempo depende del tamaño del factor primo más pequeño del número y se puede representar por exp [( √ 2 + o (1)) √ ln p ln ln p ] , donde p es el factor más pequeño de n , o, En L-notación .
¿Por qué funciona el algoritmo?
Si p y q son dos divisores primos de n , entonces y 2 = x 3 + ax + b (mod n ) implica la misma ecuación también en módulo p y módulo q . Estas dos curvas elípticas más pequeñas con el-Además ahora son grupos genuinos . Si estos grupos tienen N p y N q elementos, respectivamente, entonces para cualquier punto P en la curva original, según el teorema de Lagrange , k > 0 es mínimo tal queen la curva módulo p implica que k divide a N p ; es más,. La declaración análoga es válida para la curva módulo q . Cuando la curva elíptica se elige al azar, N p y N q son números aleatorios cercanos a p + 1 y q + 1, respectivamente (ver más abajo). Por tanto, es poco probable que la mayoría de los factores primos de N p y N q sean iguales, y es muy probable que al calcular eP , encontremos algún kP que sea ∞ módulo p pero no módulo q , o viceversa. Cuando este es el caso, kP no existe en la curva original, y en los cálculos encontramos algo de v con mcd ( v , p ) = p o mcd ( v , q ) = q , pero no ambos. Es decir, mcd ( v , n ) dio un factor no trivial de n .
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 correo , un múltiplo de p - 1, y cualquier un primo con respecto a p , por pequeño teorema de Fermat tenemos un correo ≡ 1 ( mod p ) . Entonces es probable que mcd ( a e - 1, n ) produzca un factor de n . Sin embargo, el algoritmo falla cuando p - 1 tiene factores primos grandes, como es el caso de números que contienen primos fuertes , por ejemplo.
ECM evita este obstáculo al considerar el grupo de una curva elíptica aleatoria sobre el campo finito Z p , en lugar de considerar el grupo multiplicativo 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 y p + 1 + 2 √ p por el teorema de Hasse , y es probable que sean suaves para algunas curvas elípticas. Aunque no hay pruebas de que se encuentre un orden de grupo uniforme 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 probar L [ √ 2 /2, √ 2 ] curvas antes de conseguir un orden de grupo lisa. 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 agregados.
Queremos factor de n = 455839. vamos a elegir la curva elíptica y 2 = x 3 + 5 x - 5, con el punto P = (1, 1) sobre el mismo, y vamos a tratar de cálculo (10!) P .
La pendiente de la recta tangente en algún punto A = ( x , y ) es s = (3 x 2 + 5) / (2 y ) (mod n) . Utilizando s podemos calcular 2 A . 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 .
En primer lugar, calculamos 2 P . Tenemos s ( P ) = s (1,1) = 4, entonces las coordenadas de 2 P = ( x ′ , y ′ ) son x ′ = s 2 - 2 x = 14 y y ′ = s ( x - x ′ ) - y = 4 (1 - 14) - 1 = –53, se entienden todos los números (mod n ). Solo para comprobar que este 2 P está efectivamente en la curva: (–53) 2 = 2809 = 14 3 + 5 · 14 - 5.
Luego calculamos 3 (2 P ). Tenemos s (2 P ) = s (14, -53) = –593/106 (mod n ). Usando el algoritmo euclidiano : 455839 = 4300 · 106 + 39, luego 106 = 2 · 39 + 28, luego 39 = 28 + 11, luego 28 = 2 · 11 + 6, luego 11 = 6 + 5, luego 6 = 5 + 1. Por lo tanto, mcd (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 tanto, 106 −1 = 81707 (mod 455839) y –593/106 = –133317 (mod 455839). Dado este s , podemos calcular las coordenadas de 2 (2 P ), tal como lo hicimos anteriormente: 4 P = (259851, 116255). Solo para comprobar que este es un punto en la curva: y 2 = 54514 = x 3 + 5 x - 5 (mod 455839). Después de esto, podemos calcular.
¡Podemos calcular 4 de manera similar! P , y así sucesivamente, ¡pero 8! P requiere invertir 599 (mod 455839). 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 7 · 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. ¡Desde las 8! es un múltiplo de 640 pero no un múltiplo de 777, ¡tenemos 8! P = ∞ en la curva (mod 599), pero no en la curva (mod 761), por lo tanto , la adición repetida se rompió aquí, dando como resultado la factorización.
El algoritmo con coordenadas proyectivas
Antes de considerar el plano proyectivo sobre Considere primero un espacio proyectivo "normal" sobre ℝ: en lugar de puntos, se estudian las líneas que pasan por el origen. Una línea puede representarse como un punto distinto de cero, bajo una relación de equivalencia ~ dada por: ⇔ ∃ c ≠ 0 tal que x '= c x , y' = c y y z '= c z . Bajo esta relación de equivalencia, el espacio se denomina plano proyectivo. ; puntos, denotados por, corresponden a líneas en un espacio tridimensional que pasan por el origen. Tenga en cuenta que el puntono existe en este espacio ya que para trazar una línea en cualquier dirección posible se requiere al menos uno de x ', y' o z '≠ 0. Ahora observe que casi todas las líneas pasan por cualquier plano de referencia dado, como ( X , Y , 1) -plano, mientras que las líneas exactamente paralelas a este plano, que tienen coordenadas ( X, Y , 0), especifican direcciones de forma única, como 'puntos en el infinito' que se utilizan en el plano afín ( X, Y ) que yace arriba.
En el algoritmo, solo se utiliza la estructura de grupo de una curva elíptica sobre el campo ℝ. Dado que no necesitamos necesariamente el campo ℝ, un campo finito también proporcionará una estructura de grupo en una curva elíptica. Sin embargo, considerando la misma curva y operación sobrecon n no primo no da un grupo. El método de la curva elíptica hace uso de los casos de falla de la ley de la adición.
Ahora expresamos el algoritmo en coordenadas proyectivas. El elemento neutro viene dado por el punto en el infinito. Sea n un entero (positivo) y considere la curva elíptica (un conjunto de puntos con alguna estructura).
- Elegir con un ≠ 0.
- Calcular . La curva elíptica E está entonces en forma de Weierstrass dada por y al usar coordenadas proyectivas, la curva elíptica viene dada por la ecuación homogénea . Tiene el punto.
- Elija un límite superior para esta curva elíptica. Observación: sólo encontrará factores p si el orden de grupo de la curva elíptica E sobre (denotado por ) es B-suave , lo que significa que todos los factores primos detiene que ser menor o igual a B .
- Calcular .
- Calcular ( k veces) en el ring. Tenga en cuenta que sies B -suave yn es primo (y por lo tanto es un campo) que . Sin embargo, si soloes B-suave para algún divisor p de n , el producto podría no ser (0: 1: 0) porque la suma y la multiplicación no están bien definidas si n no es primo. En este caso, se puede encontrar un divisor no trivial.
- De lo contrario, vuelva al paso 2. Si esto ocurre, lo notará al simplificar el producto.
En el punto 5 se dice que en las circunstancias adecuadas se puede encontrar un divisor no trivial. Como se señaló en el artículo de Lenstra (Factorizar enteros con curvas elípticas), la adición necesita la suposición. Si no son y distinta (de lo contrario, la adición funciona de manera similar, pero es un poco diferente), entonces la adición funciona de la siguiente manera:
- Calcular: ,
- ,
- ,
- ,
- .
Si la suma falla, esto se debe a una falla en el cálculo En particular, porque no siempre se puede calcular si n no es primo (y por lo tantono es un campo). Sin hacer uso de siendo un campo, se podría calcular:
- ,
- ,
- ,
- y simplificar si es posible.
Este cálculo es siempre legal y si el mcd de la coordenada Z con n ≠ (1 o n ), entonces cuando la simplificación falla, se encuentra un divisor no trivial de n .
Curvas retorcidas de Edwards
El uso de curvas de Edwards necesita menos multiplicaciones modulares y menos tiempo que el uso de curvas de Montgomery o curvas de Weierstrass (otros métodos utilizados). Usando las curvas de Edwards también puede encontrar más números primos.
Definición. Dejar ser un campo en el que , y deja con . Luego, la retorcida curva de Edwards es dado por Una curva de Edwards es una curva de Edwards retorcida en la que .
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 completados.
El conjunto de puntos afines viene dado por:
- .
La ley de la suma viene dada por
El punto (0,1) es su elemento neutro y el inverso de es .
Las otras representaciones se definen de manera similar a cómo la curva proyectiva de Weierstrass se sigue de la afín.
Cualquier curva elíptica en la forma de Edwards tiene un punto de orden 4. Por lo tanto, el grupo de torsión de una curva de Edwards sobre es isomorfo a cualquiera o .
Los casos más interesantes para ECM son y , ya que obligan a que los órdenes de grupo de los módulos primos de la curva sean divisibles por 12 y 16 respectivamente. Las siguientes curvas tienen un grupo de torsión isomorfo a:
- con punto dónde y
- con punto dónde y
Cada curva de Edwards con un punto de orden 3 se puede escribir de las formas que se muestran arriba. Curvas con grupo de torsión isomorfo a y puede ser más eficiente para encontrar números primos. [2]
Etapa 2
El texto anterior trata sobre la primera etapa de la factorización de la curva elíptica. Allí se espera encontrar un divisor primo p tal que es el elemento neutral de . En la segunda etapa se espera haber encontrado un divisor primo q tal que tiene un pequeño primer orden en .
Esperamos que el orden esté entre y , dónde se determina en la etapa 1 y es el nuevo parámetro de la etapa 2. Comprobando una pequeña orden de, se puede hacer computando módulo n para cada primo l .
GMP-ECM y EECM-MPFQ
Bernstein et al [2] utilizaron el uso de curvas elípticas Twisted Edwards, así como otras técnicas, para proporcionar una implementación optimizada de ECM. Su único inconveniente es que funciona con números compuestos más pequeños que la implementación de propósito más general, GMP-ECM de Zimmerman.
Método de la curva hiperelíptica (HECM)
Hay avances recientes en el uso de curvas hiperelípticas para factorizar números enteros. Cosset muestra en su artículo (de 2010) que se puede construir una curva hiperelíptica con el género dos (por lo que una curvacon f de grado 5), lo que da el mismo resultado que usar dos curvas elípticas "normales" al mismo tiempo. Al hacer uso de la superficie Kummer, el cálculo es más eficiente. Las desventajas de la curva hiperelíptica (frente a una curva elíptica) se compensan con esta forma alternativa de cálculo. Por lo tanto, Cosset afirma aproximadamente que usar curvas hiperelípticas para la factorización no es peor que usar curvas elípticas.
Versión cuántica (GEECM)
Bernstein , Heninger , Lou y Valenta sugieren GEECM, una versión cuántica de ECM con curvas de Edwards. [3] Utiliza el algoritmo de Grover para duplicar aproximadamente la longitud de los números primos encontrados en comparación con el EECM estándar, asumiendo una computadora cuántica con suficientes qubits y de velocidad comparable a la computadora clásica que ejecuta EECM.
Ver también
- UBASIC para programa práctico (ECMX).
Referencias
- ^ 50 factores más grandes encontrados por ECM .
- ↑ a b Berstein, Daniel J .; Birkner, Peter; Lange, Tanja ; Peters, Christiane (9 de enero de 2008). "ECM usando curvas de Edwards" (PDF) . Archivo ePrint de criptología . (consulte la parte superior de la página 30 para ver ejemplos de tales curvas)
- ^ Bernstein DJ, Heninger N., Lou P., Valenta L. (2017) RSA post-cuántica . En: Lange T., Takagi T. (eds), Criptografía post-cuántica . PQCrypto 2017. Lecture Notes in Computer Science, vol 10346. Springer, Cham
- Bernstein, Daniel J .; Birkner, Peter; Lange, Tanja; Peters, Christiane (2013). "ECM usando curvas de Edwards". Matemáticas de la Computación . 82 (282): 1139-1179. doi : 10.1090 / S0025-5718-2012-02633-0 . Señor 3008853 .
- Bosma, W .; Hulst, MPM van der (1990). Demostración de la primacía con ciclotomía . Doctor. Tesis, Universiteit van Amsterdam. OCLC 256778332 .
- Brent, Richard P. (1999). "Factorización del décimo número de Fermat" . Matemáticas de la Computación . 68 (225): 429–451. Código Bibliográfico : 1999MaCom..68..429B . doi : 10.1090 / S0025-5718-99-00992-8 . Señor 1489968 .
- Cohen, Henri (1993). Un curso de teoría de números algebraicos computacionales . Textos de Posgrado en Matemáticas. 138 . Berlín: Springer-Verlag. doi : 10.1007 / 978-3-662-02945-9 . ISBN 978-0-387-55640-6. Señor 1228206 .
- Cosset, R. (2010). "Factorización con curvas de género 2". Matemáticas de la Computación . 79 (270): 1191–1208. arXiv : 0905.2325 . Código Bibliográfico : 2010MaCom..79.1191C . doi : 10.1090 / S0025-5718-09-02295-9 . Señor 2600562 .
- Lenstra, AK ; Lenstra Jr., HW, eds. (1993). El desarrollo del tamiz de campo numérico . Apuntes de clase en matemáticas. 1554 . Berlín: Springer-Verlag. doi : 10.1007 / BFb0091534 . ISBN 978-3-540-57013-4. Señor 1321216 .
- Lenstra Jr., HW (1987). "Factorizar enteros con curvas elípticas" (PDF) . Annals of Mathematics . 126 (3): 649–673. doi : 10.2307 / 1971363 . hdl : 1887/2140 . JSTOR 1971363 . Señor 0916721 .
- Pomerance, Carl ; Crandall, Richard (2005). Números primos: una perspectiva computacional (Segunda ed.). Nueva York: Springer. ISBN 978-0-387-25282-7. Señor 2156291 .
- Pomerance, Carl (1985). "El algoritmo de factorización de tamiz cuadrático". Avances en criptología, Proc. Eurocrypt '84 . Apuntes de conferencias en Ciencias de la Computación. 209 . Berlín: Springer-Verlag. págs. 169-182. doi : 10.1007 / 3-540-39757-4_17 . ISBN 978-3-540-16076-2. Señor 0825590 .
- Pomerance, Carl (1996). "Historia de dos tamices" (PDF) . Avisos de la Sociedad Matemática Estadounidense . 43 (12): 1473–1485. Señor 1416721 .
- Silverman, Robert D. (1987). "El tamiz cuadrático polinomial múltiple" . Matemáticas de la Computación . 48 (177): 329–339. doi : 10.1090 / S0025-5718-1987-0866119-8 . Señor 0866119 .
- Trappe, W .; Washington, LC (2006). Introducción a la criptografía con teoría de la codificación (Segunda ed.). Saddle River, Nueva Jersey: Pearson Prentice Hall. ISBN 978-0-13-186239-5. Señor 2372272 .
- Samuel S. Wagstaff, Jr. (2013). La alegría de la factorización . Providence, RI: Sociedad Matemática Estadounidense. págs. 173–190. ISBN 978-1-4704-1048-3.
- Watras, Marcin (2008). Criptografía, análisis numérico y números muy grandes . Bydgoszcz: Wojciechowski-Steinhagen. PL: 5324564.
enlaces externos
- Factorización utilizando el método de curva elíptica , un subprograma de Java que utiliza ECM y cambia al tamiz cuadrático de autoinicialización cuando es más rápido.
- GMP-ECM , una implementación eficiente de ECM.
- ECMNet , una sencilla implementación cliente-servidor que funciona con varios proyectos de factorización.
- pyecm , una implementación de Python de ECM. Mucho más rápido con psyco y / o gmpy.
- Proyecto de computación distribuida yoyo @ Home Subproject ECM es un programa para factorización de curvas elípticas que es utilizado por un par de proyectos para encontrar factores para diferentes tipos de números.
- Código fuente del algoritmo de factorización de curva elíptica de Lenstra Código fuente del algoritmo de factorización de curva elíptica simple C y GMP.
- EECM-MPFQ Una implementación de ECM usando curvas de Edwards escritas con la biblioteca de campos finitos MPFQ.