La factorización de grandes enteros:

Para un entero «no demasiado grande», es bastante fácil obtener su descomposición en producto de factores primos mediante divisiones sucesivas entre números primos (que se han identificado como divisores o, si no, sistemáticamente en orden creciente). Por ejemplo, 45 = 5 × 9 = 5 × 3² o, de forma más sistemática, 4 851 = 3 ×1 617 = 3 × 3 ×539 = 3² × 7 ×77 = 3² × 7² × 11. Este método alcanza pronto sus límites en el caso de un número compuesto cuyos factores primos sean relativamente «grandes»: los criterios de divisibilidad de los enteros dejan de ayudar y el método de división sistemática entre números primos crecientes alarga considerablemente el procedimiento. Hoy, gracias a los ordenadores y a métodos más refinados, se pueden factorizar enteros de alrededor de cien cifras; sin embargo, todavía no existen algoritmos de factorización suficientemente eficientes para hacerlo mucho mejor en un tiempo razonable (el mayor entero, producto de dos números primos, factorizado hasta la fecha solo tiene doscientas cincuenta cifras).

En la raíz del problema -----------------------

Ya en el XVII^e siglo encontramos, en la correspondencia entre Marin Mersenne y Pierre de Fermat, problemas de factorización de enteros de hasta doce cifras: en una época en la que no existían las calculadoras, ¡es bastante notable! Así, en una carta de 1643 que Fermat dirige a Mersenne, se plantea si el número 2 027 651 281 es primo o compuesto y, en este último caso, cómo se descompone en factores primos. Esta carta nos proporciona además valiosos indicios sobre el estado de la aritmética de la época y su evolución hacia una teoría de números moderna, de la que puede considerarse a Fermat fundador.

El método de factorización expuesto por Fermat se apoya esencialmente en la siguiente propiedad: el producto de dos números impares siempre puede escribirse como diferencia de dos cuadrados. En efecto, si p y q (con p > q) son dos enteros impares, su suma y su diferencia son pares, lo que permite escribir $pq={\left(\frac{p+q}{2}\right)}^2-{\left(\frac{p-q}{2}\right)}^2\mathrm{.}pq=\backslash left\; (\; \backslash frac\{p+q\}\{2\}\; \backslash right\; )^2-\; \backslash left\; (\; \backslash frac\{p-q\}\{2\}\; \backslash right\; )^2.$

Como R² – S² = (R – S)(R + S), se sigue que, si un entero impar N es compuesto, existen enteros R y S tales que N = (R – S)(R + S). Esta propiedad puede conducir, por tanto, a un método general de descomposición: como todos los números primos (salvo el 2) son impares, todo entero compuesto tiene la forma 2*^k N (k* un número natural), con N impar, que, si no es primo, podrá escribirse como diferencia de dos cuadrados y, por tanto, factorizarse. Si los factores hallados son primos, la descomposición está completa; de lo contrario, se procede del mismo modo con los factores que aún puedan descomponerse.

Pero, dado un entero impar N, ¿cómo determinar R y S tales que N = R² – S² ? La idea consiste en buscar R a partir de la parte entera de $\sqrt{\mathrm{N}}\backslash sqrt\{\backslash rm\{N\}\}$, que denotaremos por c, mediante incrementos sucesivos: R = c + k, con k = 1, 2, 3… (R es necesariamente mayor que $\sqrt{\mathrm{N}}\backslash sqrt\{\backslash rm\{N\}\}$, puesto que N = R² – S²). Como N = R² – S² = (c + k)² – S², (c + k)² – N debe ser un cuadrado (igual a S²): esa es la condición de parada del bucle de incremento. Hallado el entero k, también se obtiene R = (c + k), y lo mismo ocurre con S (es la raíz cuadrada de (c + k)² – N): ¡el problema está resuelto!

Algunos trucos de cálculo permiten a Fermat hacer que su algoritmo sea menos laborioso de lo que parece: la cantidad que hay que comprobar, (c + k)² – N, se calcula para k = 1 observando que, para un entero r, (c + 1)² – (c² + r) = (c² + 2c + 1) – (c² + r) = 2c + 1 – r, expresión mucho más fácil de calcular «a mano» que la expresión inicial cuando c es «grande». A continuación, Fermat aprovecha que (c + k + 1)² – N = (c + k)² – N + (2c + 1 + 2k) para pasar de un valor de k al siguiente.

Veamos qué ocurre con el entero mencionado en la carta: N = 2 027 651 281. Empezamos extrayendo la raíz cuadrada de N y nos detenemos en su parte entera; obtenemos c = 45 029 y un resto r = 40 440 (es decir, 2 027 651 281 = 45 029² + 40 440). Calculamos entonces 2c + 1 – r, que es la cantidad que hay que comprobar en la etapa k = 1; obtenemos 49 619. Este número no es un cuadrado porque, dice Fermat, «ningún cuadrado termina en 19» (véase el recuadro). Pasamos, pues, a k = 2, añadiendo 2c + 1 + 2 = 90 061 a 49 619. Obtenemos 139 680, que tampoco es un cuadrado. Para k = 3: 139 680 + 90 063 = 229 743 no es un cuadrado. Para k = 4: 229 743 + 90 065 = 319 808 no es un cuadrado… La carta de Fermat nos informa de que tuvo que continuar hasta k = 12 (¡compruébelo!) para hallar 1 040 400, que es el cuadrado de 1 020. Así obtenemos R = c + 12 = 45 041, S = 1 020 y, por tanto, N = (R – S)(R + S) = 44 021 × 46 061. La descomposición termina aquí, ya que 44 021 y 46 061 son números primos (lo que puede comprobarse mediante la criba de Eratóstenes; véase el recuadro «Fermat, Mersenne y los números primos»).

en Beaumont-de-Lomagne, en Tarn y Garona.

Un método realmente eficaz -----------------------------

El método de Fermat permite así factorizar eficazmente el número N = 2 027 651 281: el algoritmo concluye en relativamente pocos pasos (12). Si se hubieran buscado los factores primos de N = 2 027 651 281 por la «vía ordinaria», es decir, mediante divisiones sucesivas entre números primos crecientes, habría sido necesario, escribe Fermat, «dividir entre todos los números desde 7 hasta 44 021». ¡En efecto, su algoritmo lo hace mucho mejor! Pero esto se debe a que los dos factores primos p y q que componen N están «bastante próximos» entre sí. El método propuesto por Fermat parte de $c=\left[\sqrt{pq}\right]c=\backslash left\; [\backslash sqrt\{pq\}\backslash right\; ]$, es decir, de la parte entera de la media geométrica de los dos factores, para avanzar hacia R = (p + q) / 2, su media aritmética. La diferencia entre estas dos medias da una idea de la longitud del algoritmo de Fermat; por desgracia, cuanto más se alejan entre sí p y q, más aumenta esa diferencia…

No obstante, este método de factorización siguió siendo hasta la década de 1970 el más eficaz para factorizar enteros bien elegidos. Fue mejorado en 1981 por el estadounidense Carl Pomerance (nacido en 1944), mediante un algoritmo llamado criba cuadrática, en el que se buscan R y S tales que N divida R² – S² (mientras que en el método de Fermat R y S son tales que N = R² – S²). Este algoritmo permitió, en 1994, gracias a varios cientos de ordenadores y meses de esfuerzo, factorizar el número RSA-129, un número de ciento veintinueve cifras producto de dos grandes números primos.

Un desafío entre sabios ---------------------

En otra carta fechada en 1643, Fermat se enfrenta a algo más difícil, con N = 100 895 598 169, a raíz de la petición formulada por Mersenne de «un método para descubrir en el plazo de un día si es primo o compuesto» (la correspondencia entre los sabios de la época tenía a menudo algo de justa intelectual…). Fermat rara vez explicaba cómo obtenía sus resultados, lo que mantuvo ocupados a muchos matemáticos demostrándolos, ¡hasta el XX^e siglo! Fiel a esta práctica, respondió, sin más explicación, que el número propuesto por su corresponsal es producto de 898 423 y 112 303, que, añade, son primos.

¿Habría utilizado Fermat también en este caso el algoritmo anterior? ¡Seguro que no! Una implementación informática de este algoritmo muestra, en efecto, que habría tenido que llegar hasta k = 187 723. Se ve hasta qué punto es exigente la condición de proximidad entre los dos factores: 898 423 y 112 303 están demasiado «alejados» entre sí para poder encontrarlos en un tiempo «razonable» con este método. Entonces, ¿qué nuevo método pudo emplear Fermat para superar el desafío planteado por Mersenne?

Resulta que Fermat se interesó por números particulares: los números perfectos (iguales a la suma de sus divisores propios, como 28, igual a 1 + 2 + 4 + 7 + 14) y los números multiperfectos (enteros para los que la suma de sus divisores propios es un múltiplo del entero, como 120, cuya suma de divisores propios vale 360, es decir, 3 × 120). Todos estos números fueron estudiados por Euclides y después por Descartes. Ahora bien, otro pasaje de esta segunda carta deja patente que Mersenne se interesa por la factorización de un número N, supuesto multiperfecto (probablemente Frénicle sugirió este número). La descomposición de N en factores primos está establecida… o casi, pues cierto factor resulta más complicado de analizar que los demás: se trata precisamente de 100 895 598 169. ¿Es primo este entero? ¡No hay más que preguntárselo a Fermat!

Fermat aborda el problema, que muy probablemente trata a partir de consideraciones sobre las propiedades de los números multiperfectos. Su razonamiento pudo haber sido el siguiente: si N es k-perfecto, es decir, si la suma σ (N) de sus divisores propios vale kN, con k «pequeño», entonces los factores primos «grandes» de σ (N) y de N son los mismos. Pues bien, 616 318 177 aparece en la descomposición de N; por tanto, el número σ (616 318 177) aparece en la de σ (N), con σ (616 318 177) = 616 318 177 + 1. La descomposición de 616 318 178 es 2 × 73 × 898 423, siendo 898 423 primo; este último número es, por tanto, también un factor primo de N. Como no aparece en la descomposición inicial, debe de ser un factor de 100 895 598 169. Una última división puede conducir a la factorización buscada: 100 895 598 169 = 898 423 × 112 303. De forma menos laboriosa, también puede reutilizarse el razonamiento anterior para encontrarla: σ (898 423) = 898 424 = 23 × 112 303; como 112 303 tampoco aparece en la descomposición inicial de N, también es un factor primo de 100 895 598 169. ¡Y asunto resuelto!

La factorización sigue siendo difícil, ¡menos mal! ----------------------------------------------

En el XVII^e siglo, saber factorizar enteros muy grandes probablemente no tenía otro interés que demostrar a sus pares su ingenio para el cálculo. Hoy, esta cuestión se ha vuelto crucial: ¡todo un sector de la seguridad digital se basa en la dificultad de resolver un problema de factorización de este tipo! Actualmente sabemos generar números tan difíciles de factorizar que, incluso si dedicáramos la potencia de todos nuestros ordenadores a esta única tarea, no lograríamos resolverla en un tiempo razonable. Lejos de ser una contrariedad, esta dificultad se halla en el núcleo mismo del sistema de cifrado más utilizado hoy: el sistema RSA, inventado en 1977 por Ronald Linn Rivest (nacido en 1947), Adi Shamir (nacido en 1952) y Leonard Adleman (nacido en 1945), y generalizado como clave de cifrado a finales de la década de 1990, con la llegada de Internet. Se trata de un código asimétrico, con una clave conocida por todos para cifrar los mensajes, llamada clave pública, y una clave conocida solo por el destinatario para descifrarlos, llamada clave privada. La ventaja de este tipo de código asimétrico es que la clave privada no circula por ningún canal de comunicación.

En el sistema de cifrado RSA, la clave pública es un número N producto de dos factores primos p y q «muy grandes» que no es necesario conocer para cifrar el mensaje (véase el recuadro), mientras que el descifrado requiere no solo conocer N, sino también los dos factores p y q. Se comprende entonces que, si N es «suficientemente grande» y p y q están bien elegidos, dadas las limitaciones actuales de la factorización, un sistema de cifrado así es en la práctica inexpugnable. Hoy se estima que usar un número N de unas seiscientas cifras (p y q tienen unas trescientas cifras cada uno) nos protege de cualquier amenaza durante varias decenas de años (actualmente no sabemos hacer más que factorizar un número de doscientas cincuenta cifras).

Este texto procede de la conferencia impartida por Daniel Perrin el miércoles 14 de marzo de 2018 en la Biblioteca Nacional de Francia, dentro del ciclo «Un texto, un matemático».