Introducción a las Pruebas de Primalidad

Introducción

Ya en 1798, Gauss, en sus Disquisitiones Arithmeticae, auguraba: «El problema de distinguir entre números primos y números compuestos es uno de las más importantes y útiles de la aritmética» ¹Gauss, Carl Friedrich. Disquisitiones Arithmeticae. 1966..

En efecto, en 1977 se desarrolló el sistema criptográfico RSA²M. D. Kelly. The RSA Algorithm: A Mathematical History of the Ubiquitous Cryptological Algorithm. 2009., que ha pasado la prueba del tiempo y aún es usado para garantizar la confidencialidad de las transacciones electrónicas. RSA es un algoritmo fuértemente ligado a los números primos: el proceso de cifrado requiere de números primos grandes $($del orden los trescientos dígitos), las llamadas llaves públicas.

Generar números primos de tal magnitud es un problema muy estudiado, y casi siempre involucra resolver un problema en apariencia más sencillo, pero igualmente escencial; el mismo que interesó a Gauss en uno de los textos más importantes sobre Teoría de Números: ¿Cómo saber si un número dado es primo o compuesto?

En este artículo describiremos una solución a este problema, estudiando primero los conceptos y propiedades de números primos que hacen posible su funcionamiento.

Números primos

Recordemos una definición esencial para nuestros próximos esfuerzos, la de divisibilidad. Decimos que un número entero a divide a otro número b (y escribimos a ∣ b) si existe un tercer número c tal que ac = b. Además, a a y c los llamamos divisores de b. Por ejemplo, 2 ∣ 8 (pues 2 × 4 = 8), 3 ∣ 15, pero 6 no divide a 21.

Por otro lado, decimos que un número p es primo si sus únicos divisores son 1 y p. Consideremos por ejemplo al número 18 que tiene 6 divisores: 1, 2, 3, 6, 9 y 18. Efectivamente, 1 y 18 son divisores de 18, pero también lo son 2, 3, 6, y 9, de tal forma que 18 no es un número primo (a este tipo de números solemos llamarle compuestos). En contraste 19 tiene solo dos divisores: 1 y 19, lo que lo convierte en un número primo.

Una Primera Prueba de Primalidad

Usemos la definición de número primo para diseñar un primer algoritmo que identifique si un número es primo o compuesto (prueba de primalidad). Un número n es primo si sus únicos divisores son 1 y él mismo. Bastará entonces que probemos, uno por uno, con todos los números entre 2 y n − 1, si alguno de ellos es divisor de n, sabemos que n no es primo; si, por otro lado, no encontramos ningún divisor de n, concluimos que n es primo.

Esta es nuestra primera prueba de primalidad. Notemos que este algoritmo determina si el número n es compuesto encontrado un número i, entre 2 y n − 1, que divida a n. De existir, dicho número i funge como, llamémosle así, testigo de la no-primalidad de n.

Es importante resaltar que en el peor de los casos, cuando n es primo, se hará la prueba de divisibilidad con cada uno de los números entre 2 y n − 1 sin encontrar divisores. Esta primera prueba de primalidad tiene entonces una complejidad computacional de O(n).

¿Es posible diseñar una prueba de primalidad más eficiente?

Es fácil ver que si ab = c, se debe cumplir que $ a \leq \sqrt{c}$ o $ b \leq \sqrt{c} $ (de lo contrario, si ambos divisores fueran mayores a $ \sqrt{c}$, el producto ab sería mayor a c). Esta afirmación nos permite concluir que si n es un número compuesto, entonces n tiene un divisor menor o igual a $\sqrt{n}$ que es distinto de 1 y de n. Con esto podemos reducir la complejidad de nuestra prueba de primalidad a $O(\sqrt{n})$.

El procedimiento a seguir es el mismo, simplemente hemos notado que basta con buscar divisores menores o iguales a $\sqrt{n}$. Aún con este algoritmo mejorado, nuestra prueba de primalidad es poco eficiente y no es viable para números tan grandes como los usados por RSA. Para diseñar una mejor prueba de primalidad requerimos de más conceptos de Teoría de Números.

Conceptos de Teoría de Números

Nuestro principal objetivo para diseñar una mejor prueba de primalidad será determinar una manerá más eficiente de econtrar testigos de la no primalidad de un número. Para ello permítamonos estudiar brevemente algunos conceptos de Teoría de Números y Teoría de Anillos. Comencemos por el concepto de congruencia.

Definición. Sean a, b, m ∈ ℤ, con m ≠ 0. Decimos que a y b son congruentes módulo m si m divide a b − a. Esta relación se expresa a ≡ b (mod  m).

La relación de congruencia módulo m define una relación de equivalencia: en efecto es simétrica, reflexiva y transitiva. De este modo podemos definir $\overline{a}$, la clase de equivalencia de a módulo m, como $\overline{a} = \{ x \in \mathbb{Z} \mid a \equiv x \pmod {m} \}$. A este conjunto también se le conoce como clase de congruencia. Por ejemplo, si m = 2, tenemos dos clases de congruencia: $\overline{0}$, el conjunto de todos los números pares, y $\overline{1}$, el conjunto de todos los números impares. En general hay m clases de congruencia modulo m, a saber: $\overline{0}, \overline{1}, \overline{2}, \dots, \overline{m – 2}, \overline{m – 1}$.

Definición. El conjunto de todas las clases de coungrencia módulo m se denota por ℤ/mℤ.

ℤ/mℤ define un anillo con la suma y producto definidos como sigue: para $\overline{a}, \overline{b} \in \mathbb{Z}/m\mathbb{Z}$, $\overline{a} + \overline{b} = \overline{a + b}$ y $\overline{a}\overline{b} = \overline{ab}$. Esta definición parece indicar que el valor de la suma y producto depende de los valores númericos de a y b y no de sus clases de coungruencia. La siguiente proposición es suficiente para ver que el valor de la suma y producto así definidos depende solo de las clases de congruencia de a y b.

Proposición. Sean a, b, c, d ∈ ℤ. Si a ≡ c (mod  m) y b ≡ d (mod  m), entonces a + b ≡ c + d (mod  m) y ab ≡ cd (mod  m).

Demostración. Una importante propiedad de divisibilidad es que si n ∣ x y n ∣ y, entonces n ∣ x + y.

Dado que m ∣ a − c y m ∣ b − d, concluimos que m ∣ (a − c) + (b − d) = (a + b) − (c + d); por lo tanto a + b ≡ c + d (mod  m). Por otro lado ab − cd = ab − cb + cb − cd = b(a − c) + c(b − d). m divide a ambos terminos de esta suma, por lo que m ∣ ab − cd y por lo tanto ab ≡ cd (mod  m).

Además, $\overline{0}$ funge como neutro aditivo, mientras que $\overline{1}$, a su vez, juega el papel de neutro multiplicativo. Todo elemento $\overline{a} \in \mathbb{Z}/m\mathbb{Z}$ tiene inverso aditivo: $\overline{m – a}$. Así pues, a ℤ/mℤ también se le denomina como el anillo de los enteros módulo m.

Recordemos que las unidades de un anillo son aquellos elementos del mismo que tienen inverso multiplicativo. Para el caso particular de ℤ/mℤ, las unidades son $\overline{a} \in \mathbb{Z}/m\mathbb{Z}$ tal que existe x que cumple $\overline{ax} = \overline{1}$. Como vimos, esto es equivalente a ax ≡ 1 (mod  m). Es posible demostrar que esta ecuación tiene solución si y solo si a es coprimo con m, es decir, si a y m no tienen divisores en común además de 1. De tal forma que $\overline{a}$ es una unidad de ℤ/mℤ si y solo si a es coprimo con m. Estamos en condiciones para enunciar un teorema escencial para nuestro propósito de distinguir números primos de números compuestos.

Definición. Sea m ∈ ℤ⁺, definimos la función ϕ(m) como el número de enteros entre 1 y m − 1 que son coprimos con m.

Por ejemplo, ϕ(8) = 4, pues 1, 3, 5 y 7 son coprimos con 8. Es fácil ver que si p es primo, ϕ(p) = p − 1. Por lo que vimos arriba, ℤ/mℤ tiene entonces ϕ(m) unidades. Si p es un número primo, ℤ/pℤ tiene ϕ(p) = p − 1 unidades.

Teorema 1 (Teorema de Euler). Si a y m son coprimos, entonces a^ϕ(m) ≡ 1 (mod  m).

Demostración. Por propiedades de anillos, las unidades de ℤ/mℤ forman un grupo de orden ϕ(m). Como a es coprimo con m, $\overline{a}$ es una unidad del anillo y se cumple que $\overline{a}^{\phi(m)} = \overline{1}$ o, equivalentemente, a^ϕ(m) ≡ 1 (mod  m).

Colorario (Pequeño Teorema de Fermat). Sean a, p ∈ ℤ, con p primo. Si p no divide a a, entonces a^p − 1 ≡ 1 (mod  p).

Demostración. Es consecuencia directa del Teorema anterior: como p no divide a a y p es primo, a y p son coprimos. Además, como vimos antes, ϕ(p) = p − 1. Aplicando el Teorema de Euler obtenemos la congruencia que buscamos: a^p − 1 ≡ 1 (mod  m).

Por último, demostremos la siguiente proposición que nos será de gran utilidad.

Proposición. Si p es primo, entonces x² ≡ 1 (mod  p) si y solo si x ≡ 1 (mod  p) o x ≡  − 1 (mod  p).

Demostración. Para esta demostración requerimos de una importante propiedad de los números primos: sean a, b ∈ ℤ, si p ∣ ab, entonces p ∣ a o p ∣ b.

Supongamos que x² ≡ 1 (mod  p), entonces p ∣ x² − 1 = (x + 1)(x − 1). Esto implica que p ∣ x + 1 o p ∣ x − 1; escribiendo esto en términos de congruencia módulo p: x ≡  − 1 (mod  p) o x ≡ 1 (mod  p).

Por otro lado, si x ≡ 1 (mod  p) o x ≡  − 1 (mod  p), naturalmente tenemos que x² ≡ 1 (mod  p); con lo que concluimos la demostración.

Resulta entonces que en ℤ/pℤ, con p primo, lás unicas ráices cudradas de $\overline{1}$ son las triviales: $\overline{1}$ y $\overline{-1}$.

Prueba de Primalidad Probabilística de Miller-Rabin

Permítamonos resaltar las dos propiedades demostradas en la sección anterior que nos permitirán describir una segunda y mucho más eficiente prueba de primalidad:

Teorema 2(Pequeño Teorema de Fermat). Sean a, p ∈ ℤ, con p primo. Si p no divide a a, entonces a^p − 1 ≡ 1 (mod  p).

No existen raíces cuadradas no triviales de la unidad en ℤ/pℤ. Si p es primo, entonces x² ≡ 1 (mod  p) si y solo sí x ≡ 1 (mod  p) o x ≡  − 1 (mod  p).

Es valioso resaltar que si tomamos un número compuesto, estas propiedades no necesariamente se cumplen. Por ejemplo, tomemos 8, que a todas luces es un número compuesto. Resulta que 5 es una raíz cuadrada no trivial de la únidad: 5² = 25 ≡ 1 (mod  p). Tampoco se cumple la ecuación del Pequeño Teorema de Fermat: 5⁷ ≡ 5 (mod  8).

Tenemos entonces dos nuevas maneras de buscar testigos de la no-primalidad de un número:

1. Si n ∈ ℤ⁺, a ∈ {2, 3, …, n − 1}, y a^n − 1 ≢ 1 (mod  n), entonces n es un número compuesto. a es testigo de la no primalidad de n pues muestra que no se cumple el Pequeño Teorema de Fermat.
2. Si n ∈ ℤ⁺, b ∈ {2, 3, …, n − 1}, y b² ≡ 1 (mod  n), entonces n es un número compuesto. b es testigo de la no primalidad de n pues muestra que no se cumple la propiedad de raíces no triviales en ℤ/nℤ.

En nuestra primera prueba de primalidad buscábamos testigos de manera secuencial, de 2 a n − 1. Para esta prueba de primalidad elijamos los potenciales testigos de manera aleatoria; más adelante veremos que esta forma de proceder es bastante eficiente.

De tal forma que, para saber si n ∈ ℤ⁺ es primo, procederemos de la siguiente forma:

1. Elegimos a ∈ {2, 3, …, n − 1} aleatoriamente.
2. Escribimos a n − 1 como n − 1 = 2^tu, con t, u enteros no negativos y u impar.
3. Calcularemos la sucesión x₀, x₁, …, x_t. x₀ = a^u y para i ∈ {1, 2, …, t} x_i = x_i − 1² (mod  m). Notemos que x_t ≡ a^2tu ≡ a^n − 1 (mod  n).
4. Si i ∈ {1, 2, …, t}, x_i ≡ 1 (mod  n) y además x_i − 1 ≠ 1,  − 1, hemos encontrado una raíz cuadrada no trivial de la unidad módulo n. Concluimos entonces que n no es primo.
5. Si x_t = a^n − 1 ≢ 1 (mod  n), entonces n no cumple la ecuación del Pequeño Teorema de Fermat, por lo que n es un número compuesto.

A continuación mostramos el pseudocódigo de este algoritmo.

Está claro que el costo computacional de este algoritmo es el de obtener los elementos de la secuencia x₀, x₁, …, x_t. Si tenemos cuidado de obtener el valor de a^u de manera eficiente (utilizando un método conocido como exponenciación binaria), la complejidad computacional de este procedimiento es O(log n).

Ahora bien, este procedimiento solo prueba con un potencial testigo. La prueba de primalidad de Miller-Rabin (propuesta por Michael O. Rabin en 1980, basada en el trabajo previo de Gary L. Miller)³Rabin, Michael O. «Probabilistic Algorithm for Testing Primality.» Journal of Number Theory 12, no. 1 (1980): 128-38. consiste en elegir s potenciales testigos de manera aleatoria, si alguno de ellos en efecto atestigua la no-primalidad de n, el algoritmo concluye que n es compuesto; en caso contrario se concluye que n es primo.

Notemos lo siguiente: cuando la prueba de primalidad devuelve COMPUESTO, tenemos total certeza de que n no es primo, pues hemos encontrado que n no cumple la ecuación del Pequeño Teorema de Fermat o tiene raíces no triviales de la unidad. Por otro lado, cuando el procedimiento devuelve PRIMO, no tenemos total certeza de que el número sea en efecto primo, sólo sabemos que entre los s valores elegidos aleatoriamente no hay testigos de la no-primalidad de n. Este algoritmo es entonces propenso a errores, pero el único tipo de error que comete es asumir erroneamente que n es primo.

Lo cierto es que es posible demostrar que incluso con valores pequeños de s, tan pequeños como 3, la Prueba de Primalidad de Miller-Rabin es muy poco propensa a errores⁴T.H. Cormen. Introduction to Algorithms. MIT Press, 2009.. Así pues, aunque está prueba de primalidad tienen una pequeña probabilidad de cometer errores, su complejidad computacional es, como vimos, O(log n), mucho mejor que la de nuestras primeras dos pruebas de primalidad. No entraremos en detalles sobre la probabilidad de fallo de este algoritmo, pero vale la pena reconocer que este algoritmo probabilístico, como RSA, ha pasado la prueba del tiempo y sigue siendo la prueba de probabilidad más utilizada.