Prueba de primacía de Pocklington

En matemáticas, la prueba de primalidad de Pocklington - Lehmer es una prueba de primalidad ideada por Henry Cabourn Pocklington ^{[ 1 ]} y Derrick Henry Lehmer . ^{[ 2 ]} La prueba utiliza una factorización parcial de $N-1$ para demostrar que un entero $N$ es primordial .

Produce un certificado de primalidad que se puede encontrar con menos esfuerzo que la prueba de primalidad 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:

Dejar $N>1$ Sea un número entero, y supongamos que existen números naturales $a$ y $p$ tales que

Entonces $N$ es primo. ^{[ 3 ]} Aquí $i\equiv j{\pmod {k}}$ significa que después de encontrar el resto de la división por k , i y j son iguales; $i\vert j$ significa que i es un divisor de j ; y mcd es el máximo común divisor .

Nota: La ecuación ( 1 ) es simplemente una prueba de primalidad de Fermat . Si encontramos algún valor de $a$ , no divisible por $N$ , tal que la ecuación ( 1 ) sea falsa, podemos 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 $N=35$ . Con $a=2$ , encontramos que $a^{N-1}\equiv 9{\pmod {N}}$ Esto es suficiente para demostrar que $N$ no es primo.

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 un certificado de primalidad que se puede verificar rápidamente para comprobar que satisface las condiciones del teorema, confirmando así que $N$ es primo.

La principal dificultad radica en 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 primos $N$ , tal $p$ no existe. Por ejemplo, $N=17$ no tiene $p$ adecuado porque $N-1=2^{4}$ , y $p=2<{\sqrt {N}}-1$ , lo cual viola la desigualdad en ( 2 ) ; otros ejemplos incluyen $N=19,37,41,61,71,73,$ y $97$ .

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 $1\leq a\leq N-1$ satisfará ( 1 ) (sin embargo, los casos $a=1$ y $a=N-1$ son triviales y no satisfarán ( 3 )). Esto $a$ satisfará ( 3 ) siempre que ord( $a$ ) no divida $(N-1)/p$ . Por lo tanto, un valor a elegido al azar $en$ el intervalo $2\leq a\leq N-2$ tiene una buena probabilidad de funcionar. Si $a$ es un generador módulo $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 del teorema de Pocklington a veces es imposible de aplicar porque algunos números primos $N$ son tales que no hay primo $p$ divisor $N-1$ dónde $p>{\sqrt {N}}-1$ La siguiente versión generalizada del teorema de Pocklington es de aplicación más amplia. ^{[ 5 ]}^{: Corolario 1}

Teorema: Factorizar $N - 1$ como $N - 1 = AB$ , donde $A$ y $B$ son primos relativos, $A>{\sqrt {N}}$ Se conoce la factorización prima de $A$ , pero no necesariamente se conoce la factorización de $B.$

Si para cada factor primo $p$ de $A$ existe un entero $a_{p}$ de modo que

entonces N es primo.

Comentarios

La prueba de primalidad de Pocklington-Lehmer se deriva directamente de este corolario. Para utilizar este corolario, primero hay que encontrar suficientes factores de $N - 1$ de modo que el producto de esos factores supere ${\sqrt {N}}$ Llamemos a este producto $A.$ Entonces, sea $B = (N - 1)/ A$ la porción restante, no factorizada, de $N - 1.$ No importa si $B$ es primo. Simplemente necesitamos verificar que ningún primo que divida $a A$ también divida $a B$ , es decir, que $A$ y $B$ sean primos entre sí. Entonces, para cada factor primo $p$ de $A$ , encontremos un $a_{p}$ que cumple las condiciones ( 6 ) y ( 7 ) del corolario. Si tal $a_{p}$ Se puede encontrar s, el corolario implica que $N$ es primo.

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

Ejemplo

Determinar si

N=27457

es primordial.

Primero, busque factores primos pequeños de $N-1$ . Rápidamente descubrimos que

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

.

Debemos determinar si $A=192$ y $B=(N-1)/A=143$ cumplir las condiciones del Corolario. $A^{2}=36864>N$ , entonces $A>{\sqrt {N}}$ . Por lo tanto, hemos tenido en cuenta suficientes factores. $N-1$ para aplicar el corolario. También debemos verificar que $\gcd {(A,B)}=1$ .

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

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

Para $p=2$ , intentar $a_{2}=2$ . Recaudar $a_{2}$ Esta alta potencia se puede alcanzar de manera eficiente mediante la exponenciación binaria :

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

\gcd {(a_{2}^{(N-1)/2}-1,N)}=\gcd {(2^{13728}-1,27457)}=27457

.

Entonces, $a_{2}=2$ satisface ( 6 ) pero no ( 7 ) . Como se nos permite un $a p$ diferente para cada $p$ , intente $a_{2}=5$ en cambio:

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

\gcd {(a_{2}^{(N-1)/2}-1,N)}=\gcd {(5^{13728}-1,27457)}=1

.

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

Para $p=3$ , el segundo factor primo de $A$ , intenta $a_{3}=2$ :

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

.

\gcd {(a_{3}^{(N-1)/3}-1,N)}=\gcd {(2^{9152}-1,27457)}=1

.

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

Esto completa la prueba de que $N=27457$ es primordial. El certificado de primacía para $N=27457$ constaría de los dos $(p,a_{p})$ pares (2, 5) y (3, 2).

Hemos elegido números pequeños para este ejemplo, pero en la práctica, al factorizar $A,$ podemos obtener factores tan grandes que su primalidad no resulta evidente. No podemos demostrar que $N$ es primo sin demostrar también que los factores de $A$ lo son. En tal caso, aplicamos la misma prueba recursivamente a los factores grandes de $A$ , hasta que todos los números primos estén por debajo de un umbral razonable.

En nuestro ejemplo, podemos decir con certeza que 2 y 3 son primos, y por lo tanto hemos demostrado nuestro resultado. El certificado de primalidad es la lista de $(p,a_{p})$ pares, que pueden comprobarse rápidamente en el corolario.

Si nuestro ejemplo hubiera incluido factores primos grandes, el certificado sería más complejo. Primero consistiría en nuestra ronda inicial de $a p$ s que corresponden a los factores "primos" de $A$ ; luego, para cada factor de $A$ cuya primalidad sea incierta, tendríamos más $a p$ , y así sucesivamente para los factores de estos factores hasta llegar a los factores cuya primalidad sea segura. Esto puede continuar durante muchas capas si el primo inicial es grande, pero lo importante es que se puede producir un certificado que contenga en cada nivel el primo que se va a probar y los $a p$ s correspondientes, que se pueden verificar fácilmente.

Extensiones y variantes

El artículo de Brillhart, Lehmer y Selfridge de 1975 ^{[ 5 ]} proporciona una demostración de lo que se muestra arriba como el "teorema generalizado de Pocklington" como Teorema 4 en la página 623. Se muestran teoremas adicionales que permiten una menor factorización. Esto incluye su Teorema 3 (un fortalecimiento de un teorema de Proth de 1878):

Dejar

N-1=mp

donde

p

es un primo impar tal que

2p+1>{\sqrt {N}}

. Si existe un

a

para el cual

a^{(N-1)/2}\equiv -1{\pmod {N}}

, pero

a^{m/2}\not \equiv -1{\pmod {N}}

, entonces

N

es primo.

Si $N$ es grande, a menudo es difícil factorizar lo suficiente $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 de este tipo que permiten demostrar la primalidad de $N$ basándose en la factorización parcial de $N-1$ , $N+1$ , $N^{2}+1$ , y $N^{2}\pm N+1$ . ^{[ 5 ]}^{[ 6 ]}^{[ 7 ]}

Referencias

Leonard Eugene Dickson, "Historia de la teoría de los números", vol. 1, pág. 370, Chelsea Publishing, 1952.
Henry Pocklington, "Math. Quest. Educat. Times", (2), 25, 1914, págs. 43-46 (Preguntas y soluciones matemáticas como continuación de las columnas matemáticas de "The Educational Times").

↑ Pocklington, Henry C. (1914–1916). "La determinación de la naturaleza prima o compuesta de los números grandes mediante el teorema de Fermat" . Actas de la Sociedad Filosófica de Cambridge . 18 : 29–30 . Consultado el 22 de junio de 2022 .
↑ DH Lehmer (1927). "Pruebas de primalidad mediante el recíproco del teorema de Fermat" . Bull. Amer. Math. Soc . 33 (3): 327– 340. doi : 10.1090/s0002-9904-1927-04368-3 .
1 2 3 Koblitz, Neal (1994). Un curso de teoría de números y criptografía . Textos de posgrado en matemáticas. Vol. 144 (2.ª ed.). Springer. ISBN 0-387-94293-9.
↑ Roberto Avanzi; Henri Cohen; Christophe Doche; Gerhard Frey; Tanja Lange ; Kim Nguyen; Frederik Vercauteren (2005). Manual de criptografía de curvas elípticas e hiperelípticas . Boca Ratón: Chapman & Hall/CRC.
1 2 3 Brillhart, John ; Lehmer, DH ; Selfridge, JL (abril de 1975). "Nuevos criterios de primalidad y factorizaciones de 2 ^m ± 1" (PDF) . Matemáticas de la computación . 29 (130): 620– 647. doi : 10.1090/S0025-5718-1975-0384673-1 . JSTOR 2005583 .
↑ Williams, Hugh C.; Holte, R. (julio de 1978). "Algunas observaciones sobre la prueba de primalidad" . Mathematics of Computation . 32 (143): 905– 917. doi : 10.2307/2006495 . JSTOR 2006495 .
↑ Las pruebas clásicas

Enlaces externos

Chris Caldwell, "Prueba de primalidad 3.1: pruebas n-1 y las pruebas de Pepin para Fermats" en Prime Pages .
Chris Caldwell, "Prueba de primalidad 3.2: pruebas n+1 y la prueba de Lucas-Lehmer para Mersennes" en Prime Pages .

[Pocklington-1] Pocklington, Henry C. (1914–1916). "La determinación de la naturaleza prima o compuesta de los números grandes mediante el teorema de Fermat" . Actas de la Sociedad Filosófica de Cambridge . 18 : 29–30 . Consultado el 22 de junio de 2022 .

[Lehmer-2] DH Lehmer (1927). "Pruebas de primalidad mediante el recíproco del teorema de Fermat" . Bull. Amer. Math. Soc . 33 (3): 327– 340. doi : 10.1090/s0002-9904-1927-04368-3 .

[koblitz-3] 1 2 3 Koblitz, Neal (1994). Un curso de teoría de números y criptografía . Textos de posgrado en matemáticas. Vol. 144 (2.ª ed.). Springer. ISBN 0-387-94293-9.

[4] Roberto Avanzi; Henri Cohen; Christophe Doche; Gerhard Frey; Tanja Lange ; Kim Nguyen; Frederik Vercauteren (2005). Manual de criptografía de curvas elípticas e hiperelípticas . Boca Ratón: Chapman & Hall/CRC.

[BLS75-5] 1 2 3 Brillhart, John ; Lehmer, DH ; Selfridge, JL (abril de 1975). "Nuevos criterios de primalidad y factorizaciones de 2 ^m ± 1" (PDF) . Matemáticas de la computación . 29 (130): 620– 647. doi : 10.1090/S0025-5718-1975-0384673-1 . JSTOR 2005583 .

[6] Williams, Hugh C.; Holte, R. (julio de 1978). "Algunas observaciones sobre la prueba de primalidad" . Mathematics of Computation . 32 (143): 905– 917. doi : 10.2307/2006495 . JSTOR 2006495 .

[7] Las pruebas clásicas

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]