Obre el menú principal

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