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 $N-1$ para demostrar que un número entero $N$ es primo. Produce una certeza de primalidad con menos esfuerzo que el test de Lucas, que requiere la factorización completa de $N-1$.

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 $N>1$ un entero, y supóngase que existen los números naturales Plantilla:Mvar y Plantilla:Mvar tales que:

Plantilla:NumBlk

Entonces Plantilla:Mvar es primo.

Nota: La ecuación (Plantilla:EquationNote) es simplemente un test de primalidad de Fermat. Si se encuentra cualquier valor de Plantilla:Mvar, no divisible por Plantilla:Mvar, tal que la ecuación (Plantilla:EquationNote) sea falsa, se puede concluir inmediatamente que Plantilla:Mvar no es primo (esta condición de divisibilidad no se establece explícitamente porque está implícita en la ecuación (Plantilla:EquationNote)). Por ejemplo, sea $N=35$. Con $a=2$, se tiene que $a^{N-1}\equiv 9(\mathrm{mod}N)$. Esto es suficiente para probar que Plantilla:Mvar no es primo.

Demostración

Supóngase que Plantilla:Mvar no es primo. Esto significa que debe haber un primo Plantilla:Mvar, tal que $q\le \sqrt{N}$ divide a Plantilla:Mvar. Dado que $p>\sqrt{N}-1\ge q-1$, $p>q-1$, y como Plantilla:Mvar es primo, $\mathrm{mcd}(p,q-1)=1$. Por lo tanto, debe existir un número entero Plantilla:Mvar, un inverso multiplicativo de Plantilla:Mvar módulo Plantilla:Math, con la propiedad de que     Plantilla:NumBlk y por lo tanto, por el pequeño teorema de Fermat     Plantilla:NumBlk Esto implica que $1\equiv a^{N-1}(\mathrm{mod}q)$,     por (Plantilla:EquationNote) desde $q|N$ $\equiv (a^{N-1}{)}^u\equiv a^{u(N-1)}\equiv a^{up((N-1)/p)}\equiv (a^{up}{)}^{(N-1)/p}(\mathrm{mod}q)$, $\equiv a^{(N-1)/p}(\mathrm{mod}q)$,     por (Plantilla:EquationNote) Esto demuestra que Plantilla:Mvar divide el $\mathrm{mcd}()$ en (Plantilla:EquationNote), y por lo tanto este $\mathrm{mcd}()\ne 1$; lo que implica una contradicción

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

La principal dificultad es encontrar un valor de Plantilla:Mvar que satisfaga (Plantilla:EquationNote). 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 Plantilla:Mvar, tal Plantilla:Mvar no existe. Por ejemplo, $N=17$ no tiene Plantilla:Mvar adecuado porque $N-1=2^4$ y $p=2<\sqrt{N}-1$, lo que viola la desigualdad en (Plantilla:EquationNote); otros ejemplos incluyen los números

$N=19,37,41,61,71,73,$ y $97$.

Pero dado Plantilla:Mvar, encontrar Plantilla:Mvar no es tan difícil. Si Plantilla:Mvar es primo, entonces por el pequeño teorema de Fermat, cualquier Plantilla:Mvar en el intervalo $1\le a\le N-1$ satisfará (Plantilla:EquationNote) (sin embargo, los casos $a=1$ y $a=N-1$ son triviales y no satisfarán (Plantilla:EquationNote)). Este Plantilla:Mvar satisfará (Plantilla:EquationNote) siempre que [[Orden (teoría de grupos)|ord(Plantilla:Mvar)]] no divida a $(N-1)/p$. Por lo tanto, un Plantilla:Mvar elegido al azar en el intervalo $2\le a\le N-2$ tiene buenas posibilidades de funcionar. Si Plantilla:Mvar es un generador mod Plantilla:Mvar, su orden es Plantilla:Mvar 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 $N$ son tales que no hay ningún primo $p$ que divida $N-1$ donde $p>\sqrt{N}-1$. La siguiente versión generalizada del teorema de Pocklington es más aplicable.Plantilla:Rp

Teorema: Factorícese Plantilla:Math como Plantilla:Math, donde Plantilla:Mvar y Plantilla:Mvar son primos relativos, $A>\sqrt{N}$. Se conoce la descomposición en factores primos de Plantilla:Mvar, pero no necesariamente se conoce la descomposición en factores primos de Plantilla:Mvar.

Si para cada factor primo Plantilla:Mvar de Plantilla:Mvar existe un entero $a_p$ tal que:

Plantilla:NumBlk

entonces N es primo.

Demostración

Sea Plantilla:Mvar un primo que divide a Plantilla:Mvar y sea $p^e$ la máxima potencia de Plantilla:Mvar que divide a Plantilla:Mvar. Sea Plantilla:Mvar un factor primo de Plantilla:Mvar. Para el $a_p$ del conjunto corolario $b\equiv a_p^{(N-1)/p^e}(\mathrm{mod}q)$. Esto significa que $b^{p^e}\equiv a_p^{N-1}\equiv 1(\mathrm{mod}q)$ y por $\mathrm{mcd}(a_p^{(N-1)/p}-1,N)=1$ también $b^{p^{e-1}}\equiv a_p^{(N-1)/p}\equiv ̸1(\mathrm{mod}q)$. Esto implica que el orden de $b(\mathrm{mod}q)$ es $p^e$ Por lo tanto, $p^e|(q-1)$. La misma observación vale para cada factor de potencia primo $p^e$ de A, lo que implica que $A|(q-1)$. Específicamente, esto significa que $q>A\ge \sqrt{N}.$ Si Plantilla:Mvar fuera compuesto, necesariamente tendría un factor primo menor o igual que $\sqrt{N}$. Se ha demostrado que no existe tal factor, lo que prueba que Plantilla:Mvar 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 Plantilla:Math para que el producto de esos factores exceda $\sqrt{N}$. Denomínese a este producto Plantilla:Mvar. Luego, sea Plantilla:Math la porción restante no factorizada de Plantilla:Math. No importa si Plantilla:Mvar es primo. Solo se necesita verificar que ningún primo que divide a Plantilla:Mvar también divide a Plantilla:Mvar, es decir, que Plantilla:Mvar y Plantilla:Mvar son primos relativos. Luego, para cada factor primo Plantilla:Mvar de Plantilla:Mvar, encuéntrese un $a_p$ que cumpla las condiciones (Plantilla:EquationNote) y (Plantilla:EquationNote) del corolario. Si se pueden encontrar tales $a_p$, el corolario implica que Plantilla:Mvar es primo.

Según Koblitz, $a_p$= 2 suele funcionar.

Ejemplo

Determinar si

$N=27457$

es primo

Primero, búsquense pequeños factores primos de $N-1$. Rápidamente se encuentra que

$N-1=2^6\cdot 3\cdot B=192\cdot B$.

Se debe determinar si $A=192$ y $B=(N-1)/A=143$ cumplen las condiciones del corolario.

$A^2=36864>N$, y así $A>\sqrt{N}$.

Por lo tanto, se ha factorizado lo suficiente de $N-1$ para aplicar el corolario. También se debe verificar que $\mathrm{mcd}(A,B)=1$.

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

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

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

$a_2^{N-1}\equiv 2^{27456}\equiv 1(\mathrm{mod}27457)$

$\mathrm{mcd}(a_2^{(N-1)/2}-1,N)=\mathrm{mcd}(2^{13728}-1,27457)=27457$.

Entonces, $a_2=2$ satisface (Plantilla:EquationNote) pero no (Plantilla:EquationNote). Como se permite un Plantilla:Mvar diferente para cada Plantilla:Mvar, pruébese $a_2=5$ en su lugar:

$a_2^{N-1}\equiv 5^{27456}\equiv 1(\mathrm{mod}27457)$

$\mathrm{mcd}(a_2^{(N-1)/2}-1,N)=\mathrm{mcd}(5^{13728}-1,27457)=1$.

Entonces $a_2=5$ satisface tanto (Plantilla:EquationNote) como (Plantilla:EquationNote).

Para $p=3$, el segundo factor primo de Plantilla:Mvar, pruébese con $a_3=2$:

$a_3^{N-1}\equiv 2^{27456}\equiv 1(\mathrm{mod}27457)$.

$\mathrm{mcd}(a_3^{(N-1)/3}-1,N)=\mathrm{mcd}(2^{9152}-1,27457)=1$.

$a_3=2$ satisface tanto (Plantilla:EquationNote) como (Plantilla:EquationNote).

Esto completa la demostración de que $N=27457$ es primo. La certeza de primalidad para $N=27457$ está basada en los dos pares $(p,a_p)$ (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 Plantilla:Mvar se pueden obtener factores que son en sí mismos tan grandes que su primalidad no es obvia. No se puede probar que Plantilla:Mvar es primo sin probar que los factores de Plantilla:Mvar también son primos. En tal caso, se usa la misma prueba recursivamente en los factores grandes de Plantilla:Mvar, 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 $(p,a_p)$, 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 Plantilla:Mvar que corresponden a los factores 'primos' de Plantilla:Mvar. Luego, para cada factor de Plantilla:Mvar donde la primalidad era incierta, se tendrían más Plantilla:Mvar, 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 Plantilla:Mvar 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 $N-1=mp$ donde Plantilla:Mvar es un primo impar tal que $2p+1>\sqrt{N}$. Si existe un Plantilla:Mvar para el cual $a^{(N-1)/2}\equiv -1(\mathrm{mod}N)$, pero $a^{m/2}\equiv ̸-1(\mathrm{mod}N)$, entonces Plantilla:Mvar es primo.

Si Plantilla:Mvar es grande, a menudo es difícil factorizar lo suficiente de $N-1$ 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 $(N/2{)}^{1/3}$. Se presentan muchos teoremas adicionales que permiten probar la primalidad de Plantilla:Mvar con base en la factorización parcial de $N-1$ and $N+1$.

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.