En matemáticas, la prueba de primalidad de Pocklington-Lehmer es una prueba de primordialidad ideada por Henry Cabourn Pocklington [1] y Derrick Henry Lehmer . [2] La prueba utiliza una factorización parcial de para demostrar que un entero es primordial .
Produce un certificado de primalidad que se encuentra con menos esfuerzo que la prueba de primalidad 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:
Dejar ser un número entero, y supongamos que hay números EXIST una y p tal que
( 1 )
- p es primo, y
( 2 )
( 3 )
Entonces N es primo. [3]
Nota: La ecuación ( 1 ) es simplemente una prueba de primalidad de Fermat . Si encontramos cualquier valor de a , no divisible por N , tal que la ecuación ( 1 ) es 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. Con, encontramos eso . Esto es suficiente para demostrar que N no es primo.
Prueba de este teorema
Suponga que N no es primo. Esto significa que debe haber un primo q , dondeque divide N .
Desde , , y dado que p es primo,.
Por tanto, debe existir un entero u , un inverso multiplicativo de p módulo q −1 , con la propiedad de que
( 4 )
y por lo tanto, según el pequeño teorema de Fermat
( 5 )
Esto implica
Esto muestra que q divide elen ( 3 ) , y por lo tanto este; una contradicción. [3]
Dada N , si p y un se puede encontrar que satisfacen las condiciones del teorema, entonces N es primo. Además, el par ( p , a ) constituye un certificado de primordialidad que puede verificarse rápidamente para satisfacer las condiciones del teorema, confirmando N como 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 elevado. En segundo lugar, para muchos números primos N , tal p no existe. Por ejemplo,no tiene p adecuado porque, y , que viola la desigualdad en ( 2 ) .
Dado p , encontrar a no es tan difícil. [4] Si N es primo, entonces, según el pequeño teorema de Fermat, cualquier a en el intervalosatisfará ( 1 ) (sin embargo, los casos y son triviales y no satisfacen ( 3 )). Este a satisfará ( 3 ) siempre que ord ( a ) no divida. Así, un elegido al azar una en el intervalotiene buenas posibilidades de funcionar. Si a es un generador mod N , su orden es por lo que se garantiza que el método funcionará para esta elección.
Prueba de Pocklington generalizada
Una versión generalizada del teorema de Pocklington es más ampliamente aplicable porque no requiere encontrar un solo factor primo grande de; También, permite que un valor diferente de una a ser utilizado para cada factor primo conocida de. [5] : Corolario 1
Teorema: Factor N - 1 como N - 1 = AB , donde A y B son primos relativos,, 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 número entero así que eso
- , y
( 6 )
- ,
( 7 )
entonces N es primo.
Prueba: Sea p un primo que divide A y seaser la potencia máxima de p dividiendo A . Deje q sea un factor primordial de N . Para el del conjunto de corolarios . Esto significa y debido a además .
Esto significa que el orden de es
Por lo tanto, . La misma observación es válida para cada factor de potencia principal.de A , lo que implica.
Específicamente, esto significa
Si N fuera compuesto, necesariamente tendría un factor primo menor o igual a. Se ha demostrado que no existe tal factor, lo que prueba que N es primo.
La prueba
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. Llame a este producto una . 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 también divide a B , es decir, que A y B son primos relativos. Entonces, para cada factor primo p de A , encuentre unque cumpla las condiciones ( 6 ) y ( 7 ) del corolario. Si tals, el Corolario implica que N es primo.
Según Koblitz, = 2 a menudo funciona. [3]
Ejemplo
Determinar si
es primordial.
Primero, busque pequeños factores primos de . Rápidamente encontramos eso
- .
Debemos determinar si y cumplen las condiciones del Corolario. , entonces . Por lo tanto, hemos factorizado suficientespara aplicar el Corolario. También debemos verificar que.
No importa si B es primo (de hecho, no lo es).
Finalmente, para cada factor primo p de A , use prueba y error para encontrar un a p que satisfaga ( 6 ) y ( 7 ) .
Para , intentar . Levantamientoa esta alta potencia se puede hacer de manera eficiente usando exponenciación binaria :
- .
Entonces, satisface ( 6 ) pero no ( 7 ) . Como se nos permite una diferente una p para cada p , tratar en lugar de:
- .
Entonces satisface tanto ( 6 ) como ( 7 ) .
Para , el segundo factor primo de A , intente:
- .
- .
satisface tanto ( 6 ) como ( 7 ) .
Esto completa la prueba de que es primordial. El certificado de primalidad para consistiría en los dos pares (2, 5) y (3, 2).
Hemos elegido números pequeños para este ejemplo, pero en la práctica, cuando comenzamos a factorizar A, podemos obtener factores que son en sí mismos tan grandes que su primalidad no es obvia. No podemos probar que N es primo sin probar que los factores de A también lo son. En tal caso, utilizamos la misma prueba de forma recursiva en 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 así hemos probado nuestro resultado. El certificado de primordialidad es la lista depares, que se pueden comprobar rápidamente en el corolario.
Si nuestro ejemplo hubiera incluido grandes factores primos, el certificado sería más complicado. En primer lugar, consistiría en nuestra ronda inicial de a p s que corresponden a los factores "primos" de A ; A continuación, para cada factor de A donde la primordialidad fuera incierta, tendríamos más a p , y así sucesivamente para los factores de estos factores hasta que alcancemos factores de los que la primordialidad sea cierta. Esto puede continuar durante muchas capas si la prima inicial es grande, pero el punto importante es que se puede producir un certificado que contenga en cada nivel la prima que se va a probar y la correspondiente a p s, que se puede verificar fácilmente.
Extensiones y variantes
El artículo de 1975 de Brillhart, Lehmer y Selfridge [5] da una prueba de lo que se muestra arriba como el "teorema de Pocklington generalizado" como el Teorema 4 en la página 623. Se muestran teoremas adicionales que permiten menos factorización. Esto incluye su Teorema 3 (un fortalecimiento de un teorema de Proth de 1878):
- Dejar 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 una cantidad suficiente depara 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 de este tipo que permiten probar la primacía de N basándose en la factorización parcial de y . [6]
Referencias
- Leonard Eugene Dickson, "Historia de la teoría de los números" vol 1, p 370, Chelsea Publishing 1952
- Henry Pocklington, "Math. Quest. Educat. Times", (2), 25, 1914, p 43-46 (Preguntas y soluciones matemáticas en la continuación de las columnas matemáticas de "los tiempos educativos".)
- ^ Pocklington, Henry C. (1914-1916). "La determinación de la naturaleza prima o compuesta de grandes números por el teorema de Fermat". Actas de la Sociedad Filosófica de Cambridge . 18 : 29-30.
- ^ DH Lehmer (1927). "Pruebas de primalidad por el inverso del teorema de Fermat" . Toro. Amer. Matemáticas. Soc . 33 (3): 327–340. doi : 10.1090 / s0002-9904-1927-04368-3 .
- ^ a b c Koblitz, Neal (1994). Curso de Teoría de Números y Criptografía . Textos de Posgrado en Matemáticas. 144 (2ª ed.). Saltador. 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.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ a b Brillhart, John ; Lehmer, DH ; Selfridge, JL (abril de 1975). "Nuevos Criterios de Primaria 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 .
- ^ Las pruebas clásicas
enlaces externos
- Chris Caldwell, "Primality Proving 3.1: n-1 tests and the Pepin's tests for Fermats" en Prime Pages .
- Chris Caldwell, "Primality Proving 3.2: pruebas n + 1 y la prueba de Lucas-Lehmer para Mersennes" en Prime Pages .