Hispanopedia Wiki
Articulo de referencia

Certificado de primacía

En matemáticas e informática , un certificado de primalidad o prueba de primalidad es una demostración formal y concisa de que un número es primo . Los certificados de primalida...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas e informática , un certificado de primalidad o prueba de primalidad es una demostración formal y concisa de que un número es primo . Los certificados de primalidad permiten comprobar rápidamente la primalidad de un número sin necesidad de realizar una prueba costosa o poco fiable . El término "conciso" suele significar que la prueba debe ser, como máximo , polinómicamente mayor que el número de dígitos del propio número (por ejemplo, si el número tiene b bits, la prueba podría contener aproximadamente b² bits ).

Los certificados de primalidad conducen directamente a pruebas de que problemas como la comprobación de primalidad y el complemento de la factorización de enteros pertenecen a NP , la clase de problemas verificables en tiempo polinomial dada una solución. Estos problemas ya pertenecen trivialmente a co-NP . Esta fue la primera evidencia sólida de que estos problemas no son NP-completos , ya que, de ser así, implicaría que NP es un subconjunto de co-NP, un resultado que se creía falso; de hecho, esta fue la primera demostración de un problema en NP que intersectaba con co-NP y que, en ese momento, no se sabía que perteneciera a P.

Generar certificados para el problema del complemento, que permite determinar si un número es compuesto, es sencillo: basta con proporcionar un divisor no trivial. Las pruebas de primalidad probabilísticas estándar, como la prueba de primalidad de Baillie-PSW , la prueba de primalidad de Fermat y la prueba de primalidad de Miller-Rabin , también generan certificados de composición cuando el número de entrada es compuesto, pero no generan certificados para números primos.

Certificados Pratt

El concepto de certificados de primalidad fue introducido históricamente por el certificado de Pratt , concebido en 1975 por Vaughan Pratt , [ 1 ] quien describió su estructura y demostró que tiene tamaño polinomial y que es verificable en tiempo polinomial. Se basa en la prueba de primalidad de Lucas , que es esencialmente la inversa del pequeño teorema de Fermat con una condición añadida para que sea verdadera:

Teorema de Lucas : Supongamos que tenemos un número entero a tal que:
  • a n − 1 ≡ 1 (mod n ),
  • para cada factor primo q de n − 1, no es cierto que a ( n  − 1)/ q ≡ 1 (mod n ).
Entonces n es primo.

Dado tal a (llamado testigo ) y la factorización prima de n  − 1, es sencillo verificar rápidamente las condiciones anteriores: solo necesitamos hacer un número lineal de exponenciaciones modulares, ya que cada entero tiene menos factores primos que bits, y cada uno de estos se puede hacer mediante exponenciación por cuadrado en O(log n ) multiplicaciones (ver notación big-O ). Incluso con la multiplicación de enteros de la escuela primaria, esto es solo O((log n ) 4 ) tiempo; usando el algoritmo de multiplicación con el mejor tiempo de ejecución asintótico conocido, debido a David Harvey y Joris van der Hoeven , podemos reducir esto a O((log n ) 3 (log log n )) tiempo, o usando la notación soft-O Õ((log n ) 3 ).

Sin embargo, es posible engañar a un verificador para que acepte un número compuesto proporcionándole una "factorización prima" de n  − 1 que incluya números compuestos. Por ejemplo, supongamos que afirmamos que n  = 85 es primo, proporcionando a  = 4 y n  − 1 = 6 × 14 como la "factorización prima". Entonces (usando q  = 6 y q  = 14):

  • 4 es coprimo con 85,
  • 4 85−1 ≡ 1 (mod 85),
  • 4 (85−1)/6 ≡ 16 (mod 85), 4 (85−1)/14 ≡ 16 (mod 85).

Concluiríamos erróneamente que 85 es primo. No queremos simplemente obligar al verificador a factorizar el número, así que una mejor manera de evitar este problema es proporcionar certificados de primalidad para cada uno de los factores primos de n  − 1, que son simplemente instancias más pequeñas del problema original. Continuamos recursivamente de esta manera hasta llegar a un número que se sabe que es primo, como el 2. Terminamos con un árbol de números primos, cada uno asociado con un testigo a . Por ejemplo, aquí hay un certificado Pratt completo para el número 229:

  • 229 ( a  = 6, 229 − 1 = 2 2  × 3 × 19),
    • 2 (primo conocido),
    • 3 ( a  = 2, 3 − 1 = 2),
      • 2 (primo conocido),
    • 19 ( a  = 2, 19 − 1 = 2 × 3 2 ),
      • 2 (primo conocido),
      • 3 ( a  = 2, 3 − 1 = 2),
        • 2 (primo conocido).

Se puede demostrar que este árbol de pruebas contiene como máximo4registro2⁡norte−4{\displaystyle 4\log _{2}n-4}valores distintos de 2 mediante una sencilla demostración inductiva (basada en el teorema  2 de Pratt). El resultado se cumple para 3; en general, tomemos p > 3 y sean sus hijos en el árbol p 1 , ..., p k . Por la hipótesis inductiva, el árbol con raíz en p i contiene como máximo4registro2⁡pagi−4{\ Displaystyle 4 \ log _ {2} p_ {i} -4}valores, por lo que todo el árbol contiene como máximo

1+∑i=1k(4registro2⁡pagi−4)=−4k+4registro2⁡pag1⋯pagk≤4registro2⁡pag−4,{\displaystyle 1+\sum _{i=1}^{k}(4\log _{2}p_{i}-4)=-4k+4\log _{2}p_{1}\cdots p_{k}\leq 4\log _{2}p-4,}

puesto que k ≥ 2, y p 1 ... p k ≤ p  − 1. Dado que cada valor tiene como máximo log n bits, esto también demuestra que el certificado tiene un tamaño de O((log n ) 2 ) bits.

Dado que hay O(log n ) valores distintos de 2, y cada uno requiere como máximo una exponenciación para su verificación (y las exponenciaciones dominan el tiempo de ejecución), el tiempo total es O((log n ) 3 (log log n )(log log log n )), o Õ((log n ) 3 ), lo cual es bastante factible para números en el rango con el que suelen trabajar los teóricos computacionales de números.

Sin embargo, aunque resulta útil en teoría y fácil de verificar, generar un certificado Pratt para n requiere factorizar n  − 1 y otros números potencialmente grandes. Esto es sencillo para algunos números especiales, como los primos de Fermat , pero actualmente es mucho más difícil que una simple prueba de primalidad para primos grandes de forma general.

Certificados Atkin – Goldwasser – Kilian – Morain

Para abordar el problema de la generación eficiente de certificados para números grandes, en 1986 Shafi Goldwasser y Joe Kilian describieron un nuevo tipo de certificado basado en la teoría de las curvas elípticas . [ 2 ] Este fue a su vez utilizado por AOL Atkin y François Morain como base para los certificados Atkin-Goldwasser-Kilian-Morain, que son el tipo de certificados generados y verificados por los sistemas de prueba de primalidad de curvas elípticas (ECPP). [ 3 ] Así como los certificados Pratt se basan en el teorema de Lucas , los certificados Atkin-Goldwasser-Kilian-Morain se basan en el siguiente teorema de Goldwasser y Kilian (lema 2 de "Casi todos los primos se pueden certificar rápidamente"):

Teorema : Supongamos que se nos da:
  • un número entero positivo n que no sea divisible por 2 ni por 3;
  • M x , M y , A, B enZnorte{\displaystyle \mathbb {Z} _ {n}}(los enteros módulo n ) que satisfacen M y 2 = M x 3 + AM x + B y con 4A 3 + 27B 2 coprimo con n ;
  • un primoq>norte1/2+1+2norte1/4{\displaystyle q>n^{1/2}+1+2n^{1/4}}.
Entonces M = (M x , M y ) es un punto distinto de la identidad en la curva elíptica y 2 = x 3 + Ax + B. Sea k M M sumado a sí mismo k veces usando la suma estándar de curvas elípticas. Entonces, si q M es el elemento identidad I, entonces n es primo.

Técnicamente, una curva elíptica solo puede construirse sobre un campo, yZnorte{\displaystyle \mathbb {Z} _ {n}}es solo un campo si n es primo, por lo que parece que estamos asumiendo el resultado que estamos tratando de demostrar. La dificultad surge en el algoritmo de suma de curvas elípticas, que toma inversas en el campo que pueden no existir enZnorte{\displaystyle \mathbb {Z} _ {n}}Sin embargo, se puede demostrar (lema 1 de "Casi todos los números primos se pueden certificar rápidamente") que si simplemente realizamos cálculos como si la curva estuviera bien definida y en ningún momento intentamos invertir un elemento sin inverso, el resultado sigue siendo válido; si encontramos un elemento sin inverso, esto establece que n es compuesto.

Para derivar un certificado a partir de este teorema, primero codificamos M x , M y , A, B y q , luego codificamos recursivamente la prueba de primalidad para q < n , continuando hasta llegar a un primo conocido. Este certificado tiene un tamaño de Õ((log n ) 2 ) y se puede verificar en un tiempo de Õ((log n ) 4 ). Además, se puede demostrar que el algoritmo que genera estos certificados tiene una complejidad temporal polinómica para todos los primos, excepto una pequeña fracción, y esta fracción disminuye exponencialmente con el tamaño de los primos. Por consiguiente, es muy adecuado para generar primos aleatorios grandes certificados, una aplicación importante en criptografía , como la generación de claves RSA con validez demostrable .

El tiempo empleado en generar un certificado ECPP no está limitado, pero un argumento heurístico da Õ((log n ) 6 ) implementado ingenuamente como en Goldwasser-Kilian. Atkin y Morain redujeron el número a Õ((log n ) 5 ). FastECPP (Shallit, Franke, Morain, Enge) ha reducido el tiempo a Õ((log n ) 4 ). [ 4 ]

Certificados con sede en Pocklington

La generación de primos demostrables basada en variantes del teorema de Pocklington (véase la prueba de primalidad de Pocklington ) [ 5 ] puede ser una técnica eficiente para generar primos (el coste suele ser menor que el de la generación probabilística), con la ventaja añadida de contar con certificados de primalidad incorporados. Si bien estos primos pueden parecer especiales, cabe destacar que cualquier entero primo podría generarse con un algoritmo de generación demostrable basado en el teorema de Pocklington.

Pruebas de primacía de Pocklington

DejarPAG=Rh+1{\displaystyle P=Rh+1}dóndeR=∏qjmij{\displaystyle R=\prod q_{j}^{e_{j}}}dóndeqj{\displaystyle q_{j}}son primos distintos conmij{\displaystyle e_{j}}un número entero mayor que cero y un testigogramo{\displaystyle g}de tal manera que:

Entonces P es primo si se cumple alguna de las siguientes condiciones:

Certificado de primacía de Pocklington

Un certificado de primalidad de Pocklington consta del primo P, un conjunto de primosqj{\displaystyle q_{j}}divisor(PAG−1){\displaystyle (P-1)}, cada uno con su propio certificado de primo de Pocklington o lo suficientemente pequeño como para ser un primo conocido, y un testigogramo{\displaystyle g}.

Los pasos necesarios para obtener este certificado (y el orden de coste computacional) deben ser la suma de estos pasos:

  1. Verifique que todosqj{\displaystyle q_{j}}son primos y que se dividenPAG−1{\displaystyle P-1}, obteniendoR{\displaystyle R}yh{\displaystyle h}en el proceso. Esto tomaría menos tiempo que el resto del proceso.
  2. Verifica que ( 1 ) se cumple. Esta es la misma complejidad que la prueba de primalidad de Fermat, Õ((log P ) 2 ).
  3. Verificar que ( 2 ) se cumple. Esto requiere el cálculo del mcd, que para números grandes generalmente se realiza utilizando el algoritmo euclidiano extendido , sobre la cantidad de primos proporcionados. Cada operación toma entre Õ((log P ) 2 ) y Õ((log P ) 3 ) tiempo dependiendo de la magnitud relativa deqj{\displaystyle q_{j}}versusPAG{\displaystyle P}.
  4. Verifica que el último paso se mantenga. Esto es aproximadamente:
    • registro2⁡PAG(1+∑k=1∞13k)=1.5registro2⁡PAG{\displaystyle \log _{2}{P}\left(1+\sum _{k=1}^{\infty }{\frac {1}{3^{k}}}\right)=1.5\log _{2}{P}}para la versión ( 3b ) a
    • registro2⁡PAG(1+∑k=1∞12k)=2registro2⁡PAG{\displaystyle \log _{2}{P}\left(1+\sum _{k=1}^{\infty }{\frac {1}{2^{k}}}\right)=2\log _{2}{P}}para la versión ( 3a ).

Véase también la documentación de PARI/GP . [ 8 ]

Un pequeño ejemplo

DejarPAG=1056893{\displaystyle P=1056893}. Tenga en cuenta que(PAG−1)=1621⋅163⋅22{\displaystyle (P-1)=1621\cdot 163\cdot 2^{2}}yPAG1/2=1028.053…{\displaystyle P^{1/2}=1028.053\ldots },PAG1/3=101.86156…{\displaystyle P^{1/3}=101.86156\ldots }.

  • Usando el 'testigo' 2, la ecuación 1 se satisface y 2 usandoq=163{\displaystyle q=163}yq=1621{\displaystyle q=1621}.
  • Para la versión 3a , el certificado solo necesitaPAG=1056893, q=1621, gramo=2{\displaystyle P=1056893,\ q=1621,\ g=2}.
  • Para la versión 3b , el certificado solo necesitaPAG=1056893, q=163, gramo=2{\displaystyle P=1056893,\ q=163,\ g=2}, pero aún queda algo de trabajo por hacer:
    • h=(1056893−1)/163=6484{\displaystyle h=(1056893-1)/163=6484}
    • a≡h≡127mod163{\displaystyle a\equiv h\equiv 127{\bmod {163}}}yb=(6484−127)/163=39{\displaystyle b=\left(6484-127\right)/163=39}
    • Usandor=3{\displaystyle r=3}fallas:(1272−4⋅39)(3−1)/2≡(12−0)1≡1mod3{\displaystyle \left(127^{2}-4\cdot 39\right)^{(3-1)/2}\equiv (1^{2}-0)^{1}\equiv 1{\bmod {3}}}
    • Usandor=5{\displaystyle r=5}tiene éxito:(1272−4⋅39)(5−1)/2≡(22−1)2≡2mod5{\displaystyle \left(127^{2}-4\cdot 39\right)^{(5-1)/2}\equiv (2^{2}-1)^{2}\equiv 2{\bmod {5}}}, yPAG{\displaystyle P}es primordial.

Certificado basado en Gerbicz

Los certificados basados ​​en Gerbicz buscan demostrar la corrección de un proceso de exponenciación modular , como el utilizado en las pruebas probabilísticas de Proth y Fermat, así como en los primeros pasos de la prueba de Pocklington. También se han adaptado al cálculo de los términos de la secuencia de Lucas, que se utiliza en las pruebas deterministas de Lucas-Lehmer y Lucas-Lehmer-Riesel. Este tipo de certificado tomaO(registro2⁡norte){\displaystyle O(\log ^{2}n)}espacio y tiempo para producir.

El certificado producido tomaO(registro⁡norte){\displaystyle O(\log n)}espacio para transmitir yO(1){\displaystyle O(1)}cuadrados (siendo ellos mismosO(registro⁡norte){\displaystyle O(\log n)}-tiempo) para verificar. (Esta afirmación asume un valor constante de B , que es un parámetro de ajuste importante en la práctica: con un valor menor de B , se utiliza más espacio en disco para generar el certificado y se puede dedicar menos tiempo a la verificación. En la práctica, se utilizan varios gigabytes de espacio).

Se aplica a números muy grandes donde la exponenciación en sí misma es una tarea costosa. Por ejemplo, se utilizó una prueba de Gerbicz-Pietrzak para autenticar la prueba de primalidad de Fermat para2136279841−1{\displaystyle 2^{136279841}-1}, el primo de Mersenne encontrado en 2024. [ 9 ]

Plan Gerbicz-Pietrzak

Great Internet Mersenne Prime Search y proyectos afines como (parte de) PrimeGrid utilizan el esquema "Gerbicz-Pietrzak" de Pavel Atnashev, que combina la verificación de errores de Gerbicz para la exponenciación modular con la función de retardo verificable de Pietrzak para producir una "prueba" fácilmente verificable de una exponenciación modular a una potencia de 2 m . [ 10 ] [ 11 ]

El esquema de verificación de errores de Gerbicz se definió originalmente para la prueba de Proth , pero posteriormente se extendió a la prueba de primalidad de Fermat . La forma original verifica el cálculo.tú(t)=ak2t(modnorte){\displaystyle u(t)={a^{k}}^{2^{t}}{\pmod {N}}}agregando una variable adicionald(t)=∏i=0ttú(iL)(modnorte){\displaystyle d(t)=\textstyle \prod _{i=0}^{t}u(iL){\pmod {N}}}y una constante de escala arbitraria L. Por lo tanto, existe una relación de recurrencia ded(t+1)=d(t)⋅tú((t+1)⋅L)(modnorte){\displaystyle d(t+1)=d(t)\cdot u((t+1)\cdot L){\pmod {N}}}que se puede utilizar para actualizar d(t) cada L iteraciones de duplicación exponencial. También hay una relaciónd(t+1)=tú(0)⋅d(t)2L(modnorte){\displaystyle d(t+1)=u(0)\cdot d(t)^{2^{L}}{\pmod {N}}}, que se utiliza para comprobar el cálculo cada B = L 2 iteraciones. Una discrepancia daría como resultado una reversión a una tupla de "punto de control" guardada previamente.(t,tú,d){\displaystyle (t,u,d)}. [ 12 ]

Con la adición del esquema VDF de Pietrzak, [ 13 ] el cliente de cálculo genera un archivo de "certificado" utilizando los residuos de "punto de control" guardados del cálculo, lo que da como resultado un archivo de O(registro⁡(metro/L)){\displaystyle O(\log(m/L))}elementos. Carga el certificado a un servidor, que luego lo asigna a un cliente "verificador". El verificador utiliza la versión no interactiva del esquema Pietrzak para comprobar el resultado. [ 14 ]

Se ha publicado una generalización del esquema de Pietrzak a secuencias de Lucas , en la que el cálculo deU2metro(PAG,Q)modnorte{\displaystyle U_{2^{m}}(P,Q){\bmod {n}}},V2metro(PAG,Q)modnorte{\displaystyle V_{2^{m}}(P,Q){\bmod {n}}}Se verifica. [ 15 ]

Esquema de Gerbicz-Li

La principal limitación del método de Gerbicz-Pietrzak es que solo se aplica a la exponenciación modular a una potencia de 2 m . El esquema de Gerbicz-Li se desarrolló para PrimeGrid para superar esta limitación, verificando la exponenciación modular de izquierda a derecha a cualquier potencia n . Sea L la longitud de la expansión binaria de n , de modo quenorte=norte020+norte121+⋯+norteL−12L−1{\displaystyle n=n_{0}2^{0}+n_{1}2^{1}+\dots +n_{L-1}2^{L-1}}. El proceso a verificar es calculartúi=a⌊norte/2i⌋{\displaystyle u_{i}=a^{\lfloor n/2^{i}\rfloor }}mediante la siguiente relación de recurrencia:

túi={1L≤itúi+12⋅anorteide lo contrario{\displaystyle {\begin{aligned}u_{i}={\begin{cases}1&L\leq i\\u_{i+1}^{2}\cdot a^{n_{i}}&{\text{otherwise}}\end{cases}}\end{aligned}}}

Por lo tanto, existe una relacióntúi=túi+j2ja⌊norte2i⌋mod2j{\displaystyle u_{i}=u_{i+j}^{2^{j}}a^{\left\lfloor {\frac {n}{2^{i}}}\right\rfloor {\bmod {2}}^{j}}}. Al igual que con el esquema Gerbicz, el cliente que realiza el cálculo ahorratú0,túB,tú2B,…{\displaystyle u_{0},u_{B},u_{2B},\dots }por alguna constanteB{\displaystyle B}que es un múltiplo deL{\displaystyle L}Luego comprueba las equivalencias entretúiB{\displaystyle u_{iB}}ytú(i+1)B{\displaystyle u_{(i+1)B}}cadaB{\displaystyle B}bloques, añadiendo un término de peso aleatoriowi{\displaystyle w_{i}}para la solidez de la prueba de seguridad:

∏i=0túiBwi=¿∏i=0tú(i+1)Bwi2Ba(⌊norte2iB⌋mod2B)wi=(∏i=0tú(i+1)Bwi)2Ba∑i=0(⌊norte2iB⌋mod2B)wi{\displaystyle {\begin{aligned}\prod _{i=0}u_{iB}^{w_{i}}&{\overset {\text{?}}{=}}\prod _{i=0}u_{(i+1)B}^{w_{i}2^{B}}a^{\left(\left\lfloor {\frac {n}{2^{iB}}}\right\rfloor {\bmod {2}}^{B}\right)w_{i}}\\&=\left(\prod _{i=0}u_{(i+1)B}^{w_{i}}\right)^{2^{B}}a^{\sum \limits _{i=0}\left(\left\lfloor {\frac {n}{2^{iB}}}\right\rfloor {\bmod {2}}^{B}\right)w_{i}}\end{aligned}}}

El hashing se utiliza de manera similar para producir una prueba no interactiva para uso de los operadores de PrimeGrid. [ 14 ]

Pavel Atnashev ha generalizado aún más Gerbicz-Li al cálculo de términos de secuencias de Lucas arbitrarias conQ=−1{\displaystyle Q=-1}. [ 16 ] Esta generalización se utiliza en su "prueba de Morrison", una generalización de la prueba LLR con valor inicial de Rödseth, en el software "PRST" de PrimeGrid . [ 17 ]

Certificado AKS ("PRIMES está en P")

«PRIMES is in P» [ 18 ] supuso un gran avance en la informática teórica. Este artículo, publicado por Manindra Agrawal , Nitin Saxena y Neeraj Kayal en agosto de 2002, demuestra que el famoso problema de comprobar la primalidad de un número puede resolverse de forma determinista en tiempo polinomial. Los autores recibieron el Premio Gödel y el Premio Fulkerson en 2006 por este trabajo.

Dado que ahora es posible realizar pruebas de primalidad de forma determinista en tiempo polinomial mediante la prueba de primalidad AKS , un número primo podría considerarse un certificado de su propia primalidad. Esta prueba se ejecuta en tiempo Õ((log n ) 6 ). En la práctica, este método de verificación es más costoso que la verificación de certificados Pratt, pero no requiere ningún cálculo para determinar el certificado en sí.

Límite para "números primos conocidos"

A partir de ensayos exhaustivos, se sabe que la prueba de primalidad de Baillie-PSW no tiene pseudoprimos por debajo de 2 64 . Como resultado, 2 64 es un límite a partir del cual se esperan certificados primos de los números dados. [ 19 ]

Formatos de archivo

Las bases de datos de números primos aceptan el envío de certificados en formatos comunes utilizados por los programas de prueba de primalidad. Existen los siguientes formatos:

  • Formato Primo para ECPP. Originalmente utilizado por un programa de Linux con interfaz gráfica llamado Primo. [ 20 ]
  • Formato PARI para ECPP y N-1 (Pocklington), utilizado en PARI/GP . [ 8 ]

El programa Cm, un programa ECPP rápido, admite la generación de formatos Primo y PARI. Utiliza la paralelización MPI para escalar en múltiples computadoras [ 21 ] e implementa el algoritmo FastECPP [ 4 ] .

GIMPS (PrimeNet) y PrimeGrid utilizan formatos propios para los certificados de exponenciación basados ​​en Gerbicz, que no son ampliamente aceptados por otros programas o proyectos.

Referencias

  1. ↑ Vaughan Pratt. "Cada número primo tiene un certificado sucinto". SIAM Journal on Computing , vol. 4, pp. 214–220. 1975. Citas , Texto completo .
  2. ↑ Goldwasser, S. y Kilian, J. "Casi todos los números primos se pueden certificar rápidamente". Actas del 18.º STOC. págs. 316–329, 1986. Texto completo .
  3. ↑ Atkin, A OL ; Morain, F. (1993). "Curvas elípticas y demostración de primalidad" (PDF) . Matemáticas de la Computación . 61 (203): 29– 68. Bibcode : 1993MaCom..61...29A . doi : 10.1090/s0025-5718-1993-1199989-x . JSTOR 2152935 . MR 1199989 .  
  4. 1 2 Enge, Andreas (2024). "FastECPP sobre MPI" . Software matemático – ICMS 2024. Lecture Notes in Computer Science. Vol. 14749. pp. 36–45 . arXiv : 2404.05506 . doi : 10.1007/978-3-031-64529-7_4 . ISBN   978-3-031-64528-0.
  5. ↑ 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 .
  6. ↑ Crandall, Richard; Pomerance, Carl. "Números primos: una perspectiva computacional" (2.ª ed.). Springer-Verlag, 175 Fifth Ave, Nueva York, Nueva York 10010, EE. UU., 2005. 
  7. ↑ 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 . 
  8. 1 2 "Catálogo de funciones GP/PARI: funciones aritméticas" . pari.math.u-bordeaux.fr .
  9. ↑ "136 279 841 Estado del exponente" . www.mersenne.org . Certificación PRP CERT poder de prueba = 9 Prueba certificada buena
  10. ↑ Woltman, George (16 de junio de 2020). "El próximo gran desarrollo para GIMPS" . Foro de GIMPS . Recuperado el 20 de mayo de 2022 .
  11. ↑ "GIMPS - The Math - PrimeNet" . www.mersenne.org .
  12. ↑ Gerbicz, Robert (2017). "Comprobación de errores rápida y robusta en pruebas Proth/Pepin" .
  13. ↑ Boneh, Dan; Bünz, Benedikt; Fisch, Ben (2018). Un estudio de dos funciones de retardo verificables (Informe) . Recuperado el 6 de octubre de 2025 .
  14. 1 2 Darren Li; Yves Gallot (8 de febrero de 2023). "Un esquema eficiente de prueba de exponenciación modular". arXiv : 2209.15623 [ cs.CR ].
  15. ^ Hoffmann, Charlotte; Hubáček, Pavel; Kamath, Chethan; Krňák, Tomáš (2023). Funciones de retardo (verificables) de secuencias de Lucas . TCC 2023 [IACR 2023/1404] . Consultado el 11 de octubre de 2025 .
  16. ^ "prst/src/lucasmul.cpp en principal · patnashev/prst" . GitHub .
  17. ↑ Atnashev, Pavel (2023). "Una alternativa más simple a la prueba de primalidad de Lucas-Lehmer-Riesel" . Cryptology ePrint Archive .
  18. ^ Agrawal, Manindra ; Kayal, Neeraj ; Saxena, Nitin (septiembre de 2004). "PRIMES está en P" (PDF) . Anales de Matemáticas . 160 (2): 781– 793. doi : 10.4007/annals.2004.160.781 . JSTOR 3597229 . SEÑOR 2123939 .  
  19. ↑ Nicely, Thomas R. (13 de enero de 2012) [Publicado originalmente el 10 de junio de 2005]. "La prueba de primacía de Baillie-PSW" . trnicely.net . Archivado del original el 21 de noviembre de 2019. Consultado el 17 de marzo de 2013 .
  20. ↑ "Primo para Linux" . www.ellipsa.eu .
  21. ↑ "Introducción" .
  • Mathworld: Certificado de Primalidad
  • Mathworld: Certificado Pratt
  • Mathworld: Certificado Atkin-Goldwasser-Kilian-Morain
  • El glosario principal: Certificado de primacía
  • Vašek Chvátal . Apuntes de clase sobre las pruebas de primalidad de Pratt . Departamento de Informática. Universidad de Rutgers. Versión en PDF en la Universidad de Concordia .