Teorema de Proth

El teorema de Proth és un test de primalitat per als nombres de Proth inventat per François Proth al voltant de 1878.

Aquest teorema sosté que si p és un nombre de Proth, és a dir de la forma k 2 n +1 amb k senar i k <2 n , llavors si per a algun nombre enter a :

(1)

llavors p és un nombre primer anomenat cosí de Proth . Aquest test funciona a la pràctica perquè si p és primer, el 50% dels valors de a compleixen amb la condició indicada dalt.

Si a és un nombre primer i p no és un residu quadràtic mòdul a llavors a tampoc és residu quadràtic mòdul p i es compleix la condició del teorema. A la pràctica s'utilitzen diferents nombres primers petits per a la variable a i es calcula el símbol de Jacobi fins que:

la qual cosa és molt més ràpid que la exponenciació modular per trobar el valor de a , ja que en aquest cas, després de calcular p mod a , s'han de realitzar uns pocs càlculs usant nombres menors que a , mentre que amb la fórmula (1) s'han de realitzar més de (ln p /ln 2) multiplicacions modulars mòdul p , el que és molt costós en temps de càlcul.

Exemples numèricsModifica

A continuació es mostren exemples d'ús del teorema de Proth:

  • Per p = 3, 2 1 +1 = 3 és divisible per 3, per la qual cosa 3 és primer.
  • Per p = 5, 3 2 +1 = 10 és divisible per 5, de manera que 5 és primer.
  • Per p = 13, 5 6 +1 = 15.626 és divisible per 13, per la qual cosa 13 és primer.
  • Per p = 9, que no és primer, no hi ha valor de a tal que a 4 +1 sigui divisible per 9.

Els primers cosins de Proth són:

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

Aquesta és la seqüència A080076 de OEIS.

A juliol de 2009, el major cosí de Proth conegut és 19.249 · 2 13.018.586 +1, trobat pel projecte Seventeen or Bust. Posseeix 3918990 dígits decimals i és el major primer conegut que no és de Mersenne.[1]

Vegeu tambéModifica

ReferènciesModifica

  1. Caldwell, Chris. The Top Twenty: Largest Known Primes [Consulta: 1r juliol 2009].