Quanti sono i numeri primi?

PROGETTO LAUREE SCIENTIFICHE
ITGS PASCAL-UNIV. PARMA
(è stato usato vario materiale di Alessandro Zaccagnini, Alessandro Languasco e da
http://www.dti.unimi.it/citrini/MD/SitoG-M/mil-rab.htm)
Docenti: BAROZZI -SIMEONE
CORSO DI CRITTOGRAFIA
Quarto incontro
Test di Miller-Rabin
Questo è un test di primalità
probabilistico, ovvero da risulatato certo
solo quando risponde che il numero
non è primo.
Se risponde che il numero è primo, la
sua primalità non è certa.
Test di Miller-Rabin
Il test si basa sulla seguente proprietà:
Per il Teorema di Fermat :
Se n è primo an-1=1 (mod n)
questo vuole dire che esiste sicuramente qualche
radice quadrata di an-1 che è congrua a +1 o a -1
modulo n
Test di Miller-Rabin
Se si verifica che per un numero a<n, an-1 e nessuna
delle sue radici quadrate è congrua a 1 o a -1 modulo n,
allora n non può essere primo.
Ovviamente questo test da risultati tanto migliori quanti
più numeri a<n prendo in considerazione. Può infatti
accadere che per un qualche a si verifichi che una delle
radici quadrate sia 1 o -1 anche se n non è primo, in
questo caso a si dice un FALSO FORTE per n.
Test di Miller-Rabin
Esempio: n=221
Consideriamo n-1=220
Lo fattorizziamo come una potenza di 2 per un
numero dispari:
220=22*55
Abbiamo due numeri s=2 (potenza di 2) e d=55
Test di Miller-Rabin
Ora scelgo in modo casuale un numero a<n, ad
esempio 174 e calcolo:
ad mod n = 17455 mod 221 = 47  1
ad mod n = 17455 mod 221 = 47  n-1
a2*d mod n = 174110 mod 221 = 220 = n-1
Dal momento che 220 = -1 mod 221, o 221 è un
numero primo o 174 è un falso forte per 221
Test di Miller-Rabin
Proviamo un altro a casuale, questa volta scegliamo
a = 137
ad mod n = 13755 mod 221 = 188  1
ad mod n = 13755 mod 221 = 188  n-1
a2*d mod n = 137110 mod 221 = 205  n-1
In questo caso 137 è testimone della compostezza
di 221, notiamo che questo metodo non ci dice nulla
sulla fattorizzazione di 221=13*17