Test de Pocklington-Lehmer

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

La prueba utiliza una factorización parcial de ${\displaystyle N-1}$ para demostrar que un número entero ${\displaystyle N}$ es primo. Produce una certeza de primalidad con menos esfuerzo que el test de Lucas, que requiere la factorización completa de ${\displaystyle 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 ${\displaystyle N>1}$ un entero, y supóngase que existen los números naturales a y p tales que:

${\displaystyle a^{N-1}\equiv 1{\pmod {N}}}$ (1) p es primo, ${\displaystyle p\vert N-1}$ and ${\displaystyle p>{\sqrt {N}}-1}$ (2) ${\displaystyle \operatorname {mcd} {(a^{(N-1)/p}-1,N)}=1}$ (3)

Entonces N es primo.^[3]

Nota: La ecuación (1) es simplemente un test de primalidad de Fermat. 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)). Por ejemplo, sea ${\displaystyle N=35}$. Con ${\displaystyle a=2}$, se tiene que ${\displaystyle a^{N-1}\equiv 9{\pmod {N}}}$. Esto es suficiente para probar que N no es primo.

Demostración

Supóngase que N no es primo. Esto significa que debe haber un primo q, tal que ${\displaystyle q\leq {\sqrt {N}}}$ divide a N. Dado que ${\displaystyle p>{\sqrt {N}}-1\geq q-1}$, ${\displaystyle p>q-1}$, y como p es primo, ${\displaystyle \operatorname {mcd} {(p,q-1)}=1}$. Por lo tanto, debe existir un número entero u, un inverso multiplicativo de p módulo q−1, con la propiedad de que     ${\displaystyle up\equiv 1{\pmod {q-1}}}$ (4) y por lo tanto, por el pequeño teorema de Fermat     ${\displaystyle a^{up}\equiv a{\pmod {q}}}$ (5) Esto implica que ${\displaystyle 1\;\;\equiv a^{N-1}{\pmod {q}}}$,     por (1) desde ${\displaystyle q\vert N}$ ${\displaystyle \equiv (a^{N-1})^{u}\equiv a^{u(N-1)}\equiv a^{up((N-1)/p)}\equiv (a^{up})^{(N-1)/p}{\pmod {q}}}$, ${\displaystyle \equiv a^{(N-1)/p}{\pmod {q}}}$,     por (5) Esto demuestra que q divide el ${\displaystyle \operatorname {mcd} ()}$ en (3), y por lo tanto este ${\displaystyle \operatorname {mcd} ()\neq 1}$; 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 primer lugar, suele ser difícil encontrar un factor primo grande de un número grande. En segundo lugar, para muchos números primos N, tal p no existe. Por ejemplo, ${\displaystyle N=17}$ no tiene p adecuado porque ${\displaystyle N-1=2^{4}}$ y ${\displaystyle p=2<{\sqrt {N}}-1}$, lo que viola la desigualdad en (2); otros ejemplos incluyen los números

${\displaystyle N=19,37,41,61,71,73,}$ y ${\displaystyle 97}$.

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 ${\displaystyle 1\leq a\leq N-1}$ satisfará (1) (sin embargo, los casos ${\displaystyle a=1}$ y ${\displaystyle a=N-1}$ son triviales y no satisfarán (3)). Este a satisfará (3) siempre que ord(a) no divida a ${\displaystyle (N-1)/p}$. Por lo tanto, un a elegido al azar en el intervalo ${\displaystyle 2\leq a\leq N-2}$ tiene buenas posibilidades de funcionar. 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.

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 ${\displaystyle N}$ son tales que no hay ningún primo ${\displaystyle p}$ que divida ${\displaystyle N-1}$ donde ${\displaystyle p>{\sqrt {N}}-1}$. La siguiente versión generalizada del teorema de Pocklington es más aplicable.^{[5]: Corollary 1}

Teorema: Factorícese N − 1 como N − 1= AB, donde A y B son primos relativos, ${\displaystyle A>{\sqrt {N}}}$. 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 ${\displaystyle a_{p}}$ tal que:

${\displaystyle a_{p}^{N-1}\equiv 1{\pmod {N}}}$, and (6) ${\displaystyle \operatorname {mcd} {(a_{p}^{(N-1)/p}-1,N)}=1}$, (7)

entonces N es primo.

Demostración

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

Según Koblitz, ${\displaystyle a_{p}}$= 2 suele funcionar.^[3]

Ejemplo

Determinar si

${\displaystyle N=27457}$

es primo

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

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

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

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

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

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

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

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

${\displaystyle a_{2}^{N-1}\equiv 2^{27456}\equiv 1{\pmod {27457}}}$

${\displaystyle \operatorname {mcd} {(a_{2}^{(N-1)/2}-1,N)}=\operatorname {mcd} {(2^{13728}-1,27457)}=27457}$.

Entonces, ${\displaystyle a_{2}=2}$ satisface (6) pero no (7). Como se permite un a_p diferente para cada p, pruébese ${\displaystyle a_{2}=5}$ en su lugar:

${\displaystyle a_{2}^{N-1}\equiv 5^{27456}\equiv 1{\pmod {27457}}}$

${\displaystyle \operatorname {mcd} {(a_{2}^{(N-1)/2}-1,N)}=\operatorname {mcd} {(5^{13728}-1,27457)}=1}$.

Entonces ${\displaystyle a_{2}=5}$ satisface tanto (6) como (7).

Para ${\displaystyle p=3}$, el segundo factor primo de A, pruébese con ${\displaystyle a_{3}=2}$:

${\displaystyle a_{3}^{N-1}\equiv 2^{27456}\equiv 1{\pmod {27457}}}$.

${\displaystyle \operatorname {mcd} {(a_{3}^{(N-1)/3}-1,N)}=\operatorname {mcd} {(2^{9152}-1,27457)}=1}$.

${\displaystyle a_{3}=2}$ satisface tanto (6) como (7).

Esto completa la demostración de que ${\displaystyle N=27457}$ es primo. La certeza de primalidad para ${\displaystyle N=27457}$ está basada en los dos pares ${\displaystyle (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 A se pueden obtener factores que son en sí mismos tan grandes que su primalidad no es obvia. No se puede probar que N es primo sin probar que los factores de A también son primos. 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. El certificado de primalidad es la lista de pares ${\displaystyle (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 a_p que corresponden a los factores 'primos' de A. Luego, para cada factor de A donde la primalidad era incierta, se tendrían más a_p, 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 a_p correspondientes, que se pueden verificar fácilmente.

Extensiones y variantes

El artículo de 1975 de Brillhart, Lehmer y Selfridge^[5] 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 ${\displaystyle N-1=mp}$ donde p es un primo impar tal que ${\displaystyle 2p+1>{\sqrt {N}}}$. Si existe un a para el cual ${\displaystyle a^{(N-1)/2}\equiv -1{\pmod {N}}}$, pero ${\displaystyle a^{m/2}\not \equiv -1{\pmod {N}}}$, entonces N es primo.

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

Referencias

1. Pocklington, Henry C. (1914–1916). «The determination of the prime or composite nature of large numbers by Fermat's theorem». Proceedings of the Cambridge Philosophical Society 18: 29-30. Consultado el 22 de junio de 2022.
2. D. H. Lehmer (1927). «Tests for primality by the converse of Fermat's theorem». Bull. Amer. Math. Soc. 33 (3): 327-340. doi:10.1090/s0002-9904-1927-04368-3.
3. Koblitz, Neal (1994). A Course in Number Theory and Cryptography. Graduate Texts in Mathematics 144 (2nd edición). Springer. ISBN 0-387-94293-9.
4. Roberto Avanzi, Henri Cohen, Christophe Doche, Gerhard Frey, Tanja Lange, Kim Nguyen, Frederik Vercauteren (2005). Handbook of Elliptic and Hyperelliptic Curve Cryptography. Boca Raton: Chapman & Hall/CRC.
5. Brillhart, John; Lehmer, D. H.; Selfridge, J. L. (April 1975). «New Primality Criteria and Factorizations of 2^m ± 1». Mathematics of Computation 29 (130): 620-647. JSTOR 2005583. doi:10.1090/S0025-5718-1975-0384673-1.
6. The classical tests

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.

• Datos: Q4241328