Factorización de curva elíptica de Lenstra - Lenstra elliptic-curve factorization

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 más adecuado para encontrar factores pequeños. Actualmente, 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 número 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 curva elíptica de Lenstra para encontrar un factor de un número natural dado funciona de la siguiente manera: ${\ Displaystyle n}$

1. Escoja al azar curva elíptica sobre , la ecuación de la forma junto con un no trivial punto en él. ${\ Displaystyle \ mathbb {Z} / n \ mathbb {Z}}$${\ Displaystyle y ^ {2} = x ^ {3} + ax + b {\ pmod {n}}}$ ${\ Displaystyle P (x_ {0}, y_ {0})}$

   Esto se puede hacer seleccionando primero al azar y luego configurándolo para asegurar que el punto esté en la curva.${\ Displaystyle x_ {0}, y_ {0}, a \ in \ mathbb {Z} / n \ mathbb {Z}}$${\ Displaystyle b = y_ {0} ^ {2} -x_ {0} ^ {3} -ax_ {0} {\ pmod {n}}}$

2. 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 repetidas de un punto : . Las fórmulas de adición implican tomar la pendiente modular de una cuerda que se une y , por lo tanto, la división entre clases de residuos módulo , realizada utilizando el algoritmo euclidiano extendido . En particular, la división por algunos incluye el cálculo del .${\ Displaystyle P}$${\ Displaystyle [k] P = P + \ ldots + P {\ text {(k veces)}}}$${\ Displaystyle P}$${\ displaystyle Q}$${\ Displaystyle n}$${\ Displaystyle v {\ bmod {n}}}$${\ Displaystyle \ gcd (v, n)}$

   Suponiendo que calculamos una pendiente de la forma con , entonces si , 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, lo que es más importante, es un factor no trivial de .${\ Displaystyle u / v}$${\ Displaystyle \ gcd (u, v) = 1}$${\ Displaystyle v = 0 {\ bmod {n}}}$${\ Displaystyle \ infty}$${\ Displaystyle P (x, y), P '(x, -y)}$${\ Displaystyle \ gcd (v, n) \ neq 1, n}$${\ Displaystyle \ gcd (v, n)}$${\ Displaystyle n}$

3. Calcule sobre la curva elíptica ( ), donde 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. Digamos, para obtener , primero calcular , luego , luego , y así sucesivamente. se elige para que sea lo suficientemente pequeño para que la adición de puntos en sentido común se pueda realizar en un tiempo razonable. ${\ Displaystyle [k] P}$${\ Displaystyle {\ bmod {n}}}$${\ Displaystyle k}$ ${\ Displaystyle B!}$${\ Displaystyle B}$${\ displaystyle [B!] P}$${\ Displaystyle [2] P}$${\ Displaystyle [3] ([2] P)}$${\ displaystyle [4] ([3!] P)}$${\ Displaystyle B}$${\ Displaystyle B}$
   • 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.${\ Displaystyle {\ bmod {n}}}$
4. Si nos encontramos con un hemos terminado: es un factor no trivial de .${\ Displaystyle \ gcd (v, n) \ neq 1, m}$${\ Displaystyle n}$

La complejidad del tiempo depende del tamaño del factor primo más pequeño del número y se puede representar mediante 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 . ${\ Displaystyle L_ {p} \ left [{\ frac {1} {2}}, {\ sqrt {2}} \ right]}$

¿Por qué funciona el algoritmo?

Si p y q son dos divisores primos de n , entonces y ²  =  x ³  + 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 la adición-ahora son grupos genuinos . Si estos grupos tienen N _p y N _q elementos, respectivamente, entonces para cualquier punto P en la curva original, por el teorema de Lagrange , k  > 0 es mínimo tal que en la curva módulo p implica que k divide N _p ; Por otra parte, . La declaración análoga es válida para la curva módulo q . Cuando la curva elíptica se elige al azar, entonces 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 .${\ Displaystyle \ boxplus}$${\ Displaystyle kP = \ infty}$${\ Displaystyle N_ {p} P = \ infty}$

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 ² = x ³ + 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 ² + 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 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) ² = 2809 = 14 ³ + 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 ⁻¹ = 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 ² = 54514 = x ³ + 5 x - 5 (mod 455839). Después de esto, podemos calcular . ${\ Displaystyle 3 (2P) = 4P \ boxplus 2P}$

¡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 ⁷ · 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 primero, considere 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 ; los puntos, denotados por , corresponden a líneas en un espacio tridimensional que pasan por el origen. Tenga en cuenta que el punto no 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 el plano ( X , Y , 1), mientras que las líneas exactamente paralelas a este plano, que tienen coordenadas ( X, Y , 0), especifican direcciones unívocamente, como 'puntos en el infinito' que se utilizan en el afín ( X, Y ) -plano sobre el que se encuentra. ${\ Displaystyle (\ mathbb {Z} / n \ mathbb {Z}) / \ sim,}$${\ Displaystyle (x, y, z)}$${\ Displaystyle (x, y, z) \ sim (x ', y', z ')}$ ${\ Displaystyle \ mathbb {P} ^ {2}}$${\ Displaystyle (x: y: z)}$${\ displaystyle (0: 0: 0)}$

En el algoritmo, solo se utiliza la estructura de grupo de una curva elíptica sobre el campo ℝ. Dado que no necesariamente necesitamos 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 con n que no es primo, no se obtiene un grupo. El método de la curva elíptica hace uso de los casos de falla de la ley de la adición. ${\ Displaystyle (\ mathbb {Z} / n \ mathbb {Z}) / \ sim}$

Ahora expresamos el algoritmo en coordenadas proyectivas. El elemento neutro viene dado por el punto en el infinito . Sea n un número entero (positivo) y considere la curva elíptica (un conjunto de puntos con alguna estructura) . ${\ displaystyle (0: 1: 0)}$${\ Displaystyle E (\ mathbb {Z} / n \ mathbb {Z}) = \ {(x: y: z) \ in \ mathbb {P} ^ {2} \ | \ y ^ {2} z = x ^ {3} + axz ^ {2} + bz ^ {3} \}}$

1. Elija con un ≠ 0.${\ Displaystyle x_ {P}, y_ {P}, a \ in \ mathbb {Z} / n \ mathbb {Z}}$
2. Calcular . La curva elíptica E está entonces en forma de Weierstrass dada por y usando coordenadas proyectivas, la curva elíptica viene dada por la ecuación homogénea . Tiene el punto .${\ Displaystyle b = y_ {P} ^ {2} -x_ {P} ^ {3} -ax_ {P}}$${\ Displaystyle y ^ {2} = x ^ {3} + ax + b}$${\ Displaystyle ZY ^ {2} = X ^ {3} + aZ ^ {2} X + bZ ^ {3}}$${\ Displaystyle P = (x_ {P}: y_ {P}: 1)}$
3. Elija un límite superior para esta curva elíptica. Observación: sólo encontrará factores p si el orden del grupo de la curva elíptica E sobre (denotado por ) es B-alisar , lo que significa que todos los factores primos de tienen que ser menor o igual a B .${\ Displaystyle B \ in \ mathbb {Z}}$${\ Displaystyle \ mathbb {Z} / p \ mathbb {Z}}$${\ Displaystyle \ #E (\ mathbb {Z} / p \ mathbb {Z})}$${\ Displaystyle \ #E (\ mathbb {Z} / p \ mathbb {Z})}$
4. Calcular .${\ Displaystyle k = {\ rm {lcm}} (1, \ dots, B)}$
5. Calcula ( k veces) en el anillo . Tenga en cuenta que si es B -suave y n es primo (y por lo tanto es un campo) eso . Sin embargo, si solo B es 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.${\ Displaystyle kP: = P + P + \ cdots + P}$${\ Displaystyle E (\ mathbb {Z} / n \ mathbb {Z})}$${\ Displaystyle \ #E (\ mathbb {Z} / n \ mathbb {Z})}$${\ Displaystyle \ mathbb {Z} / n \ mathbb {Z}}$${\ Displaystyle kP = (0: 1: 0)}$${\ Displaystyle \ #E (\ mathbb {Z} / p \ mathbb {Z})}$
6. De lo contrario, vuelva al paso 2. Si esto ocurre, lo notará al simplificar el producto. ${\ Displaystyle kP.}$

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 suma necesita la suposición . Si no son y son distintos (de lo contrario, la adición funciona de manera similar, pero es un poco diferente), la adición funciona de la siguiente manera: ${\ Displaystyle \ gcd (x_ {1} -x_ {2}, n) = 1}$${\ Displaystyle P, Q}$${\ displaystyle (0: 1: 0)}$

• 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_ {3} = \ lambda (x_ {1} -x_ {3}) - y_ {1}}$,
• ${\ Displaystyle R = P + Q = (x_ {3}: y_ {3}: 1)}$.

Si la suma falla, será debido a una falla en el cálculo. En particular, porque no siempre se puede calcular si n no es primo (y por lo tanto no es un campo). Sin hacer uso de ser un campo, se podría calcular: ${\ Displaystyle \ lambda.}$${\ Displaystyle (x_ {1} -x_ {2}) ^ {- 1}}$${\ Displaystyle \ mathbb {Z} / n \ mathbb {Z}}$${\ Displaystyle \ mathbb {Z} / n \ mathbb {Z}}$

• ${\ Displaystyle \ lambda '= y_ {1} -y_ {2}}$,
• ${\ Displaystyle x_ {3} '= {\ lambda'} ^ {2} -x_ {1} (x_ {1} -x_ {2}) ^ {2} -x_ {2} (x_ {1} -x_ {2}) ^ {2}}$,
• ${\ Displaystyle y_ {3} '= \ lambda' (x_ {1} (x_ {1} -x_ {2}) ^ {2} -x_ {3} ') - y_ {1} (x_ {1} - x_ {2}) ^ {3}}$,
• ${\ 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 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. Vamos a ser un campo en el que , y dejar con . Entonces, la curva de Edwards torcida viene dada por Una curva de Edwards es una curva de Edwards torcida en la que . ${\ Displaystyle k}$${\ Displaystyle 2 \ neq 0}$${\ Displaystyle a, d \ in k \ setminus \ {0 \}}$${\ Displaystyle a \ neq d}$${\ Displaystyle E_ {E, a, d}}$${\ Displaystyle ax ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2}.}$${\ 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 completados.

El conjunto de puntos afines viene dado por:

${\ Displaystyle \ {(x, y) \ in \ mathbb {A} ^ {2}: ax ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2} \}}$.

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 neutro y el inverso de es . ${\ Displaystyle (e, f)}$${\ Displaystyle (-e, f)}$

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 es isomorfo a o . ${\ Displaystyle \ mathbb {Q}}$${\ Displaystyle \ mathbb {Z} / 4 \ mathbb {Z}, \ mathbb {Z} / 8 \ mathbb {Z}, \ mathbb {Z} / 12 \ mathbb {Z}, \ mathbb {Z} / 2 \ mathbb {Z} \ times \ mathbb {Z} / 4 \ mathbb {Z}}$${\ Displaystyle \ mathbb {Z} / 2 \ mathbb {Z} \ times \ mathbb {Z} / 8 \ mathbb {Z}}$

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 : ${\ Displaystyle \ mathbb {Z} / 12 \ mathbb {Z}}$${\ Displaystyle \ mathbb {Z} / 2 \ mathbb {Z} \ times \ mathbb {Z} / 8 \ mathbb {Z}}$${\ Displaystyle \ mathbb {Z} / 12 \ mathbb {Z}}$

• ${\ Displaystyle x ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2}}$con punto donde y${\ Displaystyle (a, b)}$${\ Displaystyle b \ notin \ {- 2, -1 / 2,0, \ pm 1 \}, a ^ {2} = - (b ^ {2} + 2b)}$${\ Displaystyle d = - (2b + 1) / (a ​​^ {2} b ^ {2})}$
• ${\ Displaystyle x ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2}}$con punto donde y${\ Displaystyle (a, b)}$${\ Displaystyle a = {\ frac {u ^ {2} -1} {u ^ {2} +1}}, b = - {\ frac {(u-1) ^ {2}} {u ^ {2 } +1}}}$${\ Displaystyle d = {\ frac {(u ^ {2} +1) ^ {3} (u ^ {2} -4u + 1)} {(u-1) ^ {6} (u + 1) ^ {2}}}, u \ notin \ {0, \ pm 1 \}.}$

Cada curva de Edwards con un punto de orden 3 se puede escribir de las formas que se muestran arriba. Las curvas con un grupo de torsión isomórfico y pueden ser más eficientes para encontrar números primos. ${\ Displaystyle \ mathbb {Z} / 2 \ mathbb {Z} \ times \ mathbb {Z} / 8 \ mathbb {Z}}$${\ Displaystyle \ mathbb {Z} / 2 \ mathbb {Z} \ times \ mathbb {Z} / 4 \ mathbb {Z}}$

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 sea ​​el elemento neutral de . En la segunda etapa, se espera haber encontrado un divisor primo q tal que tenga un orden primo pequeño en . ${\ displaystyle sP}$${\ Displaystyle E (\ mathbb {Z} / p \ mathbb {Z})}$${\ displaystyle sP}$${\ Displaystyle E (\ mathbb {Z} / q \ mathbb {Z})}$

Esperamos que el orden esté entre y , donde se determina en la etapa 1 y es el nuevo parámetro de la etapa 2. Se puede verificar un pequeño orden de , calculando el módulo n para cada primer l . ${\ Displaystyle B_ {1}}$${\ Displaystyle B_ {2}}$${\ Displaystyle B_ {1}}$${\ Displaystyle B_ {2}}$${\ displaystyle sP}$${\ Displaystyle (ls) P}$

GMP-ECM y EECM-MPFQ

Bernstein et al 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 (es decir, una curva con f de grado 5), 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. ${\ Displaystyle y ^ {2} = f (x)}$

Versión cuántica (GEECM)

Bernstein , Heninger , Lou y Valenta sugieren GEECM, una versión cuántica de ECM con curvas de Edwards. 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

• 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 informática. 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 mediante 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.