Hablemos de Números Primos I

Un número natural $p>1$ es primo si la única posible factorización es $p=p\cdot 1$ . Siendo los átomos de la aritmética, es natural que nos surjan muchas preguntas en torno a ellos. ¿Cuántos hay? Se sabe que hay infinitos números primos. La primera demostración conocida es de Euclides. Lo que me gusta de esta demostración es la sutil forma de acercarse al infinito.

Esta demostración, aunque muy bella, no nos proporciona suficiente información sobre cómo se distribuyen los primos. Podemos preguntarnos entonces, ¿Cuántos números primos menores a un número dado $x$ existen? La respuesta aproximada a esta pregunta viene dada por el siguiente teorema:

Teorema del Número Primo: Sea $\pi(x)=\#\{p\,primo: p\leq x\}.$ Entonces, $\pi(x)\sim \frac{x}{\log x}.$ ¹

Este teorema fue demostrado en 1986 por Hadamard y Valle Poussin de manera independiente y utiliza herramientas del análisis complejo y está estrechamente relacionada con la Hipótesis de Riemann.

Hay dos hechos sobre la distribución de los números primos que espero convencerles de forma tan contundente que se les quedarán grabados en la memoria. El primero es que, a pesar de su sencilla definición y su función como elementos fundamentales de los números naturales, los números primos crecen como la maleza entre ellos, sin obedecer a ninguna ley más que la del azar, y nadie puede predecir dónde brotará el siguiente. El segundo hecho es aún más asombroso, pues afirma justo lo contrario: que los números primos exhiben una regularidad asombrosa, que existen leyes que rigen su comportamiento y que obedecen a estas leyes con una precisión casi militar. ²

Don Zagier, 1975

¿Existe alguna fórmula para el $n$ -ésimo número primo $p_n$ ? Es común escuchar que, al contrario de la mayoría de los subconjuntos interesantes de los números naturales, los primos no obedecen a ninguna fórmula. Les cuento que esto no es cierto. La respuesta es que existen fórmulas, pero computacionalmente ineficientes. Un ejemplo es la fórmula de Willians (1964) ³ :

p_n = 1 + \sum_{m=1}^{2^n} \left\lfloor \left[ \frac{n}{\sum_{j=1}^m \left\lfloor \cos^2 \left( \pi \frac{(j-1)! + 1}{j} \right) \right\rfloor} \right]^{1/n} \right\rfloor.

Test de Primalidad

¿Cómo decidir si un número es primo? Si tuviera una maquinita eficiente a la cual le pongo un número natural y me dice con certeza si es primo o compuesto, me habría hecho rica. Uno de los motivos de mi afirmación es que los primos aparecen por doquier en criptografía. Problemas abiertos sobre ellos son la base de la seguridad de muchos protocolos criptográficos de clave pública . El ejemplo más claro es el Algoritmo RSA. De aquí un tema importante en criptografía en entender los test de primalidad, que son algoritmos que permiten decidir si un número es primo o compuesto.

Existen algunas herramientas que nos permiten aproximarnos a una respuesta.

Teorema: Si $N$ no es primo, al menos uno de sus factores primos debe ser menor que $\sqrt{N}$ .

Esto, pues si $p_1$ y $p_2$ son factores primos de $N$ con $p_1>\sqrt{N}$ y $p_2>\sqrt{N}$ , entonces: $N\geq p_1\cdot p_2>\sqrt{N}\cdot\sqrt{N}=N$ lo que es falso, pues $N$ no puede ser más grande que $N$ . Por lo tanto, para saber si un número $N$ es primo hay que detectar si tiene factores entre 1 y $\sqrt{N}$ .

La Criba de Eratóstenes

Este algoritmo data de la época de la Grecia antigua y fue desarrollado por Eratostenes de Cyrene (276-195 a.C). Consiste en poner en una lista todos los números del 2 hasta cierto límite. Primero se tachan todos los múltiplos de 2, excepto el 2. Después se hará lo mismo con los múltiplos de 3, excepto el 3 (será como ir saltando de 3 en 3). Se seguirá tachando los múltiplos de 5, salvo el 5, que no estén tachados, y así hasta terminar. Los números que no hayan sido tachados serán los primos.

Considerando que su complejidad para detectar primos entre 2 y $n$ es de $\mathcal{O}(n\log\log n)$ , dependiendo de la versión que se use, es viable utilizarlo entre $n=6.4\cdot 10^{10}\, o\, n=10^{12}$ .⁴

Test de Fermat

Aquí tenemos un test para decidir si un número es compuesto. El (pequeño) Teorema de Fermat, dice que si $p$ es primo, y $a$ es un entero sin factores comunes con $p$ , entonces

a^{p-1}\equiv 1\pmod p.

Si para un entero $a$ entre 2 y $p-2$ la ecuación no es válida, entonces $p$ no puede ser primo. Sin embargo, si la ecuación vale para todos estos enteros $a$ , no es posible concluir nada.

Test de Miller-Rabin

Este test es probabilista, es decir, el resultado que entrega tiene una alta probabilidad de ser válido. Fue propuesto por Gary L. Miller⁵ en 1976, y modificado por Michael O. Rabin⁶ en 1980.

Sea $n \ge 2$ un número impar, con $n – 1 = 2^s\cdot d$ , y $d$ un número entero impar y $s\ge 1$ . Se tiene que $a \in \mathbb{Z}$ es un testigo de Miller-Rabin de $n$ si no tienen factores comunes y las siguientes condiciones valen simultáneamente:

$a^d \not\equiv 1 \pmod{n}$
$a^{2^i d} \not\equiv -1 \pmod{n}$ , para cualquier $i = 0, 1, 2, \dots, k – 1.$

Este número base demuestra, cuando es el caso, que $n$ no es primo.

Algoritmo de Miller-Rabin

Entrada: Un número impar $n > 3$ y una base $a$ tal que $2 \leq a \leq n-2$ . Salida: COMPUESTO (si $a$ es testigo) o PROBABLE PRIMO.

Factorización: Hallar $s$ y $d$ tales que $n – 1 = 2^s \cdot d$ , con $d$ impar.
Cálculo inicial: Calcular $x = a^d \pmod{n}$ .
Primer test: Si $x = 1$ o $x = n – 1$ , retornar PROBABLE PRIMO.
Bucle de elevación al cuadrado: Repetir s−1 s – 1 veces:
- $x = x^2 \pmod{n}$
- Si $x = n – 1$ , retornar PROBABLE PRIMO.
Conclusión: Si el bucle termina sin haber retornado, retornar COMPUESTO ( $a$ es un testigo).

Si el test se repite $k$ veces con todas las salidas siendo PROBABLE PRIMO, entonces la probabilidad de error verifica

P(\text{error}) \leq \left(\frac{1}{4}\right)^k.

¿Es útil el Test de Miller-Rabin?

Para números menores a $2^{32}$ , basta utilizar las bases 2, 7 y 61 para obtener certeza ⁷. La eficiencia del test de Miller-Rabin no depende solo del número de rondas, sino de la velocidad con la que se realizan las operaciones de exponenciación modular.

El test de Miller-Rabin tiene un papel vital como filtro de alta velocidad en el proyecto GIMPS (Great Internet Mersenne Prime Search), del cual han aparecido los primos más grandes conocidos a la fecha.

Existen estándares de seguridad que indican que para una clave RSA de 2048 bits, se deben realizar al menos 64 rondas del test. Esto garantiza una probabilidad de error inferior a $2^{-128}$ , ⁸ lo que significa que la probabilidad de generar una clave insegura por accidente es menor que la de adivinar una clave AES-128 en el primer intento.

La lista de test de primalidad y la historia sobre los primos no terminan acá.

Continuará….

View this post on Instagram

MacLean, S. (2014). Teorema del Número Primo: Dos enfoques de la demostración [Tesis de Licenciatura en Matemáticas, Universidad de Valparaíso]. Repositorio de la Universidad de Valparaíso. ↩︎
Esta frase corresponde a parte de la clase inaugural del matemático Don Zagier en la Universidad de Bonn en 1975. https://people.mpim-bonn.mpg.de/zagier/files/doi/10.1007/BF03039306/fulltext.pdf ↩︎
C. P. Willans, On Formulae for the nth Prime Number, The Mathematical Gazette
Vol. 48, No. 366 (Dec., 1964), ↩︎
R. Crandall, C. Pomerance, Prime Numbers: A Computational Perspective
Springer, 2nd Edition, 2005 ↩︎
Miller, G. L. (1976). Riemann’s hypothesis and tests for primality. Journal of Computer and System Sciences, 13(3), 300-317. ↩︎
Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1), 128–138 ↩︎
https://miller-rabin.appspot.com/#records ↩︎
Damgård, I., Landrock, P., & Pomerance, C. (1993). Average case error estimates for the strong probable prime test. Mathematics of Computation, 61(203), 177-194 ↩︎

Matemáticas, Criptografía y otras hierbas