En teoría de números , el teorema de Proth es una prueba de primalidad para los números de Proth .
Se afirma [1] [2] que si p es un número de Proth , de la forma k 2 n + 1 con k impar y k < 2 n , y si existe un entero a para el cual
entonces p es primo . En este caso p se llama primo de Proth . Esta es una prueba práctica porque si p es primo, cualquier a elegido tiene alrededor de un 50 por ciento de posibilidades de funcionar, además, dado que el cálculo es mod p , solo se deben tomar en consideración valores de a menores que p .
En la práctica, sin embargo, un residuo cuadrático no determinado de p se encuentra mediante un algoritmo de Euclides modificado [ cita requerida ] y se toma como el valor de a , ya que si a es un residuo cuadrático no determinado módulo p entonces la inversa también es cierta y la prueba es concluyente. Para tal a el símbolo de Legendre es
Por lo tanto, a diferencia de muchas pruebas de primalidad de Monte Carlo (algoritmos aleatorios que pueden devolver un falso positivo ), el algoritmo de prueba de primalidad basado en el teorema de Proth es un algoritmo de Las Vegas , que siempre devuelve la respuesta correcta pero con un tiempo de ejecución que varía aleatoriamente. Tenga en cuenta que si se elige a como un residuo cuadrático no válido como se describió anteriormente, el tiempo de ejecución es constante, salvo el tiempo empleado en encontrar dicho residuo cuadrático no válido. Encontrar dicho valor es muy rápido en comparación con la prueba real.
Algunos ejemplos del teorema incluyen:
Los primeros primos de Proth son (secuencia A080076 en la OEIS ):
El primo de Proth más grande conocido hasta 2016 [actualizar]es , y tiene 9.383.761 dígitos de longitud. [3] Fue encontrado por Peter Szabolcs en el proyecto de computación voluntaria PrimeGrid que lo anunció el 6 de noviembre de 2016. [4] Es el undécimo número primo más grande conocido hasta enero de 2024, fue el primo no Mersenne más grande conocido hasta ser superado en 2023, [5] y es el número de Colbert más grande . [ cita requerida ] El segundo primo de Proth más grande conocido es , encontrado por PrimeGrid . [6]
La prueba de este teorema utiliza el test de primalidad de Pocklington-Lehmer y se parece mucho a la prueba del test de Pépin . La prueba se puede encontrar en la página 52 del libro de Ribenboim en las referencias.
François Proth (1852-1879) publicó el teorema en 1878. [7] [8]