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:

(1)

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.

Ejemplos numéricos

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

• para p = 3, 2¹ + 1 = 3 es divisible por 3, por lo que 3 es primo.
• para p = 5, 3² + 1 = 10 es divisible por 5, por lo que 5 es primo.
• para p = 13, 5⁶ + 1 = 15626 es divisible por 13, por lo que 13 es primo.
• para p = 9, que no es primo, no existe valor de a tal que a⁴ + 1 sea divisible por 9.

Los primeros primos de Proth son:

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, ….

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]

Referencias