Teorema de Proth

El teorema de Proth es un test de primalidad para los números de Proth inventado por François Proth alrededor de 1878.

Este teorema sostiene que si p es un número de Proth, es decir de la forma k2ⁿ + 1 con k impar y k < 2ⁿ, entonces si para algún número entero a:

entonces p es un número primo llamado primo de Proth. Este test funciona en la práctica porque si p es primo, el 50% de los valores de a cumplen con la condición indicada arriba.

Si a es un número primo y p no es un residuo cuadrático módulo a entonces a tampoco es residuo cuadrático módulo p y se cumple la condición del teorema. En la práctica se usan diferentes números primos pequeños para la variable a y se calcula el símbolo de Jacobi hasta que:

lo cual es mucho más rápido que la exponenciación modular para hallar el valor de a, ya que en este caso, luego de calcular p mod a, se deben realizar unos pocos cálculos usando números menores que a, mientras que con la fórmula (1) se deben realizar más de (ln p/ln 2) multiplicaciones modulares modulo p, lo que es muy costoso en tiempo de cálculo.

A continuación se muestran ejemplos de uso del teorema de Proth:

Los primeros primos de Proth son:

Esta es la secuencia A080076 de OEIS.

A julio de 2009, el mayor primo de Proth conocido es 19249 · 2^13018586 + 1, hallado por el proyecto Seventeen or Bust. Posee 3918990 dígitos decimales y es el mayor primo conocido que no es de Mersenne.^[1]​