Factorización IV: El Método de Curva Elíptica

El siguiente artículo es el cuarto de una serie dedicada a la factorización de números enteros. Hasta ahora se han visto los algoritmos básicos de factorización como Pollard P-1, que aunque pueden parecer rápidos, tienen complejidad exponencial, lo que los incapacita para factorizar números relativamente grandes. También se han introducido algunos de los conceptos necesarios para profundizar en el tema que nos permitirán, en este artículo y en los siguientes, estudiar los tres algoritmos más rápidos de factorización. Estos son el Método de Curva Elíptica (ECM), La Criba Cuadrática (QS) y la Criba en el Campo de Números (NFS), los tres de complejidad subexponencial. Empezaremos por el Método de Curva Elíptica.

En el artículo Criptografía de Curva Elíptica dimos una introducción a este peculiar tipo de curvas y su aplicación a la criptografía. A continuación iremos un poco más lejos y veremos como aprovechar esta herramienta matemática para factorizar números enteros grandes.

Para entender el siguiente artículo es necesario disponer de unos conocimientos básicos de curvas elípticas. En caso contrario, es recomendable leer primero el artículo mencionado anterioremente.


El Teorema de Lagrange:

Si aplicamos el Teorema de Lagrange a las curvas elípticas no encontramos con algo interesante que nos conducizará al método de factorización mediante curvas elípticas.

Si P es un punto en una curva elíptica E, entonces el orden de P dividirá el orden de E.

Recordemos que el orden de E, representado como #E, corresponde al número de puntos que hay en una curva E. Mientras que el orden de P, corresponde al valor k más pequeño (diferente de O) tal que kP = O.


Imaginemos que queremos factorizar un número N. Si encontramos una curva E definida sobre N, cuyo orden sea B-smooth, para un valor de B suficientemente pequeño, nos encontraremos con que B!P = O.

Esto ocurre debido a que #E es B-smooth y el orden de P debe ser un divisor de #E, tal y como nos indica el Teorema de Lagrange.


Factorización:

Encontrar un valor k tal que kP=O, en una curva mod N, es equivalente a encontrar un factor de N.

Esto ocurre por que durante el proceso de cálculo de kP se realizan operaciones que necesitan que cierto número d tenga inversa d^(-1). Para que d sea invertible debe cumplirse que el máximo común divisor entre d i el módulo sea igual a 1.

Pero ¿qué ocurre si d no tiene inversa? pues que el máximo común divisor entre d y el módulo N es diferente de 1. Con lo que tenemos un factor de N!


Imaginemos que queremos factorizar 4453. En este caso buscaríamos curvas aleatorias hasta encontrar una cuyo orden fuese B-smooth. Por ejemplo y²=x³+10x-2 mod 4453.

Ahora calcularíamos, kP para un valor pequeño de K. Empezemos por 2P para, por ejemplo P=(1,3).

(3x²+10) / 2y = 13 / 6 mod 4453 (derivada)

Para calcular 13/6 necesitamos calcular 6^(-1). Dado que MCD(6, 4452) podemos hacerlo: 6^(-1) = 3711, con lo que obtenemos:

13 / 6 = 3713 mod 4453
x = 3713²-2 = 4332
y = -3713(x-1)-3 = 3230

Para calcular 3P hacemos 2P + P:

(3230-3) / (4332-1) = 3227/4331.

Igual que en el cálculo anterior, para poder calcular 3227/4331 es necesario que 4331 tenga inversa, es decir, que MCD(4331, 4453) sea 1. Pero si realizamos el cálculo vemos que MCD(4331, 4453)=61. Con lo que hemos encontrado un factor de N.



Complejidad:

El método de factorización mediante curvas elípticas és muy rápido. De hecho, cuando deseamos factorizar números enteros grandes i sabemos que undo de los factores es mucho menor que el otro, este método es el más rápido.

Veamos a continuación por que és tan rápido.

El teorema de Hasse nos dice que el orden #E satisface la siguiente ecuación:

p+1-2 sqr(p) < #E < p+1-2 sqr(p)

Esto nos da una cierta idea del intervalo en el que puede moverse el valor #E. De esta manera sabemos que al generar una curva aleatoria, estamos obteniendo un valor entre este rango, de manera que si es B-smooth, conseguiremos factorizar N.

El número estimado de operaciones que necesitaremos realizar para encontrar una curva B-smooth es el siguiente:

exp(sqr(2) + O(1) + sqr(lnp ln lnp)

Como vemos, el número de operaciones necesarias es subexponencial, esto proviene del hecho de que la complejidad de encontrar números smooth es también subexponencial. Lo mismo ocurre con los algoritmos QS y NFS.



Software:

Actualmente la implementación libre más rápida de ECM es GMP-ECM, disponible en:

http://www.komite.net/laurent/soft/ecm/



Referencias:
- Elliptic Curves, Number Theory and Cryptography. Lawrence C. Washington.
- Prime Numbers, A Computational Perspective. Crandall & Pomerance.