Teorema de Proth

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 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

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

  1. Caldwell, Chris. «The Top Twenty: Largest Known Primes». Consultado el 1 de julio de 2009.

Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Número de Proth — En teoría de números, un número de Proth es un número de la forma donde k es impar, n es un entero positivo y 2n > k. Los números de Proth se llaman así en honor al matemático François Proth. Si un número de Proth es primo, se… …   Wikipedia Español

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

  • Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”