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 ⁿ +1 amb k senar i k <2 ⁿ , llavors si per a algun nombre enter a :

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

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

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

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

• Per p = 3, 2 ¹ +1 = 3 és divisible per 3, per la qual cosa 3 és primer.
• Per p = 5, 3 ² +1 = 10 és divisible per 5, de manera que 5 és primer.
• Per p = 13, 5 ⁶ +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 ⁴ +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.

Vegeu també

• Test de Lucas