En matemáticas, el test de Pocklington-Lehmer es una prueba de primalidad ideada por Henry Cabourn Pocklington[1] y por Derrick Henry Lehmer.
Si se encuentra cualquier valor de a, no divisible por N, tal que la ecuación (1) sea falsa, se puede concluir inmediatamente que N no es primo (esta condición de divisibilidad no se establece explícitamente porque está implícita en la ecuación (3)).
Esto es suficiente para probar que N no es primo.
; lo que implica una contradicción[3] Dado N, si se pueden encontrar p y a que satisfagan las condiciones del teorema, entonces N es primo.
Además, el par (p, a) constituye una certeza de primalidad que puede verificarse rápidamente para satisfacer las condiciones del teorema, confirmando que N es primo.
La principal dificultad es encontrar un valor de p que satisfaga (2).
En segundo lugar, para muchos números primos N, tal p no existe.
, lo que viola la desigualdad en (2); otros ejemplos incluyen los números Pero dado p, encontrar a no es tan difícil.
[4] Si N es primo, entonces por el pequeño teorema de Fermat, cualquier a en el intervalo
Si a es un generador mod N, su orden es N-1 y, por lo tanto, se garantiza que el método funcionará para esta elección.
son tales que no hay ningún primo
La siguiente versión generalizada del teorema de Pocklington es más aplicable.
Se conoce la descomposición en factores primos de A, pero no necesariamente se conoce la descomposición en factores primos de B.
Si para cada factor primo p de A existe un entero
Sea q un factor primo de N. Para el
del conjunto corolario Esto implica que el orden de
La misma observación vale para cada factor de potencia primo
Si N fuera compuesto, necesariamente tendría un factor primo menor o igual que
Para usar este corolario, primero encuentre suficientes factores de N − 1 para que el producto de esos factores exceda
Luego, para cada factor primo p de A, encuéntrese un
Finalmente, para cada factor primo p de A, úsese el método de prueba y error para encontrar un ap que satisfaga (6) y (7).
a esta alta potencia se puede hacer de manera eficiente usando exponenciación binaria: Entonces,
Como se permite un ap diferente para cada p, pruébese
Se han elegido números pequeños para este ejemplo, pero en la práctica cuando se comienza a factorizar A se pueden obtener factores que son en sí mismos tan grandes que su primalidad no es obvia.
En tal caso, se usa la misma prueba recursivamente en los factores grandes de A, 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.
Si el ejemplo hubiera incluido grandes factores primos, el certificado sería más complicado.
Se muestran teoremas adicionales que permiten menos factores.
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 N con base en la factorización parcial de