Un Test de Primalidad es un algoritmo que permite decidir si un número natural n es primo o compuesto.

TESTS DE PRIMALIDAD

Definición: Un Test de Primalidad es un algoritmo que permite decidir si un número natural n es primo o compuesto.

Cualquier método de factorización (por ejemplo la división por los números, impares, menores que √n), constituye un test de primalidad. Sin embargo, todos los métodos conocidos de factorización, tienen una complejidad computacional exponencial en el número de dígitos de n, o equivalentemente en el loga- ritmo de n en la base de numeración considerada. Así, en el lenguaje de Teoría de la Complejidad , el costo del método anterior de criba es O(n1/2log2n)) (hay que realizar aproximadamente 1/2 · n1/2 divisiones y el coste de cada una es cuadrático en log(n)).

Veamos algunos ejemplos:

1. Test de Wilson: (n − 1)! ≡ −1 (mod n) si y solo si n es primo. (El inconveniente es que el computo del factorial es un problema computacionalmente más complejo que la factorización, ver [López-Tena, 1990]).

2. Test de Lucas: Sea a natural con 1 ≤ a^n−1  ≡ 1 (mod n), pero a^n −1/q   ≠ 1 (mod n) , para todo factor primo q de n − 1. Entonces n es primo.

(El inconveniente en este caso es la necesidad de conocer la factorización de n − 1 y como hemos dicho, factorizar es computacionalmente un problema difícil).

El comentario anterior, a propósito del test de Lucas, muestra que, para números particulares, pueden ser factibles tests deterministas de primalidad eficientes y fáciles de implementar.

3.Test de Proth: n = A2^r + 1, A < 2r. Sea p primo tal que n no es cuadrado modulo p. Entonces n es primo si y solo si p^n−1/2 ≡ −1 (mod n).

Los tests anteriores tienen una complejidad similar a la de los tests probabilísticos (en concreto O(log3n)) y han permitido obtener los records, ver [Ribemboim, 1988], de primos conocidos. Así, el primo número 38 de Mersenne, M38 = 26972593 − 1 posee más de dos millones de dígitos. Bien es cierto que, por ahora, primos de este tamaño (conocidos como primos titánicos) no tienen demanda en el mercado.

5.Teorema de Fermat: Sea p un primo y a entero tal que mcd(a, p) = 1. Se verifica que

(a)^p−1 ≡ 1 (mod p).

Para todo a existen también contraejemplos a la implicación inversa (pseudoprimos en base a), así:

-n = 91 = 7 × 13, para a = 3. Nótese que, aunque 91 no es pseudoprimo en base 2, sin embargo, n = 1105 es pseudoprimo en ambas bases 2 y 3.  Existen números, denominados números de Carmichael, n, impar compuesto, tales que ∀a, mcd(a, n) = 1 verifican (a) ^n−1 ≡ 1 (mod n). (Ejemplos: 561, 1105, etc).

...