La criptografía puede ser muy útil, pero nuestro objetivo como matemáticos es resolver problemas. Por tanto 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 interés matemático.
Gauss consideraba que el honor de la Matemática requería que resolviéramos un problema tan elegante como la factorización. Con sus métodos él podía factorizar números de 7, 8 o incluso más cifras. En 1970 el límite eran 20 dígitos, con el método de las fracciones continuas de Brillhart-Morrison saltó a 50 dígitos en 1980. En 1994 el método de la criba cuadrática de Pomerance dobló esta cantidad (números de 100 dígitos). Todavía surgieron dos métodos importantes la criba de cuerpos algebraicos de Pollard y el método de Lenstra usando curvas elípticas, cada uno con sus peculiaridades.
El problema de la factorización está en la clase \(\textbf{NP}\) (si conocemos la factorización es fácil comprobarlo), pero no parece que sea \(\textbf{NP}-\text{completo}\) (un algoritmo rápido de factorización no implica la solución de cualquier otro problema en la clase \(\textbf{NP}\)). Hay bastante consenso en que es un problema difícil, pero los avances anteriores hacen dudar ¡Quizás hay una solución mágica! Como mágicos le parecerían a Gauss los métodos actuales.
Fermat y sus cuadrados.
Fermat buscaba poner \(n\) como diferencia de dos cuadrados $$n=a^2-b^2=(a+b)(a-b).$$ Si queremos factorizar 1927 podemos notar que el año de la guerra es un cuadrado perfecto \(1936=44^2\). Así que $$1927=1936-9=(44+3)(44-3)=47\times41.$$ El método es general, si \(n\) es impar y tiene dos factores \(n=\alpha\beta\), entonces $$n=\bigl(\frac12(\alpha+\beta)\bigr)^2- \bigl(\frac12(\alpha-\beta)\bigr)^2,$$ pero en la práctica el método está muy limitado.
Maurice Kraitchik en 1920 tuvo una idea que mejoró el método de Fermat sustancialmente. Se dio cuenta que bastaba encontrar una diferencia de cuadrados \(a^2-b^2\) divisible por \(n\). Es decir tal que \(a^2\equiv b^2\bmod n\). En este caso \(n\) divide a \((a+b)(a-b)\) luego hay cierta probabilidad, si \(n\) es compuesto, que \(n\) no divida a \((a+b)\) ni a \((a-b)\). Algunos de los factores de \(n\) están en \(a+b\) y otros en \(a-b\) y el máximo común divisor \(\mathop{\rm mcd}(n,a-b)\) será un divisor propio de \(n\).
La mayor parte de los métodos que hemos considerado antes siguen esta ruta, encontrar números \(a\) y \(b\) cumpliendo \(a^2\equiv b^2\bmod n\). Se termina aplicando el algoritmo de Euclides para obtener el máximo común divisor.
Kraitchik tuvo todavía otra idea importante, que se sigue usando en casi todos los métodos posteriores. Aunque no parece fácil encontrar dos cuadrados cuya diferencia sea divisible por \(n\), sí que es fácil tomar un número \(b\) elevarlo al cuadrado y dividir por \(n\) para obtener un resto \(r\) (relativamente pequeño) y tal que \(r\equiv b^2\bmod n\). Esto no parece servir de nada, hasta que uno se da cuenta de que si tengo muchos de estos \(r_j\equiv b_j^2\bmod n\) cuyos factores primos sean pequeños, podríamos formar un producto de ellos \(r_1r_2\cdots r_k=a^2\) que sí sea un cuadrado, entonces
$$r_1r_2\cdots r_k=a^2\equiv (b_1b_2\cdots b_k)^2\bmod n.$$
Ejemplo del método de Kreitchik.
Con \(n=21449\) tenemos que \(147^2=21609\), así que calculamos
\begin{align*}147^2-n&\equiv 2^5\cdot 5 \bmod{n}\\148^2-n&\equiv 5\cdot7\cdot 13\bmod{n}\\151^2-n&\equiv 2^3\cdot 13^2\bmod{n}\\153^2-n&\equiv 2^3\cdot 5\cdot7^2\bmod{n}\\\end{align*}
Donde hemos escogido 145, 148, 151 porque sus restos se factorizan con números pequeños. Podemos notar entonces que
$$(147\cdot153)^2=(2^5\cdot 5)\cdot(2^3\cdot 5\cdot7^2)\equiv (2^4\cdot 5\cdot 7)^2 \bmod 21449.$$
Veamos si hemos obtenido un factor, calculando el máximo común divisor de \(a-b\) $$\mathop{\rm mcd}(147\cdot153-2^4\cdot 5\cdot 7, 21449)=\mathop{\rm mcd}(21931,21449)=241.$$ Que efectivamente es un divisor propio y por tanto tenemos la factorización \(21449=241\cdot 89\)
Mejoras del método.
Una de las cosas que sorprenden cuando uno intenta hacer algo explícitamente, digamos que programando, es el hecho de que al intentarlo se hacen evidentes ligeras modificaciones del método. Y sí, aparentemente son ligeras modificaciones del método, pero tienen una gran repercusión en el resultado.
Por ejemplo deseamos encontrar \(a\) tal que \(a^2-n\bmod n\) se factorize con primos pequeños. Es claro que queremos que \(a^2\) esté cerca de \(n\). Podemos, también, usar números \(a\) con \(a^2<n\) siempre que anotemos \(-1\) como si fuera un factor primo. Esta simple observación duplica el número de \(a\) convenientes.
En 1931 D. H. Lehmer y R. E. Powers encontraron otro modo de encontrar restos pequeños. En lugar de usar el polinomio \(Q(x)=x^2-n\) consideran aproximaciones racionales a \(\frac{a}{b}\approx\sqrt{n}\). Cabe esperar que en ese caso \(a^2-b^2n\) sea pequeño y \(a^2\equiv a^2-b^2n\bmod n\). Hay una teoría muy importante para encontrar buenas aproximaciones a un número irracional, las fracciones continuas. De este modo se consiguen muchos mas números pequeños congruentes con cuadrados. Así que es una mejora evidente del método de Kreitchik.
El álgebra lineal.
El punto débil del método es que uno encuentra números suaves (esto es con factores primos pequeños) que son congruentes módulo \(n\) con un cuadrado. Pero entonces tiene que combinarlos para obtener un cuadrado. Como cuando antes vimos que \((2^5\cdot 5)(2^3\cdot5\cdot7^2)\) era un cuadrado. Cuando los números son realmente grandes la cuestión puede ser mucho mas difícil. Podemos estar hablando de decenas de números con factores primos todos \(\le 100\). ¿Cómo imaginar cuáles tenemos que multiplicar para obtener un cuadrado?
La respuesta a este problema la dieron en 1975 M. A. Morrison y J. Brillhart. Suponiendo que los números son de la forma $$(-1)^a 2^{r_1}3^{r_2}\cdots p_{k-1}^{r_{k-1}}$$ la información importante es la paridad de \((a,r_1,r_2,\dots, r_{k-1})\). Podemos considerar una matriz de \(0\) y \(1\)’s registrando las paridades de cada uno de nuestros números $$\begin{array}{c|ccccccc}& 2 & 3 & 5 & 7 & 11 & 13\\ \hline 147^2-n & 1 & & 1 & & & \\148^2-n & & & 1 & 1 & & 1\\151^2-n & 1 \\153^2-n & 1 & & 1\end{array}$$ Nuestro problema es encontrar varias filas cuya suma tenga todas sus coordenadas pares. Podemos considerar cada fila como un vector \(\mathbf{v}\) en un espacio vectorial \(\mathbf{F}_2^{k}\) sobre el cuerpo con solo dos elementos. Lo que deseamos es encontrar un conjunto de estos vectores \(\mathbf{v_1} \dots \mathbf{v_\ell}\) que sumen \(0\). Podemos aplicar los métodos del algebra lineal para encontrar rápidamente este subconjunto. De hecho si tenemos \(k+1\) números con esa factorización, los teoremas generales nos dicen que esos vectores son linealmente dependientes y, por tanto, podemos formar con ellos un cuadrado.
Por tanto Morrison y Brillhart fijan un número \(B\) y consideran solo los números primos \(\le B\). Dado \(n\) ahora la dificultad es como escoger el número \(B\). Si lo tomamos demasiado pequeño habrá pocos números \(a^2\bmod n\) que se factorizen con los primos \(p\le B\). Si lo tomamos muy grande el problema final de álgebra lineal se complica. Es relativo a este problema y su estudio teórico el avance reciente que queremos destacar hoy.
La complejidad de la factorización.
Con el advenimiento de los ordenadores ha surgido el problema de estudiar la dificultad de los problemas. Dado un número \(n\) grande, cuál es el tiempo necesario para factorizarlo. Eso depende del método empleado. Queremos considerar los métodos actuales.
Richard Schroeppel hacia el final de los años 70 y en correspondencia privada sugiere considerar aleatorios los números \(Q(a)=a^2-n\) o los \(Q_j\) del método de las fracciones continuas. No son realmente aleatorios, los hemos obtenido muy cuidadosamente para que sean congruentes con un cuadrado módulo \(n\). La cuestión es que desde el punto de vista de obtener con ellos un cuadrado, si que los podemos considerar aleatorios. Llamemos un número \(B\)-suave si se descompone en factores primos \(\le B\). La primera pregunta es entonces ¿Cuál es la probabilidad de que un número al azar en el intervalo \([1, X]\) sea \(B\)-suave? la respuesta es \(\frac{\psi(X,B)}{X}\), donde \(\psi(X,B)\) es el número de números \(B\)-suaves \(\le X\).
Si tomamos números \(\le X\) al azar, el número esperado de intentos antes de encontrar un número \(B\)-suave será el inverso de esta probabilidad \(\frac{X}{\psi(X,B)}\). Pero por el método de Morrison-Brillhart necesitamos del orden de \(\pi(B)\) (el número de primos \(\le B\)) para obtener un conjunto de vectores linealmente dependientes. De manera que el número total de intentos para conseguir un cuadrado será \(\frac{X\pi(B)}{\psi(X,B)}\). Finalmente, ¿qué trabajo lleva comprobar que un número dado es \(B\)-suave? Si lo que hacemos es dividir por los primos pequeños, el trabajo es aproximadamente \(\pi(B)\) divisiones. Luego al final el número de pasos de la factorización del número, escogiendo \(B\) como base de los primos es $$\frac{X\pi(B)^2}{\psi(X,B)}.$$
Tenemos así un trabajo para la Teoría Analítica de Números: Dado \(X\), ¿cómo escoger \(B\) de manera que esta cantidad sea mínima? ¿cuánto vale entonces este mínimo?
La respuesta es que \(B\) debe ser del orden \(\exp(\frac12\sqrt{\log X\log\log X})\) y el valor del mínimo es aproximadamente \(\exp(2\sqrt{\log X\log\log X})\). Para factorizar \(n\), los números que intentamos son del orden de \(X=\sqrt{n}\). Por tanto el método factoriza \(n\) en \(\exp(\sqrt{2\log n\log\log n})\) pasos.
Esto no es más que una conjetura (bien fundada), los problemas son que los números que usamos no son aleatorios y que podría pasar que encontráramos cuadrados que en el paso final del máximo común divisor fallen. Este argumento, sin embargo es muy acertado como veremos en el resto de la entrada.
El método de la criba cuadrática.
Según cuenta Carl Pomerance este razonamiento de Schroeppel le indujo a mejorar el método de una forma espectacular. Sustituyendo uno de los pasos del método por otro alternativo mucho mejor.
Descubrió que en el argumento anterior el proceso de comprobar si un número es \(B\)-suave, tiene un efecto grande en el resultado. De este modo en 1981, pensó que podría usar un método de criba, parecido a la criba de Eratóstenes para encontrar los primos.
Queremos encontrar números \(Q(x)=x^2-n\) que sean \(B\)-suaves. Hacemos una tabla con los números. Por cada \(p\le B\) vemos que \(Q(x)\) es divisible por \(p\) si \(x\equiv a\) o si \(x\equiv b\) para dos números concretos \(a\) y \(b\) que podemos calcular fácilmente. Luego en la tabla es fácil localizar esos números y dividirlos por \(p\). Cuando acabemos con todos los primos las posiciones en que aparezca un \(1\), es porque el correspondiente número \(Q(x)\) es \(B\)-suave. El proceso es mucho mas rápido que el de dividir. Con el procedimiento anterior la mayor parte de las veces dividimos para encontrar que el número al final no es divisible o no es \(B\)-suave.
Con este método el número de operaciones pasa de \(\exp(\sqrt{2\log n\log\log n})\) a \(\exp(\sqrt{\log n\log\log n})\). Esto nació como una idea de Pomerance, pero cuando se implementó el resultado fue espectacular, se factorizaban números de 100 dígitos.
Hay otros métodos que han mejorado el de la criba cuadrática, pero lo que hemos visto es suficiente para ver la importancia del resultado que comentamos.
Generación de cuadrados.
Hemos visto que muchos de los métodos de factorización de \(n\) reposan en la idea de generar números \(a_i\equiv b_i^2\bmod n\) y después encontrar subconjuntos de los \(a_i\) cuyo producto \(\prod_{i\in I}a_i\equiv z^2\bmod n\). De manera que \(z^2\equiv w^2:= \prod_{i\in I}b_i^2\bmod n\) con lo que tenemos candidatos a factores de \(n\) los números \(\mathop{mcd}(z-w,n)\).
La idea sugerida por Schroeppel es imaginar los \(a_i\) tomados al azar de un conjunto de números \([1,X]\). En el Congreso Internacional de 1994 Pomerance planteó la pregunta, siguiente: consideramos \([1,X]\) como espacio de probabilidad (cada número con la misma probabilidad) y dada una sucesión de variables independientes \(a_i\) en ese espacio consideremos la variable aleatoria $$T(X):=\min\{ N\in \mathbf{N}\colon \exists\ I\subset [1,X] \text{ tal que }\prod_{i\in I} a_i \text{ es un cuadrado }\}$$ Pomerance probó que para todo \(\varepsilon>0\) se tiene con probabilidad alta que $$\exp((1-\varepsilon)\sqrt{2\log X\log\log X})\le T(X)\le \exp((1+\varepsilon)\sqrt{2\log X\log\log X}).$$ y conjeturó que \(T(X)\) tiene un salto muy definido en el sentido de que existe una función \(f(X)\) con la propiedad de que con alta probabilidad $$(1-\varepsilon)f(X)\le T(X)\le (1+\varepsilon)f(X).$$ Es decir si tomamos mas de \(f(X)\) muestras \(a_i\) con gran probabilidad obtendremos un cuadrado (que podremos extraer mediante el álgebra lineal).
En 2012 E. Croot, A. Granville, R. Pemantle y P. Tetali casi consiguieron probar la existencia del salto. Probaron que con gran probabilidad $$\frac{\pi}{4}(e^{-\gamma}-\varepsilon)J(x)\le T(x)\le (e^{-\gamma}+\varepsilon)J(x)$$ donde $$J(X)=\min_{2\le B\le X}\frac{\pi(B)X}{\psi(X,B)}.$$ Es decir salvo por el factor \(\pi/4\) habían encontrado la función \(J(X)\) que determina la posición del salto.
La entrada está dedicada a un trabajo publicado este año en Annals of Mathematics: P. Balister, B. Bollobás, R. Morris, han probado que efectivamente con gran probabilidad se tiene $$(e^{-\gamma}-\varepsilon)J(X)\le T(X)\le (e^{-\gamma}+\varepsilon)J(X)\qquad (1).$$
El artículo tiene una 100 páginas. La demostración es muy técnica y combina técnicas de combinatoria, probabilidad y teoría analítica de números. Esto hace difícil explicar la prueba. En su lugar trataré de explicar las ideas que se aplican. Es este un ejemplo de como la Matemática resolviendo problemas aparentemente sin conexión crea herramientas que después se combinan inesperadamente para resolver nuevos problemas. Estas ideas que se usan en la prueba de (1) son:
Teoría analítica de números.
La función \(\psi(X,B)\) que hemos usado antes representa el número de números naturales \(n\le x\) que son \(B\)-suaves, es decir que no son divisibles por ningún primo \(p>B\). Su estudio comenzó en 1930 cuando Dickman probó $$\lim_{x\to\infty}\frac{\psi(x,x^{1/u})}{x}=\rho(u),$$ donde \(\rho(u)\) es la única solución de la ecuación diferencial con retardo $$u\rho'(u)+\rho(u-1)=0.$$ La función \(\rho(u)\) se conoce hoy con el nombre de función de Dickman-de Bruijn. La prueba de (1) hace uso de numerosos resultados sobre \(\psi(x,y)\) y \(\rho(u)\) que se han publicado a partir de los años 80 del pasado siglo.
Ecuaciones diferenciales y el método de martingalas autocorrectoras.
Muchos procesos que son realmente discretos se modelan mediante ecuaciones diferenciales. Por ejemplo la ecuación diferencial $$\frac{d}{dt}M=\lambda M$$ se usa para describir el crecimiento de poblaciones o la descomposición radioactiva. Muchos de estos procesos pueden describirse también mediante un proceso de Markov. Por ejemplo en el caso anterior mediante un proceso aleatorio \(X(t)\) tal que $$\mathbb{E}(X(t))=X(0)e^{\lambda t}.$$
Los dos tratamientos están relacionados. Los valores del proceso se concentran cerca de la solución de la ecuación diferencial. Mas precisamente, si tenemos una sucesión de valores iniciales del proceso \(X_n(0)\) tal que \(\lim_n X_n(0)/n=M(0)\), entonces para todo \(\varepsilon>0\) se tiene $$\lim_{n\to\infty} \mathbb{P}\Bigl\{\sup_{s\le t}\Bigl|\frac{X_n(s)}{n}-M(s)\Bigr|>\varepsilon\Bigr\}=0.$$
En 1970 T. G. Kurtz, publica un artículo en que extiende este resultado a muchas otras ecuaciones diferenciales. Este trabajo, y sobre todo, las técnicas que emplea, es el germen del método que hoy se conoce como de las martingalas autocorrectoras. Y es el principal ingrediente en la prueba de (1).
Los tres protagonistas.
Para saber mas.
El motivo de esta entrada es el artículo:
R. Balister, B. Bollobás, R. Morris, The sharp threshold for making squares, Ann. Math. 188 (2018) 49-143.
como hemos dicho es muy técnico. Podemos ver una exposición por uno de los autores Robert Morris en el Alang Turing Institute, que se encuentra en Youtube
Gran parte de la entrada la he basado en el artículo de Carl Pomerance, uno de los protagonistas de la historia. Desde luego es una lectura fácil y provechosa. La revista Notices of the American Mathematical Society es libre y cada mes aporta novedades interesantes sobre la Matemática.
C. Pomerance, A Tale of Two Sieves, Notices Amer. Math. Soc. 43 nº 12 (1996) 1473-1485.
Finalmente, hemos usado también el artículo de Kurtz sobre las ecuaciones diferenciales
T. G. Kurtz, Solutions of Ordinary differential equations as limits of Pure Jump Markov Processes, J. Appl. Probability, 7 (1970) 49–58.
Dejar una contestacion