Ricordiamo che n composto é detto pseudoprimo nella base a, se n supera il test di Fermat per tale scelta di a, cioè se a,n sono coprimi e se a n-1 1 (mod n).

Lezione del giorno 27 aprile 2009

Anche per il test di Rabin-Miller, come per il test di Fermat, può avvenire che un input n composto (dispari) superi il test, “fingendo” di essere primo.

Diremo che un naturale n composto dispari è fortemente pseudoprimo nella base a (dove 1an-1 è la base scelta casualmente nel passo 3)), se n supera il test di Rabin-Miller per tale scelta di a.

Ricordiamo che n composto é detto pseudoprimo nella base a, se n supera il test di Fermat per tale scelta di a, cioè se a,n sono coprimi e se a ^n-1 1 (mod n).

Ma allora se n composto (dispari) è fortemente pseudoprimo nella base a, certamente n è anche pseudoprimo nella stessa base a: infatti, essendo verificata una delle condizioni del passo 5), quadrando successivamente si ottiene (essendo (-1) ² =1) a ^n-1 = _a ²

^t = (a ²

^t ) ² 1 (mod n) (la proprietà che a,n sono coprimi è ovvia, perché in Z n si ha che [a] è invertibile con inverso [a ^n-2 ]).

Esempio.

Consideriamo il minimo numero di Carmichael n=561=31117.

Sappiamo che esso è pseudoprimo in tutte le basi a tali che a,561 sono coprimi, quindi in tutte queste basi (che sono la maggioranza) “finge” di essere primo superando il test di Fermat.

Una di tali basi è per esempio a=2; se utilizziamo con tale base il test di Rabin-Miller, si ha:

n-1=560=2 ^s t dove s=4, t=35, le potenze da studiare sono 2 ³⁵ ,2 ^235 =2 ⁷⁰ , 2 ^435 =2 ¹⁴⁰ , 2 ^835 =2 ²⁸⁰ , con le seguenti riduzioni modulo 561

2 ³⁵ mod561=263

2 ⁷⁰ mod561=(263) ² mod561=166 2 ¹⁴⁰ mod561=(166) ² mod561=67 2 ²⁸⁰ mod561=(67) ² mod561=1

quindi non é verificata nessuna delle condizioni del passo 4), e il numero n=561 non supera il test di Rabin-Miller nella base a=2 (cioé 561é soltanto pseudoprimo nella base a=2, ma non é fortemente pseudoprimo nella stessa base): 561 “si rivela” composto utilizzando la base a=2 nel test di Rabin- Miller.

Per concludere in modo definitivo che il test di Rabin-Miller sia un test di primalità probabilistico, dobbiamo calcolare un maggiorante per la probabilità che un input n composto (dispari) superi il test per una scelta casuale della base a.

In effetti storicamente Miller (1977) implementò per primo il test, ma avendo come scopo la costruzione di un test di primalità deterministico di complessità polinomiale: aveva infatti congetturato che se n è un input composto (dispari) di lunghezza binaria k, allora esiste una base a con 1a2k ² in cui n non è fortemente pseudoprimo (cioè in cui n non supera il test rivelando di essere composto); se tale congettura fosse vera (ma nessuno ha trovato una dimostrazione di ciò) il test diventerebbe deterministico, perché non si dovrebbe scegliere casualmente la base a, ma farle assumere tutti i valori nell’intervallo [1, 2k ² ] e se il test è sempre superato concludere con certezza che n è primo (la complessità del test è polinomiale di ordine O(k ⁶ )).

Solo in seguito Rabin (1980) ebbe l’idea di utilizzare lo stesso test ma come test di primalità probabilistico, e dimostrò che la probabilità che un numero composto superi il test è 1/4: quindi eseguendo il test k volte, con k scelte indipendenti della base casuale a, la probabilità che un numero composto superi tutte le volte il test è 1/4 ^k .

Poiché la dimostrazione del Teorema di Rabin è molto macchinosa, ci limiteremo ad una forma

semplificata in cui però la maggiorazione ottenuta per la probabilità è 1/2 (come nel test di Fermat),

ma senza le eccezioni presentate nel test di Fermat dai numeri di Carmichael:

Teorema di Rabin (forma semplificata).

Sia n>1 un numero naturale composto dispari. Il numero di basi a (con 1an-1) in cui n è fortemente pseudoprimo è  (n)/2.

Dimostrazione:

Se n non è un numero di Carmichael, sappiamo che il numero delle basi a in cui n è pseudoprimo è

 (n)/2, e poiché se n è fortemente pseudoprimo nella base a, n è pseudoprimo nella stessa base a, si ha la tesi.

Quindi supponiamo che n sia un numero di Carmichael.

Sia n-1=2 ^s t, con s>0, t naturale dispari.

Esiste qualche esponente k fra t, 2t, 2 ² t,…,2 ^s-1 t per il quale la congruenza x ^k -1 (mod n) abbia qualche soluzione x con 1xn-1 (per esempio k=t, x=n-1, perché (n-1) ^t (-1) ^t -1 (mod n)).

Dunque possiamo considerare il massimo esponente k fra t, 2t, 2 ² t,…,2 ^s-1 t per il quale la congruenza x ^k -1 (mod n) abbia qualche soluzione x con 1xn-1, e sia x=a una tale soluzione. Notiamo che a,n sono coprimi: infatti si ha a ^2k 1 (mod n), e [a] è invertibile in Z n con inverso [a ^2k-1 ].

Essendo n numero di Carmichael, per il criterio di Korselt n è prodotto di primi distinti:

n = p 1 p 2 …..p r (r>1, p i primi distinti dispari)

Consideriamo i numeri coprimi v=p 1 , z=p 2 …..p r ; per il Teorema Cinese del Resto esiste una soluzione del sistema di 2 congruenze:

 







z) (mod 1

x

v) (mod a

x

Se si considera una soluzione canonica x si ha 0xvz-1=n-1, anzi 1x n-1 (perché 0 non è soluzione della seconda congruenza). Inoltre a ^k -1 (mod n), quindi (essendo vn) a maggior ragione a ^k -1 (mod v), x ^k a ^k -1 (mod v), x ^k 1 ^k =1 (mod z). Ma allora non si ha x ^k 1 (mod n) (se fosse x ^k +1 (mod n), sarebbe 1-1 (mod v), impossibile perché v è dispari; se invece fosse x ^k -1 (mod n), sarebbe -11 (mod z), impossibile perché z è dispari). Infine x,n sono coprimi: se per assurdo non lo fossero, x sarebbe multiplo di qualche p i con i=1,2,…,r; ma x non è multiplo di v=p 1 (dalla prima congruenza del sistema seguirebbe p 1 a mentre a,n sono coprimi) ed x non è multiplo di p i con i>1 (dalla seconda congruenza del sistema seguirebbe p i 1 contraddizione perché p i è primo)

Consideriamo allora gli insiemi:

A={y interi / 1yn-1, n fortemente pseudoprimo nella base y}

S={y interi / 1yn-1, y ^k 1 (mod n)}

T={y interi / 1yn-1, y,n coprimi}

Si ha AS : se n é fortemente pseudoprimo nella base y, allora o si ha y ^t 1 (mod n) (nel qual caso essendo k=2 ⁱ t si ha y ^k = (y ^t ) ²

1 (mod n)) oppure si ha y ²

^t -1 (mod n) per qualche j=0,1,…,s-1 (nel qual caso se k=2 ⁱ t si ha per costruzione ji, da cui se j<i y ^k = (y ²

^t ) ²

 ( 1) ²

=1 (mod n), mentre se j=i y ^k = y ²

^t -1 (mod n)).

Si ha poi ST: se y ^k 1 (mod n), y ^2k 1 (mod n), [y] è invertibile in Z n (con inverso [y ^2k-1 ]), y,n sono coprimi.

Se consideriamo il numero x costruito nella prima parte (1 x n-1, tale che non é x ^k 1 (mod n), x,n coprimi) si ha xT-S. Sia g=S, e siano a 1 ,a 2 ,…,a g gli elementi distinti di A. Consideriamo le riduzioni b i =(a i x)modn con i=1,2,…,g: sono g elementi distinti ( se fosse (a i x)modn=(a j x)modn con ij, nel gruppo Z n * sarebbe [a i ][x]= [a j ][x], [a i ]=[a j ], contraddizione perché le classi [1],[2],…,[n-1]

sono distinte). Inoltre i b i sono coprimi con n (perché [b i ]= [a i ][x]Z n *), e sono in T-S (perché se fosse b i k =a i k x ^k 1 (mod n), sarebbe x ^k 1 (mod n), contraddizione).

Dunque T-S contiene un sottoinsieme di cardinalità g=S, e si conclude che:

AST/2 =(n)/2

Come conseguenza di tale versione del Teorema di Rabin, si ha che la probabilità che un numero composto superi il test di Rabin-Miller è 1/2 (in effetti 1/4 nella versione originale del Teorema):

infatti le basi casuali a sono in numero totale di n-1, e se h è il numero di quelle in cui n (composto) è fortemente pseudoprimo, la probabilità che n (composto) superi il test è (essendo (n)n-1):

h/(n-1)h/(n)[(n)/2]/(n)=1/2

Test di primalità per numeri di forma particolare

Studieremo ora dei test deterministici di primalità che sono di complessità polinomiale, ma che sono validi solo se l’input è un numero naturale di forma particolare.

In particolare ci occuperemo di numeri naturali della forma 2 ^k 1: quelli della forma 2 ^k +1 sono i cosiddetti numeri di Fermat, quelli della forma 2 ^k -1 sono i cosiddetti numeri di Mersenne.

Dimostreremo un risultato di Pocklington, che, sotto particolari ipotesi, dimostra una notevole proprietà dei fattori primi di un numero naturale.

Teorema di Pocklington.

Sia n>1 un numero naturale, q un fattore primo di n-1, q ^m la massima potenza di q che divide n-1.

Se esiste un naturale a con 1an-1 tale che:

1) a ^n-1 1 (mod n) 2) mcd(a ^(n-1)/q -1,n)=1

allora per ogni fattore primo p di n, si ha p1 (mod q ^m ), quindi p è della forma 1+tq ^m , con t intero.

Dimostrazione:

Essendo pn dalla 1) segue a ^n-1 1 (mod p), quindi [a] ^n-1 =[1] in Z p , ossia [a] è invertibile in Z p (con inverso [a ^n-2 ]) e nel gruppo moltiplicativo Z p * il periodo r di [a] è divisore di n-1; inoltre il periodo r di [a] è anche divisore della cardinalità p-1 di Z p * .

Affermiamo che:

r non è divisore di (n-1)/q (*)

Infatti se per assurdo fosse (n-1)/q=rk (con k intero), seguirebbe [a] ^(n-1)/q =([a] ^r ) ^k =[1], p(a ^(n-1)/q -1), in contraddizione con la 2).

Ma allora è anche vero che:

q non è divisore di (n-1)/r (notare che (n-1)/r è intero perché r(n-1) )

Infatti se per assurdo fosse (n-1)/r=qh (con h intero), sarebbe (n-1)/q=rh, in contraddizione con (*).

Essendo q ^m la massima potenza di q che divide n-1, si ha n-1=q ^m z, con z intero non divisibile per q.

Da r(n-1) segue n-1=rw=q ^m z (con w intero), e poiché q non è divisore di (n-1)/r=w, per la fattorizzazione unica si ha che q ^m r, ma r(p-1), quindi q ^m (p-1), e si ha la tesi.

Da questo teorema, aggiungendo un’ulteriore ipotesi, si ottiene un test deterministico di primalità:

Teorema di Proth-Pocklington.

Sia n>1 un naturale dispari, e sia 2 ^m la massima potenza di 2 che divide il numero pari n-1, in modo che sia n-1=2 ^m h con h naturale dispari. Se 2 ^m >h si ha:

n è primo  esiste un naturale a, con 1an-1, tale che a ^(n-1)/2 -1 (mod n) Dimostrazione:

(): Supponiamo n primo. Per il teorema di Gauss il gruppo moltiplicativo Z n * è ciclico, e se [a] è un suo generatore, il periodo di [a] è la cardinalità n-1 di Z n * .

Poiché [a] ^n-1 =[1], si ha (a ^(n-1)/2 ) ² =a ^n-1 1 (mod n), e per una proprietà già osservata nel test di Rabin-

Miller, ciò implica a ^(n-1)/2 1 (mod n), ma a ^(n-1)/2 1 (mod n) è da escludere (perché, essendo n il

periodo di [a], si ha [a] ^(n-1)/2 [1]), dunque a ^(n-1)/2 -1 (mod n).

(): Supponiamo l’esistenza del naturale a, con 1an-1, tale che a ^(n-1)/2 -1 (mod n), e per assurdo sia n non primo. Allora esisterebbe un divisore d (non banale) di n con d n , e a maggior ragione esisterebbe un divisore primo p di n con p n (basta scegliere un fattore primo p di d).

Verifichiamo le ipotesi 1) e 2) del Teorema di Pocklington (con q=2).

La 1) è verificata in quanto basta elevare al quadrato l’ipotesi a ^(n-1)/2 -1 (mod n).

Per quanto riguarda la 2), posto t= mcd(a ^(n-1)/2 -1,n)=1, si ha, essendo a ^(n-1)/2 -1 (mod n), a ^(n-1)/2 +1=kn (con k intero), 2=kn-(a ^(n-1)/2 -1), ossia t2 (perché tn, t(a ^(n-1)/2 -1)); ma tn con n dispari, dunque necessariamente t=1, e la 2) è verificata.

Dal Teorema di Pocklington segue allora che p1 (mod 2 ^m ), p-1=2 ^m w (con w naturale), 2 ^m p-1<p.

Ma per ipotesi n-1=2 ^m h con h naturale dispari e con 2 ^m >h, da cui n=1+2 ^m h<1+2 ^m 2 ^m =1+2 ^2m , n2 ^2m . Essendo n dispari la disuguaglianza è stretta cioè n<2 ^2m , da cui p n <2 ^m , contraddizione.

Possiamo notare che il teorema fornisce un test di primalità deterministico per input n dispari, tale

che n-1=2 ^m h con h naturale dispari e con 2 ^m >h: tuttavia il test non ha complessità polinomiale,

perché, benché testare la congruenza a ^(n-1)/2 -1 (mod n) equivalga alla condizione a ^(n-1)/2 modnn-1

(verificabile con complessità polinomiale con l’esponenziazione modulare), la ricerca dell’esistenza

di un valore a che soddisfi tale congruenza ha complessità esponenziale (il numero dei valori

possibili di a è <n<2 ^k se k=L(n) ).