Test de Pocklington

El test de Pocklington es un test de primalidad para cierto conjunto de números inventado por Henry Cabourn Pocklington en 1914.^[1]​

Sea N = fr + 1 donde 0 < r < f+2 y se conocen todos los factores primos de f. El teorema sostiene que N es un número primo si por cada divisor primo p de f, existe un número entero x_p tal que:

Si ${displaystyle x_{p}^{N-1}mod N, eq ,1}$ entonces N no pasa el test de primalidad que sugiere el pequeño teorema de Fermat y por lo tanto el número es compuesto. En caso contrario, si además ${displaystyle mathrm {mcd} (x_{p}^{(N-1)/p}-1,N),=,N}$ el test no puede determinar si el número es primo o compuesto y entonces hay que utilizar otro valor para x_p.

Cuando se factoriza N-1 es posible que quede un factor muy grande (mayor que la raíz cuadrada de N) y no pueda utilizarse este teorema. Si se demuestra fácilmente que dicho factor es compuesto usando el Teorema de Fermat por ejemplo, el teorema de Pocklington no se puede utilizar, en caso contrario se puede intentar usar el teorema de Pocklington sobre ese factor intentando factorizar el número inmediatamente anterior. Si se demuestra que es primo, se conocen todos los factores primos de N-1, por lo que se puede utilizar el teorema sobre el número inicial.

En el siguiente ejemplo suponemos que sólo se usará el método de división por tentativa hasta el divisor 10000.

N = 10²⁰+1663 = 100000000000000001663

N-1 = 2 × 17 × 1289 × 2179 × 4513 × 232030781

No se puede determinar si el número r = 232030781 es primo o compuesto realizando divisiones sucesivas hasta 10000, ya que r supera al cuadrado de este número. Sin embargo, como el producto de los otros factores primos es mayor que r, se puede aplicar el teorema.

Eligiendo x_p = 5 se cumple la fórmula (1) para los valores de p igual a 2, 17, 1289, 2179 y 4513, por lo que el número N es primo. En este caso se usó el mismo número x para todos los factores primos, pero esto no es necesario.