Tests de primalidad

Este artículo describe varios algoritmos para determinar si un número es primo o no.

División por tentativa

Por definición, un número primo no tiene ningún divisor distinto de $1$ y de sí mismo. Un número compuesto tiene al menos un divisor adicional; llamémoslo $d$. Naturalmente $\frac{n}{d}$ también es un divisor de $n$. Es fácil ver que o bien $d \le \sqrt{n}$ o bien $\frac{n}{d} \le \sqrt{n}$, por lo tanto uno de los divisores $d$ y $\frac{n}{d}$ es $\le \sqrt{n}$. Podemos usar esta información para comprobar la primalidad.

Intentamos hallar un divisor no trivial, comprobando si alguno de los números entre $2$ y $\sqrt{n}$ es un divisor de $n$. Si es un divisor, entonces $n$ definitivamente no es primo; en caso contrario, lo es.

bool isPrime(int x) {
    for (int d = 2; d * d <= x; d++) {
        if (x % d == 0)
            return false;
    }
    return x >= 2;
}

Esta es la forma más simple de una comprobación de primalidad. Se puede optimizar esta función bastante, por ejemplo comprobando solo todos los números impares en el bucle, ya que el único primo par es 2. Varias de esas optimizaciones se describen en el artículo sobre factorización de enteros.

Test de primalidad de Fermat

Este es un test probabilístico.

El pequeño teorema de Fermat (véase también la función φ de Euler) afirma que, para un número primo $p$ y un entero $a$ coprimo, se cumple la siguiente ecuación:

$$a^{p-1} \equiv 1 \bmod p$$

En general este teorema no se cumple para números compuestos.

Esto se puede usar para crear un test de primalidad. Elegimos un entero $2 \le a \le p - 2$ y comprobamos si la ecuación se cumple o no. Si no se cumple, p. ej. $a^{p-1} \not\equiv 1 \bmod p$, sabemos que $p$ no puede ser un número primo. En este caso llamamos a la base $a$ un testigo de Fermat (Fermat witness) de que $p$ es compuesto.

Sin embargo también es posible que la ecuación se cumpla para un número compuesto. Así que si la ecuación se cumple, no tenemos una demostración de primalidad. Solo podemos decir que $p$ es probablemente primo. Si resulta que el número es en realidad compuesto, llamamos a la base $a$ un mentiroso de Fermat (Fermat liar).

Ejecutando el test para todas las bases $a$ posibles, de hecho podemos demostrar que un número es primo. Sin embargo esto no se hace en la práctica, ya que es mucho más trabajo que simplemente hacer división por tentativa. En su lugar, el test se repetirá varias veces con elecciones aleatorias de $a$. Si no encontramos ningún testigo de que el número es compuesto, es muy probable que de hecho sea primo.

bool probablyPrimeFermat(int n, int iter=5) {
    if (n < 4)
        return n == 2 || n == 3;
 
    for (int i = 0; i < iter; i++) {
        int a = 2 + rand() % (n - 3);
        if (binpower(a, n - 1, n) != 1)
            return false;
    }
    return true;
}

Usamos exponenciación binaria para calcular de forma eficiente la potencia $a^{p-1}$.

Hay una mala noticia, sin embargo: existen algunos números compuestos para los que $a^{n-1} \equiv 1 \bmod n$ se cumple para todo $a$ coprimo con $n$, por ejemplo para el número $561 = 3 \cdot 11 \cdot 17$. Tales números se llaman números de Carmichael. El test de primalidad de Fermat solo puede identificar estos números si tenemos una inmensa suerte y elegimos una base $a$ con $\gcd(a, n) \ne 1$.

El test de Fermat se sigue usando en la práctica, ya que es muy rápido y los números de Carmichael son muy raros. P. ej. solo existen 646 de esos números por debajo de $10^9$.

Test de primalidad de Miller-Rabin

El test de Miller-Rabin extiende las ideas del test de Fermat.

Para un número impar $n$, $n-1$ es par y podemos extraer todas las potencias de 2. Podemos escribir:

$$n - 1 = 2^s \cdot d,~\text{with}d\text{odd}.$$

Esto nos permite factorizar la ecuación del pequeño teorema de Fermat:

$$\begin{array}{rl}{a}^{n-1}\equiv 1<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>n& ⟺a^{2^{s}d}-1\equiv 0<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>n\\ \\ & ⟺(a^{2^{s-1}d}+1)(a^{2^{s-1}d}-1)\equiv 0<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>n\\ \\ & ⟺(a^{2^{s-1}d}+1)(a^{2^{s-2}d}+1)(a^{2^{s-2}d}-1)\equiv 0<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>n\\ \\ & \mathrm{⋮}\\ \\ & ⟺(a^{2^{s-1}d}+1)(a^{2^{s-2}d}+1)\cdots (a^d+1)(a^d-1)\equiv 0<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>n\\ \end{array}$$$$\begin{array}{rl} a^{n-1} \equiv 1 \bmod n &amp;\Longleftrightarrow a^{2^s d} - 1 \equiv 0 \bmod n \\ &amp;\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-1} d} - 1) \equiv 0 \bmod n \\ &amp;\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-2} d} + 1) (a^{2^{s-2} d} - 1) \equiv 0 \bmod n \\ &amp;\quad\vdots \\ &amp;\Longleftrightarrow (a^{2^{s-1} d} + 1) (a^{2^{s-2} d} + 1) \cdots (a^{d} + 1) (a^{d} - 1) \equiv 0 \bmod n \\ \end{array}$$

Si $n$ es primo, entonces $n$ tiene que dividir a uno de estos factores. Y en el test de primalidad de Miller-Rabin comprobamos exactamente esa afirmación, que es una versión más estricta de la afirmación del test de Fermat. Para una base $2 \le a \le n-2$ comprobamos si o bien

$$a^d \equiv 1 \bmod n$$

se cumple, o bien

$$a^{2^r d} \equiv -1 \bmod n$$

se cumple para algún $0 \le r \le s - 1$.

Si encontramos una base $a$ que no satisface ninguna de las igualdades anteriores, entonces encontramos un testigo de que $n$ es compuesto. En este caso hemos demostrado que $n$ no es un número primo.

De forma similar al test de Fermat, también es posible que el conjunto de ecuaciones se cumpla para un número compuesto. En ese caso la base $a$ se llama un mentiroso fuerte (strong liar). Si una base $a$ satisface las ecuaciones (una de ellas), $n$ es solo primo probable fuerte (strong probable prime). Sin embargo, no hay números como los de Carmichael, en los que todas las bases no triviales mientan. De hecho es posible mostrar que a lo sumo $\frac{1}{4}$ de las bases pueden ser mentirosos fuertes. Si $n$ es compuesto, tenemos una probabilidad de $\ge 75$ de que una base aleatoria nos diga que es compuesto. Haciendo varias iteraciones, eligiendo distintas bases aleatorias, podemos decir con probabilidad muy alta si el número es verdaderamente primo o si es compuesto.

Aquí hay una implementación para enteros de 64 bits.

using u64 = uint64_t;
using u128 = __uint128_t;
 
u64 binpower(u64 base, u64 e, u64 mod) {
    u64 result = 1;
    base %= mod;
    while (e) {
        if (e & 1)
            result = (u128)result * base % mod;
        base = (u128)base * base % mod;
        e >>= 1;
    }
    return result;
}
 
bool check_composite(u64 n, u64 a, u64 d, int s) {
    u64 x = binpower(a, d, n);
    if (x == 1 || x == n - 1)
        return false;
    for (int r = 1; r < s; r++) {
        x = (u128)x * x % n;
        if (x == n - 1)
            return false;
    }
    return true;
};
 
bool MillerRabin(u64 n, int iter=5) { // devuelve true si n es probablemente primo; si no, devuelve false.
    if (n < 4)
        return n == 2 || n == 3;
 
    int s = 0;
    u64 d = n - 1;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }
 
    for (int i = 0; i < iter; i++) {
        int a = 2 + rand() % (n - 3);
        if (check_composite(n, a, d, s))
            return false;
    }
    return true;
}

Antes del test de Miller-Rabin se puede comprobar adicionalmente si alguno de los primeros números primos es un divisor. Esto puede acelerar mucho el test, ya que la mayoría de los números compuestos tienen divisores primos muy pequeños. P. ej. el $88$ de todos los números tiene un factor primo menor que $100$.

Versión determinista

Miller mostró que es posible hacer el algoritmo determinista comprobando solo todas las bases $\le O((\ln n)^2)$. Bach dio después una cota concreta: solo es necesario probar todas las bases $a \le 2 \ln(n)^2$.

Esto sigue siendo una cantidad bastante grande de bases. Así que se ha invertido bastante poder de cómputo en hallar cotas más bajas. Resulta que, para probar un entero de 32 bits, solo es necesario comprobar las primeras 4 bases primas: 2, 3, 5 y 7. El menor número compuesto que falla este test es $3,215,031,751 = 151 \cdot 751 \cdot 28351$. Y para probar un entero de 64 bits basta con comprobar las primeras 12 bases primas: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 y 37.

Esto da lugar a la siguiente implementación determinista:

bool MillerRabin(u64 n) { // devuelve true si n es primo; si no, devuelve false.
    if (n < 2)
        return false;
 
    int r = 0;
    u64 d = n - 1;
    while ((d & 1) == 0) {
        d >>= 1;
        r++;
    }
 
    for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n == a)
            return true;
        if (check_composite(n, a, d, r))
            return false;
    }
    return true;
}

También es posible hacer la comprobación con solo 7 bases: 2, 325, 9375, 28178, 450775, 9780504 y 1795265022. Sin embargo, como estos números (excepto 2) no son primos, hay que comprobar adicionalmente si el número que se está comprobando es igual a algún divisor primo de esas bases: 2, 3, 5, 13, 19, 73, 193, 407521, 299210837.

Problemas de práctica

• SPOJ - Prime or Not 
• Project euler - Investigating a Prime Pattern