7 dicembre 2011

Teoria dei numeri e Crittografia: lezione del 7 dicembre 2011 Numeri di Mersenne. Dopo avere studiato i numeri di Fermat (successivi di una potenza di 2), studieremo i numeri che precedono una potenza di 2. Poniamo Mk=2k-1, con k>1: un tale numero naturale (dispari) è detto numero di Mersenne. Come per i numeri di Fermat, studiamo quando un numero di Mersenne Mk è primo: vedremo in tale caso che k non può essere un esponente qualunque. Teorema. Se Mk=2k-1 (con k>1) è un numero primo, l’esponente k è necessariamente primo. Dimostrazione: Per assurdo sia k non primo, e sia k=ts, con 11) e 2t-12, si ha: Mp è primo  Sp-1  0 (mod Mp) Si può allora costruire un algoritmo deterministico di primalità per i numeri di Mersenne Mp=2p-1, con p primo >2, nel modo seguente: 1) Si calcolano i numeri interi T1, T2, …., Tp-1 ponendo: T1 = 4; per ogni i>1: Ti = (Ti-12-2)modMp (notare che per ogni i si ha 0 Ti2, per ogni divisore primo q di Mp=2p-1 si ha q  1 (mod p), quindi q=1+kp con k naturale, e inoltre si ha q  1,7 (mod 8).

Dimostrazione: Essendo Mp dispari, si ha q dispari. Poiché 2p  1 (mod q), si ha [2] p=[1] in Zq* e se s=ord([2]) è il periodo di [2] in Zq*, si ha sp, da cui, essendo p primo, s=p (perché s1 in quanto [2] [1]). Il periodo s=p è divisore della cardinalità q-1 di Zq* , dunque q  1 (mod p), q=1+kp con k naturale e in particolare k pari perché q, p sono dispari). Infine, posto k=2t, [2] (q-1)/2=([2] p)t=[1] in Zq* , 2(q-1)/2  1 (mod q), e per il criterio di Eulero 2 è resto quadratico modulo q, dunque (2/q)=1, e ciò sappiamo che avviene solo per q  1,7 (mod 8). Per trovare un divisore primo di Mp (con p primo >2 fissato), si può procedere allora facendo assumere in successione al parametro t i valori interi positivi t=1,2,…., e verificando con l’algoritmo della divisione se il numero q=1+2tp è  1,7 (mod 8) ed è divisore di Mp. Il minimo valore di t per cui ciò avviene fornisce con certezza un divisore primo q di Mp (se q non fosse primo avrebbe un divisore primo q1