Teorema de Proth

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 k2n + 1 con k impar y k < 2n, entonces si para algún número entero a:

a^{(p-1)/2}\equiv -1 \mod{p}\,\! (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:

\left(\frac{a}{p}\right)=-1

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[editar]

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

  • para p = 3, 21 + 1 = 3 es divisible por 3, por lo que 3 es primo.
  • para p = 5, 32 + 1 = 10 es divisible por 5, por lo que 5 es primo.
  • para p = 13, 56 + 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 a4 + 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 · 213018586 + 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[editar]