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 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 a y p tales que:

   

 

 

 

 

(1)

p es primo, and

 

 

 

 

(2)

 

 

 

 

(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 . Con , se tiene que . 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 divide a N.

Dado que , , y como p es primo, .

Por lo tanto, debe existir un número entero u, un inverso multiplicativo de p módulo q−1, con la propiedad de que

   

 

 

 

 

(4)

y por lo tanto, por el pequeño teorema de Fermat

   

 

 

 

 

(5)

Esto implica que

,     por (1) desde
,
,     por (5)

Esto demuestra que q divide el en (3), y por lo tanto este ; 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, no tiene p adecuado porque y , lo que viola la desigualdad en (2); otros ejemplos incluyen los números

y .

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 satisfará (1) (sin embargo, los casos y son triviales y no satisfarán (3)). Este a satisfará (3) siempre que ord(a) no divida a . Por lo tanto, un a elegido al azar en el intervalo 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 son tales que no hay ningún primo que divida donde . 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, . 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 tal que:

   

, and

 

 

 

 

(6)

,

 

 

 

 

(7)

entonces N es primo.

Demostración
Sea p un primo que divide a A y sea la máxima potencia de p que divide a A.

Sea q un factor primo de N. Para el del conjunto corolario

. Esto significa que
y por también
.

Esto implica que el orden de es

Por lo tanto, . La misma observación vale para cada factor de potencia primo de A, lo que implica que .

Específicamente, esto significa que

Si N fuera compuesto, necesariamente tendría un factor primo menor o igual que . 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 . 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 que cumpla las condiciones (6) y (7) del corolario. Si se pueden encontrar tales , el corolario implica que N es primo.

Según Koblitz, = 2 suele funcionar.[3]

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 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 ap que satisfaga (6) y (7).

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

.

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

.

Entonces satisface tanto (6) como (7).

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

.
.

satisface tanto (6) como (7).

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 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 , 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 ap que corresponden a los factores 'primos' de A. Luego, para cada factor de A donde la primalidad era incierta, se tendrían más ap, 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 ap 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 donde p es un primo impar tal que . Si existe un a para el cual , pero , entonces N es primo.

Si N 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 N con base en la factorización parcial de and .[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. a b c 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. a b c Brillhart, John; Lehmer, D. H.; Selfridge, J. L. (April 1975). «New Primality Criteria and Factorizations of 2m ± 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