Test de primalidad de Fermat

El test de primalidad de Fermat és un algoritme provabilístic que fa us del menuda teorema de Fermat. Esta teorema enuncia que si p és primer i a és coprimo en p, llavors a^p-1 - 1 és divisible per p. Açò també es pot expressar aixina:

a^p-1 ≡ 1 (mod p).

Resulta que el recíproc d'esta teorema sol ser veritat: si p és compost, llavors a^p-1 és poc provable que siga congruent en 1 mòdul p per a un valor arbitrari de a. No obstant, prenent número compuesto n i elegint un a coprimo en estos, alguns d'ells poden fer fallar este test. Estos números es denominen pseudoprimos.

Algoritme

l'algoritme per a implementar el test és el següent:

Utilisant algoritmes ràpits d'exponenciación modular, es pot comprovar que el temps d'eixecució d'este algoritme és O(k × log²n × log log n × log log log n), a on k representa el número de voltes que es comprova la congruència per al número aleatori a i n és el número a testear.

Eixemple

Supongam que es vol determinar si n = 221 és primer. Triant aleatoriamente 1 < a < 221, digam a = 38, es pot chequear l'expressió per a determinar si es complix:

$a^{n-1}=38^{220}\equiv 1(\mathrm{mod}221).$

després 221 pot ser primer, o també pot ser que 38 siga un número que falsege el test, de manera que prenem un atre a, esta volta 24:

$a^{n-1}=24^{220}\equiv 81\equiv ̸1(\mathrm{mod}221).$

Després 221 és compost i 38 era en efecte un número que falsaba el test. Ademés, 24 és un testic de Fermat de la no primalidad de 221.

Vore també

• Test de primalidad

Referències

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). «Section 31.8: Primality testing», Introduction to Algorithms, Second edició, MIT Press; McGraw-Hill, p. 889–890. ISBN 0-262-03293-7.