Numeri primi e Piccolo Teorema di Fermat
Controllo della primalità
Un numero si dice primo quando è divisibile solo per se stesso e per 1; se possiede altri divisori, si dice che è composto.
Escluso dunque il numero 2, tutti i numeri primi sono dispari.
Il controllo della primalità di un numero è la classificazione di quest’ultimo come primo o come composto.
Un “veloce” algoritmo di controllo della quasi certa primalità di numeri con un elevato numero di cifre, si basa sul cosiddetto Piccolo Teorema di Fermat.
Piccolo Teorema di Fermat
Stabilisce che: se p è un numero primo, allora per ogni numero naturale b (detto base) che appartiene all’intervallo [1,p-1] si può affermare che:
bp(mod p)=b
Facciamo qualche esempio.
Esempi
I numeri 2, 3 e 5 sono primi, infatti:
2 → 12=1(mod 2)=1
3 → 13=1(mod 3)=1
23=8(mod 3)=2
5 → 15=1(mod 5)=1
25=32(mod 5)=2
35=243(mod 5)=3
45=1024(mod 5)=4
continua…
Di conseguenza, se esiste un numero naturale b appartenente all’intervallo [1,p-1], per il quale si verifica che:
bp(mod p)≠b
allora p è un numero composto.
Anche qui facciamo un esempio.
Consideriamo il numero p=4 :
14=1(mod 4)=1
24=16(mod 4)=0
34=81(mod 4)=1
per cui il numero 4 è, come ci attendeva, composto.
Condizioni del Piccolo Teorema di Fermat
A questo punto sarebbe opportuno porre la seguente domanda:
se per ogni b, appartenente all’intervallo [1,p-1], vale:
bp(mod p)=b
si può affermare dunque che p è un numero primo?
Purtroppo no, cioè la condizione espressa dal Piccolo Teorema di Fermat è necessaria, ma non sufficiente. A tal proposito esistono di fatto i numeri di Carmichael (numeri pseudoprimi).
Analisi probabilistica per il Piccolo Teorema di Fermat
Se effettuiamo il test della primalità su un numero p molto grande, scegliendo a caso 100 basi differenti, la probabilità che un numero pseudoprimo non venga riconosciuto come numero composto, nemmeno al 100-esimo test, è all’incirca minore o uguale a:
PC(ric. primo) ≤ (1/2)100=(1/210)10=(1/1024)10 ≈(1/103)10= 1/1030
Questo significa che: facendo uso del test di Fermat, se dopo 100 tentativi un numero non viene riconosciuto come composto, allora è quasi certamente un numero primo (la probabilità precedente si può considerare nulla).
