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 enteroa:
(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, 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.
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]
teorema, proth, teorema, proth, test, primalidad, para, números, proth, inventado, françois, proth, alrededor, 1878, este, teorema, sostiene, número, proth, decir, forma, impar, entonces, para, algún, número, entero, displaystyle, equiv, entonces, número, prim. El teorema de Proth es un test de primalidad para los numeros de Proth inventado por Francois Proth alrededor de 1878 Este teorema sostiene que si p es un numero de Proth es decir de la forma k2n 1 con k impar y k lt 2n entonces si para algun numero entero a a p 1 2 1 mod p displaystyle a p 1 2 equiv 1 mod p 1 entonces p es un numero primo llamado primo de Proth Este test funciona en la practica porque si p es primo el 50 de los valores de a cumplen con la condicion indicada arriba Si a es un numero primo y p no es un residuo cuadratico modulo a entonces a tampoco es residuo cuadratico modulo p y se cumple la condicion del teorema En la practica se usan diferentes numeros primos pequenos para la variable a y se calcula el simbolo de Jacobi hasta que a p 1 displaystyle left frac a p right 1 dd lo cual es mucho mas rapido que la exponenciacion modular para hallar el valor de a ya que en este caso luego de calcular p mod a se deben realizar unos pocos calculos usando numeros menores que a mientras que con la formula 1 se deben realizar mas de ln p ln 2 multiplicaciones modulares modulo p lo que es muy costoso en tiempo de calculo Ejemplos numericos EditarA continuacion 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 digitos decimales y es el mayor primo conocido que no es de Mersenne 1 Referencias Editar Caldwell Chris en ingles The Prime Pages Universidad de Tennessee http primes utm edu top20 page php id 3 Consultado el 1 de julio de 2009 Datos Q3771212 Obtenido de https es wikipedia org w index php title Teorema de Proth amp oldid 131647908, wikipedia, wiki, leyendo, leer, libro, biblioteca,
