Nuestro objetivo como matemáticos es encontrar el modo de romper los códigos, no de facilitarlos. Por ejemplo, un gran objetivo es encontrar modos eficientes de descomponer números en factores primos. Lo otro, encontrar primos suficientemente grandes para formar \(N=pq\) será muy útil pero no tiene valor matemático.
Gauss consideraba este un problema importante desde el punto de vista matemático:
El problema de distinguir los números primos de los compuestos, y de descomponer los números compuestos en factores primos es uno de los más importantes y útiles de toda la aritmética.
… La dignidad de la ciencia nos obliga a que cada vía para la solución de tan elegante y celebrado problema sea exhaustivamente investigada.
— C. F. Gauss, Disquisitiones Aritmeticae, 329 (1801).
La dignidad de la ciencia se ha visto últimamente pisoteada por el uso mercantil en la criptografía. Descomponer en factores se ha convertido en objetivo mercantil, militar o simplemente de poder. Es casi seguro que los últimos avances en el problema no son de dominio público. Hace unos días Google alerta de que los datos enviados hoy están ya en riesgo. Y desde ya, se pide que se usen nuevos algoritmos inmunes a los ordenadores cuánticos.
Solo podemos especular, ¿es que ya Google es capaz de encontrar los factores que encierran la llave para leer los mensajes? ¿es que ya tiene los ordenadores cuánticos? ¿conoce nuevos métodos de factorizar? Quizás Google primero ha suscitado el miedo a los futuros ordenadores cuánticos, con el solo objeto de vender sus métodos criptográficos inmunes a los posibles futuros ataques cuánticos. De influenciar a la agencia americana, el «Center for Cybersecurity Standard» a que fije los estándares de los nuevos sistemas de seguridad en aquellos desarrollados por Google.
Nosotros preferimos seguir en el espíritu de Gauss. Y en esta entrada tratamos de estudiar una de las posibles estrategias para descomponer un número en factores. Tan solo como una muestra de que hay muchas vías posibles y, como dice Gauss, la dignidad de la ciencia nos pide que las investiguemos. Nos llevará a plantear un problema probablemente más difícil que el original.
La herramienta básica: el máximo común divisor
Los Elementos de Euclides contienen varios capítulos dedicados a la aritmética. La notación de los griegos para los números no era muy eficiente. A falta de numerales nosotros representaríamos los números por montones de piedras o de puntos, ¡no Euclides!, Euclides los representa por segmentos. Quizás eso explique la búsqueda de la medida común. Dados dos segmentos encontrar otro que los mida exactamente. Así dados dos segmentos \(a>b\) toma el menor de los segmentos \(b\) y mide el grande. En general \(b\) no mide exactamente \(a\) (no es la medida común) y queda un resto \(r\), esto es \(a=nb+r\). Si hay un segmento que mida a \(b\) y a \(r\), también medirá a \(a\). Así que de buscar una medida común para el par segmentos \((a,b)\), he pasado a buscarla para \((b,r)\). Y ese proceso se puede iterar hasta que encontremos la medida común.
Es curioso que los primeros matemáticos pensaran que este algoritmo acabaría siempre encontrando la medida común en un número finito de pasos, para dos longitudes cualesquiera. Parece que Pitágoras no aceptó bien el descubrimiento de que había segmentos inconmensurables, quizás, como se ha dicho, aprovechó la ocasión para inventar el truco de eliminar al mensajero. Yo no creo que fuera tan irracional, hay mucho mito en todo esto.
En todo caso, con números naturales en lugar de segmentos, el algoritmo de Euclides acaba siempre en un número finito de pasos. Muchos de los métodos para romper en factores un número \(N\) lo que hacen es proporcionar otro número \(Q\) tal que el máximo común divisor \(d=\gcd(N,Q)\) cumpla \(1<d<N\). Será pues un divisor propio de \(N\). Como existen métodos rápidos de comprobar si un número es primo, reiterando el proceso llegamos a factorizar \(N\) completamente.
El problema de descomponer \(N\) en factores primos se reduce a otro más simple.
Dado un número \(N\), que sabemos que no es primo, encontrar un divisor propio de \(N\).
Por ejemplo si \(N\) no es primo, sabemos que el menor factor primo de \(N\) es \(p\le\sqrt{N}\). Por esto si tomamos \(M=Q!\) siendo \(Q\le\sqrt{N}<Q+1\), estamos seguros que el máximo común divisor de \(M\) y \(N\) $$d=\gcd(N, M)=\gcd(N,Q!),$$ es un divisor propio de \(N\), o bien todos los factores primos de \(N\) son menores que \(Q\), en ambos casos una información muy relevante.
El segundo caso es más simple, o bien \(Q^2=N\) y ya tenemos el divisor propio \(Q\), o bien el menor primo que divide a \(N\) es \(\le N^{1/3}\) y el problema se nos simplifica.
Algoritmo de factorización
Las ideas anteriores permiten construir un algoritmo para encontrar un factor propio de \(N\), o bien, probar que es primo.
En cada momento del algoritmo tendremos un par de números \(1\le a < b\le N\), tales que $$\gcd(a!,N)=1,\qquad \gcd(b!,N)=N.$$ y en el proceso iremos disminuyendo la distancia \(b-a\), mientras no encontremos un divisor propio o probemos que \(N\) es primo. Comenzamos con el par \(a=1\), \(b=N\). Buscamos el punto medio del intervalo, digamos que \(Q\), y calculamos \(d=\gcd(Q!, N)\). Veremos que \(d\) es un divisor propio, o bien el intervalo se reduce a la mitad. El algoritmo es el siguiente:
Por construcción mientras que el programa no devuelva \(f\), en cuyo caso es un divisor propio de \(N\), tendremos \(\gcd(a!, N)=1\) y \(\gcd(b!, N)=N\). Por tanto \(a<b\) y tendremos \(a<\frac{a+b}{2}< b\). Entonces \(a\le Q< b\). Un bucle infinito solo puede ocurrir si \(Q=a\), siendo \(a=Q=\lfloor (a+b)/2\rfloor <b\). Esto solo puede pasar si \(b=a+1\). De forma que no se produce bucle infinito, sino que se devuelve un \(1\) al salir del bucle «while». La situación en ese momento es que $$\gcd(a!, N)=1,\quad \gcd((a+1)!, N)=N.$$ Esto implica, como vemos fácilmente, que \(N=a+1\) es primo.
Luego el programa devuelve siempre un divisor de \(N\), devuelve \(1\) si \(N\) es primo y, en otro caso, devuelve un divisor propio.
Como en cada paso la longitud del intervalo \([a,b]\) se divide por \(2\) (esencialmente), el número de ciclos en el «while» es del orden de \(\log N\), el logaritmo de la longitud del intervalo en el momento inicial. El problema del algoritmo es que en cada paso hay que calcular \(\gcd(Q!, N)\) y, al menos en los primeros pasos, \(Q\) es del orden de \(N\), luego \(Q!\) es un número con \(N\log N\) dígitos aproximadamente.
Un buen algoritmo sería aquel que devolviera el divisor en un tiempo (es decir, número de pasos) del orden de \((\log N)^k\) con un \(k\) fijo. De este modo el tiempo que el algoritmo necesita para encontrar un factor crecería polinomialmente con la longitud \(\log N\) del número \(N\). Pero el algoritmo que hemos descrito solo en escribir el primer \(Q!\) tarda un tiempo exponencial (en \(\log N\)), ya que $$\log (Q!)\approx \log (N/2)!\approx \frac{N}{2}\log N=\frac12 (\log N)e^{\log N}.$$
¿Cómo modificar el programa?
El algoritmo de Euclides calcula \(\gcd(M,N)\) en tiempo polinómico a la longitud de \(M\) y \(N\), esto es polinómico en \(\log(MN)\). Pero queremos calcular \(\gcd(Q!,N)\) y \(Q!\) tiene longitud exponencial respecto de la de \(N\).
Recordemos el primer paso del algoritmo es dividir \(Q!=Nn+r\). Ya en el siguiente paso lo que hay que calcular es \(\gcd(N,r)\), pero \(r<N\), luego esto sí marcha en tiempo polinómico. Solo es el primer paso del algoritmo de Euclides el que es difícil.
Por tanto llegamos al problema
Problema. Podemos calcular \(r=Q!\bmod N\) con \(Q<N\) en tiempo \(O((\log N)^k)\)?
Si podemos hacerlo entonces podemos factorizar \(N\) en tiempo polinómico.
La dificultad de calcular \(Q!\bmod N\)
Supongamos que queramos descomponer en factores un número grande \(N\), digamos que un número de 10000 dígitos. El número de dígitos de \(Q!\) es entonces del orden de \(N\log N\approx 2.30\times 10^{10004}\). \(Q!\) no es grande, es gigantesco. Queremos calcular \(Q!\bmod N\), que es solo grande. En teoría hay un método de calcular \(Q!\bmod N\) usando solo números grandes
Como vemos \(x\) nunca es mayor que 2000 dígitos. Número grande pero no gigante. Este algoritmo es impracticable ya que el número de ciclos en el «for» es del orden de \(Q\approx N\approx 10^{10000}\) ciclos.
Definiremos ahora lo que entendemos por una construcción de un número \(m\). Es una sucesión de números enteros \(x_0\), \(x_1\), …, \(x_r\) tales que
- \(x_0=1\),
- \(x_r=m\),
- Para cada \(1\le k\le r\) existen \(0\le i, j<k\) tales que \(x_k=x_i\circ x_j\) donde \(\circ\) denota una suma \(+\), una multiplicación \(\times\), o una diferencia \(-\).
Diremos que \(r\) es la longitud de la construcción. Para cada número \(m\) existe un construcción con la menor longitud, esta sera su complejidad \(\tau( m) =\inf r\). Lo que a nosotros nos interesa es que una construcción de \(Q!\) permite obtener \(Q!\bmod N\), sin usar números gigantes. Basta realizar la construcción módulo \(N\). Es fácil ver que \(\tau(m)\le 2\log m\), pero nosotros necesitamos algo mucho mejor. Por ejemplo si \(m=2^{2^k}\) se tiene \(\tau(m)\le \log\log m+1\). Solo hay que hacer \(k\) sucesivas operaciones del tipo \(x\times x\). Lo que ocurre con \(Q!\) es desconocido, necesitamos una construcción corta de \(Q!\).
Problema abierto. ¿Existe una constante \(c\) tal que $$\tau(Q!)\le (\log Q)^c ?$$
Una respuesta positiva nos proporcionaría un modo de calcular \(Q!\bmod N\) en tiempo proporcional a \((\log N)^c\). Si además la respuesta positiva viniera acompañada de una construcción explícita de \(Q!\), entonces la factorización de \(N\) se podría realizar en tiempo polinómico a la longitud de \(N\).
Igual de útil sería poder calcular algún múltiplo de \(Q!\). Y esto es de ayuda en algunos casos. Por ejemplo, Noam Elkies considera el caso de $$13\times 7!=65520=2^{16}-2^4.$$ Que podemos calcular en 6 pasos $$1+1=2,\quad 2\times2=4,\quad 4\times4=16,\quad 16\times16=256,$$ $$256\times256=65536,\quad 65536-16=65520.$$
Pensemos en \(Q!\) escrito en base \(N\). Lo que nos interesa es la última cifra de este desarrollo. En análisis estamos interesados en las primeras cifras, las más significativas. Pero nuestro problema ahora es calcular la última.
Hay muchos métodos de calcular \(Q!\), recientemente Fredrik Johansson ha escrito un survey de 51 páginas sobre el cálculo de \(\Gamma(n)\). El más conocido es el desarrollo de Stirling $$\Gamma(z+1) \,= \,z! \;\sim \;\sqrt{2 \pi} \, e^{-z} z^{z+1/2} \left(1 + \frac{1}{12 z} + \frac{1}{288 z^2} + \ldots \right), \quad |z| \to \infty,$$ que es estupendo para obtener las primeras cifras significativas, muchas de ellas, pero no las últimas.
La fórmula $$(2n)!=\genfrac{(}{)}{0pt}{}{2n}{n} (n!)^2$$ permite reducir el cálculo de \(Q!\bmod N\) al cálculo de \((\log N)\) números del tipo \(\genfrac{(}{)}{0pt}{}{2n}{n}\bmod N\).
Hay muchas posibilidades abiertas para calcular \(Q!\bmod N\).
El cálculo en un anillo
Las máquinas de Turing han permitido formalizar nuestra idea de algoritmo. Estudiar la complejidad de los mismos. Sin embargo nuestros cálculos generalmente consideran números reales y/o complejos. Tratar de acomodar nuestros algoritmos numéricos a las máquinas de Turing los hace innecesariamente complicados. Leonore Blum, Felipe Cucker, Michael Shub y Steve Smale han desarrollado una teoría en que los elementos iniciales no son bits de información sino elementos de un anillo o un cuerpo. De este modo la teoría recupera la clásica usando el cuerpo \(\mathbb{F_2}\) de los enteros módulo 2, pero es mucho más flexible. Cada cuerpo proporciona un problema \(P\overset{?}=NP\), un problema con el mismo estilo pero sentido diferente. La conexión con nuestro problema es la siguiente
Diremos que la sucesión \(n!\) es fácil de cálcular si existe una sucesión de números naturales \(a_n\) tales que $$\tau(a_n\times n!)\le (\log n)^c.$$ En otro caso diremos que \(n!\) es difícil de calcular.
Nuestro problema entonces se relaciona con la cuestión \(P\overset{?}=NP\) del siguiente modo.
Teorema. Si la sucesión \(n!\) es difícil de calcular entonces \(P\ne NP\) sobre el cuerpo \(\mathbb C\).
Hay muchos caminos por explorar, pero debemos ser escépticos. Nuestro problema es complicado y difícilmente se va a simplificar.
Para saber más
El problema de la conexión entre la complejidad de calcular \(Q!\bmod N\) y la descomposición en factores primos es folklore. Me resulta difícil situar su origen. Desde luego está en el libro sobre la complejidad:
L. Bloom, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer, New York, 1998.
También en otros lugares como el blog Factoring and Factorials, J. Lipton.
Un pregunta en MathOverflow Bounds for constructing $n!$ with additions, subtractions, and multiplications starting from 1 trata el problema.
Las advertencias de Google están contenidas en algunas revistas Advertencias de Google 1, Advertencias de Google 2.
La frase citada de Gauss forma parte del artículo 329 de sus Disquisitiones Aritmeticae. El original del libro de Gauss está escrito en Latin. Existen traducciones al aleman, inglés, frances, español, etc. … La misma frase es citada por Knuth. Mi traducción al español usa varias de estas fuentes.
La imagen destacada La Torre de Babel, pintura al óleo sobre lienzo de Pieter Brueghel el Viejo quiere representar la dificultad del problema de la descomposición en factores primos y su repercusión en las comunicaciones humanas. La supresión de la diplomacia secreta es una de las condiciones de Kant para la Paz perpetua.
Dejar una contestacion