Test de Pocklington-Lehmer

En matemáticas, el test de Pocklington-Lehmer es una prueba de primalidad ideada por Henry Cabourn Pocklington y por Derrick Henry Lehmer.

La prueba utiliza una factorización parcial de  para demostrar que un número entero  es primo. Produce una certeza de primalidad con menos esfuerzo que el test de Lucas, que requiere la factorización completa de .

Criterio de Pocklington
La versión básica de la prueba se basa en el teorema de Pocklington (o criterio de Pocklington) que se formula de la siguiente manera:

Sea  un entero, y supóngase que existen los números naturales  y  tales que:

Entonces  es primo.

Nota: La ecuación () es simplemente un test de primalidad de Fermat. Si se encuentra cualquier valor de , no divisible por , tal que la ecuación () sea falsa, se puede concluir inmediatamente que  no es primo (esta condición de divisibilidad no se establece explícitamente porque está implícita en la ecuación ()). Por ejemplo, sea . Con , se tiene que . Esto es suficiente para probar que  no es primo.

Dado , si se pueden encontrar  y  que satisfagan las condiciones del teorema, entonces  es primo. Además, el par (, ) constituye una certeza de primalidad que puede verificarse rápidamente para satisfacer las condiciones del teorema, confirmando que  es primo.

La principal dificultad es encontrar un valor de  que satisfaga (). En primer lugar, suele ser difícil encontrar un factor primo grande de un número grande. En segundo lugar, para muchos números primos , tal  no existe. Por ejemplo,  no tiene  adecuado porque  y , lo que viola la desigualdad en (); otros ejemplos incluyen los números

 y .

Pero dado , encontrar  no es tan difícil. Si  es primo, entonces por el pequeño teorema de Fermat, cualquier  en el intervalo  satisfará () (sin embargo, los casos  y  son triviales y no satisfarán ()). Este  satisfará () siempre que ord() no divida a . Por lo tanto, un  elegido al azar en el intervalo  tiene buenas posibilidades de funcionar. Si  es un generador mod , su orden es  y, por lo tanto, se garantiza que el método funcionará para esta elección.

Prueba de Pocklington generalizada
La versión anterior de la versión del teorema de Pocklington a veces es imposible de aplicar porque algunos primos  son tales que no hay ningún primo  que divida  donde . La siguiente versión generalizada del teorema de Pocklington es más aplicable.

Teorema: Factorícese  como , donde  y  son primos relativos, . Se conoce la descomposición en factores primos de , pero no necesariamente se conoce la descomposición en factores primos de .

Si para cada factor primo  de  existe un entero  tal que:

entonces N es primo.

Comentarios
La prueba de primalidad de Pocklington-Lehmer se deriva directamente de este corolario.

Para usar este corolario, primero encuentre suficientes factores de  para que el producto de esos factores exceda .
Denomínese a este producto .
Luego, sea  la porción restante no factorizada de . No importa si  es primo.
Solo se necesita verificar que ningún primo que divide a  también divide a , es decir, que  y  son primos relativos.
Luego, para cada factor primo  de , encuéntrese un  que cumpla las condiciones () y () del corolario.
Si se pueden encontrar tales , el corolario implica que  es primo.

Según Koblitz, = 2 suele funcionar.

Ejemplo 
Determinar si
 
es primo

Primero, búsquense pequeños factores primos de .
Rápidamente se encuentra que
 .
Se debe determinar si  y  cumplen las condiciones del corolario.

, y así .

Por lo tanto, se ha factorizado lo suficiente de  para aplicar el corolario.
También se debe verificar que .

No importa si  es primo (de hecho, no lo es).

Finalmente, para cada factor primo  de , úsese el método de prueba y error para encontrar un  que satisfaga () y ().

Para , pruébese con .
Elevar  a esta alta potencia se puede hacer de manera eficiente usando exponenciación binaria:

 
 .

Entonces,  satisface () pero no (). Como se permite un  diferente para cada , pruébese  en su lugar:

 
 .

Entonces  satisface tanto () como ().

Para , el segundo factor primo de , pruébese con :

 .
 .

 satisface tanto () como ().

Esto completa la demostración de que  es primo.
La certeza de primalidad para  está basada en los dos pares  (2, 5) y (3, 2).

Se han elegido números pequeños para este ejemplo, pero en la práctica cuando se comienza a factorizar  se pueden obtener factores que son en sí mismos tan grandes que su primalidad no es obvia. No se puede probar que  es primo sin probar que los factores de  también son primos. En tal caso, se usa la misma prueba recursivamente en los factores grandes de , hasta que todos los números primos estén por debajo de un umbral razonable.

En el ejemplo anterior, se puede decir con certeza que 2 y 3 son primos, y así se ha probado el resultado obtenido. El certificado de primalidad es la lista de pares , que se puede comprobar rápidamente en el corolario.

Si el ejemplo hubiera incluido grandes factores primos, el certificado sería más complicado. Primero consistiría en la ronda inicial de  que corresponden a los factores 'primos' de . Luego, para cada factor de  donde la primalidad era incierta, se tendrían más , y así sucesivamente para los factores de estos factores hasta llegar a los factores de los que la primalidad es cierta. Este proceso puede continuar en muchas capas sucesivas si el primo inicial es grande, pero el punto importante es que se puede generar un certificado que contenga en cada nivel el primo que se probará y los  correspondientes, que se pueden verificar fácilmente.

Extensiones y variantes

El artículo de 1975 de Brillhart, Lehmer y Selfridge ofrece una prueba de lo que se muestra arriba como el "teorema de Pocklington generalizado" como Teorema 4 en la página 623. Se muestran teoremas adicionales que permiten menos factores. Esto incluye su Teorema 3 (una versión reforzada de un teorema de Proth de 1878):

 Sea  donde  es un primo impar tal que . Si existe un  para el cual , pero , entonces  es primo.

Si  es grande, a menudo es difícil factorizar lo suficiente de  para aplicar el corolario anterior. El teorema 5 del artículo de Brillhart, Lehmer y Selfridge permite una prueba de primalidad cuando la parte factorizada ha alcanzado solo . Se presentan muchos teoremas adicionales que permiten probar la primalidad de  con base en la factorización parcial de  and .

Referencias

Bibliografía
 Leonard Eugene Dickson, "History of the Theory of Numbers" vol 1, p 370, Chelsea Publishing 1952
 Henry Pocklington, "Math. Quest. Educat. Times", (2), 25, 1914, p 43-46 (Mathematical questions and solutions in continuation of the mathematical columns of "the Educational times".)

Enlaces externos
Chris Caldwell, "Primality Proving 3.1: n-1 tests and the Pepin's tests for Fermats" at the  Prime Pages.
Chris Caldwell, "Primality Proving 3.2: n+1 tests and the Lucas-Lehmer test for Mersennes" at the  Prime Pages.

Tests de primalidad
Pocklington-Lehmer, test