Test di primalità probabilistici e deterministici

Università degli Studi di Catania

Facoltà di Scienze Matematiche, Fisiche e Naturali

Corso di Laurea in Informatica

Test di primalità probabilistici e deterministici

Tesi di Laurea di

Giancarlo D’Urso

Relatore: Chiar.mo Prof. Domenico Cantone

Anno Accademico 2006-2007 i

Ai miei genitori.

Ringraziamenti

Ringrazio il Professore Domenico Cantone, del Dipartimento di Matematica e Informatica, presso l’Università degli Studi di Catania, che mi ha guidato nella stesura della tesi, e aiutato in ogni mia difficoltà.

Inoltre, vorrei ringraziare il professore Burton Rosenberg, della Miami University, e il professor Hendrik Lenstra, della University of California, per aver instaurato gentilmente una corrispondenza elettronica volta al chiarimento di alcuni argomenti trattati.

Infine, dedico la tesi ai miei genitori, che in tutti questi anni di studio, mi hanno sostenuto materialmente e moralmente. ii

Indice

Ringraziamenti ii

Simboli e Notazioni vi

Prefazione viii

I Preliminari di algebra e di teoria dei numeri 1

1 Richiami di Algebra 2

1.1 Numeri interi e congruenze . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Strutture Algebriche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3 Aritmetica Modulare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.4 Cenni sulla teoria dei polinomi . . . . . . . . . . . . . . . . . . . . . . . . 23

2 Teoria dei Numeri 32

2.1 Richiami di Analisi Matematica . . . . . . . . . . . . . . . . . . . . . . . . 33

2.2 Teorema di Chebyshev . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.3 Teorema di Mertens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.4 Identità di Abel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.5 Teoria dei residui quadratici . . . . . . . . . . . . . . . . . . . . . . . . . 40

iii

Indice iv

II Test algoritmici di primalità 52

3 Il Crivello di Eratostene 53

3.1 Il Crivello di Eratostene . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.2 L’Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.3 Dimostrazione dell’algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.4 Complessità dell’algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4 L’algoritmo Miller-Rabin 57

4.1 Introduzione ai test probabilistici di primalità . . . . . . . . . . . . . . . . 58

4.2 L’algoritmo di Miller-Rabin . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.2.1 I numeri di Carmichael . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.2.2 L’Idea dell’Algoritmo di Miller-Rabin . . . . . . . . . . . . . . . . . . . . 62

4.2.3 L’Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

4.2.4 Dimostrazione della correttezza dell’algoritmo di Miller-Rabin . . . 64

4.2.5 Probabilità di errore del Test di Miller-Rabin . . . . . . . . . . . . . . 66

4.2.6 Complessità dell’algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5 L’algoritmo Solovay-Strassen 70

5.1 L’idea dell’algoritmo di Solovay-Strassen . . . . . . . . . . . . . . . . . . 71

5.2 L’algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.3 Dimostrazione della correttezza dell’algoritmo di Solovay-Strassen . . . . 72

5.4 Probabilità di errore del Test di Solovay-Strassen . . . . . . . . . . . . . . 74

5.5 Complessità dell’algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6 L’algoritmo Agrawal-Kayal-Saxena 76

6.1 Il problema delle potenze perfette . . . . . . . . . . . . . . . . . . . . . . 77

6.1.1 Dimostrazione di Correttezza dell’algoritmo . . . . . . . . . . . . . . 77

6.1.2 Complessità dell’algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6.2 L’algoritmo di Agrawal, Kayal e Saxena . . . . . . . . . . . . . . . . . . . 81

6.2.1 Idea dell’algoritmo Agrawal, Kayal e Saxena . . . . . . . . . . . . . . 81

Indice v

6.2.2 L’algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.2.3 Dimostrazione di Correttezza dell’algoritmo . . . . . . . . . . . . . . . 83

6.2.4 Complessità dell’algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . 93

A L’Implementazione 96

A.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

A.2 Analisi dei Requisiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

A.3 Progettazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

A.4 Validazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

Bibliografia 114

Simboli e notazioni

N insieme dei numeri naturali

Z insieme dei numeri interi

R insieme dei numeri reali

C insieme dei numeri complessi

P insieme dei numeri primi

N\P insieme dei numeri composti

Z_n gruppo additivo modulo n

Z_n^* gruppo moltiplicativo modulo n

Z_n[x] insieme dei polinomi a coefficienti in Z_n

Z_n[x]/h(x) anello di polinomi modulo h(x) in Z_n[x]

ln n logaritmo naturale di n

log n logaritmo in base due di n

⌊x⌋ intero più grande, minore o uguale a x

⌈x⌉ intero più piccolo, maggiore o uguale a x

a | b a divide b

a - b a non divide b

√x radice quadrata di x

b^a elevamento a potenza

n! fattoriale di n

e numero di Nepero

i unità immaginaria vi

Simboli e notazioni vii

π pi greco

φ(n) funzione totiente

gcd(a, b) massimo comune divisore tra a e b

lcm(a, b) minimo comune multiplo tra a e b

sin(x) seno di x

cos(x) coseno di x

∫_a^b f(x)dx integrale definito tra a e b di f(x) in x

P simbolo di sommatoria

Q simbolo di produttoria

lim f(x) limite per x che tende ad infinito di f(x)

x→∞

ord_r(n) ordine di n modulo r

ν_p(n) massimo esponente di una potenza in base p che divide n

(a/b) simbolo di Jacobi e/o Legendre

(a/b) coefficiente binomiale

P_r[E] probabilità dell’evento E

O simbolo di O-grande

⊕ operazione generica

a ≡ b (mod n) a congruo b modulo n

a ≢ b (mod n) a non è congruo b modulo n

f(x) ≡ g(x) (mod p) coefficienti di f(x) e g(x) congrui modulo p

f(x) ≡ g(x) (mod h(x), p) f(x) ≡ g(x) (mod h(x)) in Z_p[x]

Prefazione

La matematica si è sempre interessata allo studio dei numeri primi, cercando di evidenziarne le proprietà e accentuarne le differenze con gli altri numeri interi, detti composti.

Oggi, molte di queste caratteristiche sono ancora da formalizzare e rimangono delle congetture. Recentemente è stato risolto un problema, noto in letteratura come “PRIMES” e che consiste nel trovare un algoritmo efficiente per testare la primalità di un numero. In realtà, l’interesse sull’efficienza computazionale si è diffuso solo negli anni sessanta con l’avvento dei calcolatori elettronici, ma da parecchi secoli, i matematici si sono cimentati nella produzione di algoritmi di primalità, più o meno veloci. Il più antico risale al 240 a.C. ed è il Crivello di Eratostene. Questo algoritmo produce una lista di numeri primi minori o uguali ad un intero scelto, ma con complessità esponenziale rispetto alla dimensione dell’input. Il XVII secolo segna un passo in avanti nella ricerca, grazie al piccolo teorema di Fermat. Il teorema dimostrò una proprietà per tutti i numeri primi, valida anche per alcuni numeri composti (detti di Carmichael), fornendo lo strumento teorico per costruire il primo algoritmo probabilistico della storia: il test di pseudoprimalità di Fermat.

Nel 1975, Diffie e Hellman presentarono una nuova teoria crittografica, basata sui crittosistemi a chiave pubblica, che anziché usare una stessa chiave (mantenuta segreta) tra due interlocutori per codificare e decodificare le informazioni, prevedeva due chiavi distinte, una per la codifica (chiave pubblica) e una per la decodifica (chiave privata e segreta). La chiave privata non poteva essere calcolata “facilmente” a partire dalla chiave pubblica, pertanto solo il possessore della chiave privata era in grado di decodificare le informazioni. L’applicazione pratica di questa teoria incentivò l’uso dei numeri primi, basti pensare che la robustezza dell’RSA trae origine dalla difficoltà nel fattorizzare un numero, di cui si sa essere il prodotto di due numeri primi. Quindi, stabilire se un numero è primo o composto, è utile per la crittografia, quanto per la crittoanalisi. Più la risposta di un algoritmo di primalità è veloce, più l’RSA e altri crittosistemi diventano vulnerabili. Così, nello stesso periodo, nascono algoritmi probabilistici polinomiali come l’algoritmo Solovay-Strassen (1975) e l’algoritmo Miller-Rabin (1976).

Gli ultimi decenni vedono il proliferare di algoritmi sempre più veloci, tanto da far avanzare l’ipotesi che si possa costruire un algoritmo deterministico e contemporaneamente polinomiale. Il traguardo è sempre più vicino nel 1983, quando Adleman, Pomerance e Rumely svilupparono un algoritmo deterministico di complessità O(log n)^{log log log n}.

Ma nel 2002, tre matematici indiani (Agrawal, Kayal, Saxena) raggiungono l’obiettivo diffondendo un articolo “PRIMES is in P” destinato a rimanere nella storia e che darà origine a una sequenza di miglioramenti, fino a raggiungimento della forma attuale (6^◦ versione).

Questa tesi illustra attraverso una scelta mirata di algoritmi, l’evoluzione storica del problema, mostrando i progressi che sono stati raggiunti in termini di complessità e di fattibilità realizzativa. La trattazione si sofferma anche sulla differenza tra algoritmi deterministici (cioè algoritmi che producono output sicuramente corretti) e algoritmi probabilistici (cioè algoritmi che possono, per loro natura, produrre output errati ma con basse probabilità di errore). Per ottemperare agli obiettivi previsti, la tesi si articola in sei capitoli. I capitoli iniziali (primo e secondo) contengono tutti gli strumenti matematici per la comprensione degli algoritmi trattati, tra i quali ricordiamo il teorema cinese del resto, il piccolo teorema di Fermat, la legge di reciprocità quadratica, la teoria sui polinomi ciclotomici e risultati di teoria analitica dei numeri. I quattro capitoli successivi, trattano in sequenza il crivello di Eratostene, l’algoritmo di Miller-Rabin, l’algoritmo Solovay-Strassen e l’algoritmo Agrawal-Kayal-Saxena. Per ciascun algoritmo è stata dimostrata la correttezza e la complessità, mentre per gli algoritmi probabilistici è previsto un paragrafo che ne descrive la probabilità di errore. Infine, il lavoro è corredato

Prefazione x

da una implementazione in Java degli ultimi tre algoritmi, mediante la quale è possibile confrontare i risultati ottenuti e i rispettivi tempi di elaborazione, per una data lista di numeri.

Parte I

Preliminari di algebra e di teoria dei numeri

1

Capitolo 1

Richiami di algebra

2

Capitolo 1. Richiami di algebra 3

1.1 Numeri interi e congruenze

Per trattare il problema della primalità dei numeri, è necessario studiare l’insieme dei numeri naturali e l’insieme degli interi relativi. Purtroppo l’introduzione di questi insiemi nella cultura matematica e la loro trattazione completa e rigorosa non è banale. Mi limiterò dunque ad esporre un elenco minimale di proprietà di Z ed N.

Inizio, dunque, introducendo il concetto di divisione.

Teorema 1 (Proprietà euclidea degli interi). Siano a, b ∈ Z e a ≠ 0. Allora ∃q ∈ Z e ∃r ∈ N tale che b = qa + r con 0 ≤ r < |a|.

Se b = qa, per qualche q, si dice che a divide b (o che a è un divisore di b, o che b è un multiplo di a). A volte per indicare ciò, scriviamo a | b. Mentre scriviamo a - b per indicare che a non divide b.

Enunciamo qualche proprietà dei divisori comuni.

• ∀a ∈ Z, a | a
• ∀a, b, c ∈ Z, a | b e b | c ⇒ a | c
• ∀a, b, d ∈ Z, d | a e d | b ⇒ d | (a + b) e d | (a − b)
• ∀a, b, d, x, y ∈ Z, d | a e d | b ⇒ d | (ax + by)
• ∀a, b ∈ Z, a | b e b | a ⇒ a ∈ {+b, −b}

Definizione 1 (Massimo comune divisore). Siano a, b ∈ Z con a ≠ 0 e b ≠ 0. Definiamo massimo comune divisore tra a e b e lo denotiamo con gcd(a, b) quel numero h ∈ N tale che:

• ∀d ∈ Z se d | a e d | b allora d | h
• ∃x, y ∈ Z: h = ax + by

Capitolo 1. Richiami di algebra 4

Il massimo comune divisore di due interi a e b, è il più grande dei divisori comuni di a e b. Quando a = b = 0, per convenzione, si assume gcd(0, 0) = 0. Inoltre se a e b non sono entrambi nulli, allora 1 ≤ gcd(a, b) ≤ min(|a|, |b|). Quelle che seguono, sono le proprietà elementari della funzione gcd:

• ∀a, b ∈ Z, gcd(a, b) = gcd(b, a)
• ∀a, b ∈ Z, gcd(a, b) = gcd(−a, b)
• ∀a, b ∈ Z, gcd(a, b) = gcd(|a|, |b|)
• ∀a ∈ Z, gcd(a, 0) = |a|
• ∀a, k ∈ Z, gcd(a, ka) = |a|
• ∀a, b ∈ Z e n ∈ N, gcd(na, nb) = n gcd(a, b)

Teorema 2. Se a, b ∈ Z, non entrambi nulli, allora gcd(a, b) è il più piccolo elemento positivo dell’insieme {ax + by : x, y ∈ Z}.

Dimostrazione. Sia s il più piccolo positivo intero dell’insieme {ax + by : x, y ∈ Z} e si abbia s = ax + by. Sia q = ⌊a/s⌋. Sappiamo che:

a mod s = a − qs = a − q(ax + by) = a(1 − qx) + b(−qy).

Dunque anche a mod s sta nell’insieme delle combinazioni lineari. Ma, poiché a mod s < s si ha che a mod s = 0. Allora, s | a e per lo stesso motivo s | b. Pertanto s è un divisore comune di a e di b. Quindi gcd(a, b) ≥ s, perché s è una combinazione lineare di a e b. Ma per la proprietà 4 dei divisori comuni, gcd(a, b) | s. Ciò implica che gcd(a, b) ≤ s.

In definitiva abbiamo che gcd(a, b) = s e il teorema è dimostrato.

Generalmente, il massimo comune divisore tra due numeri interi si calcola utilizzando la scomposizione in fattori primi degli operandi (Definizione 7). In particolare si moltiplicano tutti i fattori primi comuni tra i due numeri, elevandoli al minimo esponente con cui compaiono nella scomposizione in fattori.

Capitolo 1. Richiami di algebra 5

Questa procedura, da un punto di vista computazionale, è troppo onerosa. Nelle applicazioni, si adotta un algoritmo diverso, più efficiente e di particolare rilevanza storica. Si tratta dell’algoritmo di Euclide. L’algoritmo è il seguente:

euclide(a, b)

1. if (b == 0) then
2. return a;
3. else
4. return euclide(b, a mod b);

La correttezza di questo algoritmo può essere dimostrata con il seguente teorema.

+

Teorema 3. ∀a, b ∈ Z⁺, gcd(a, b) = gcd(b, a mod b).

Dimostrazione. Per dimostrare che gcd(a, b) = gcd(b, a mod b) basta dimostrare che gcd(a, b) | gcd(b, a mod b) e gcd(b, a mod b) | gcd(a, b). Mostriamo che gcd(a, b) | gcd(b, a mod b). Poniamo h = gcd(a, b) e (a mod b) = a − ⌊a/b⌋b. Poiché (a mod b) è una combinazione lineare di a e b, si ha che h | (a mod b). E quindi poiché h | b concludiamo che h | gcd(b, a mod b).

Viceversa, per dimostrare che gcd(b, a mod b) | gcd(a, b), se poniamo h = gcd(b, a mod b), allora h | b e h | (a mod b). Poiché a = ⌊a/b⌋b + (a mod b), si ha che a è combinazione lineare di b e di (a mod b). E quindi si conclude che h | a, da cui segue la tesi.

Infine, per dimostrare che l’algoritmo di Euclide non richiama se stesso all’infinito, basta notare che ad ogni chiamata ricorsiva, il secondo argomento decresce. Infatti la quantità a mod b è sempre minore di b e maggiore o uguale di zero. Quindi il decremento non può andare avanti all’infinito e termina proprio quando il secondo argomento è zero. In tal caso, l’algoritmo restituisce il primo argomento applicando la proprietà gcd(a, 0) = a.

Capitolo 1. Richiami di algebra 6

Per determinare la complessità dell’algoritmo, è importante stabilire il numero di chiamate ricorsive richieste per portarlo a termine. Il teorema di Lamé, che nel suo enunciato fa uso dei numeri di Fibonacci, ci fornisce una soluzione.

Definizione 2 (numeri di Fibonacci). I numeri di Fibonacci sono definiti dalla seguente ricorrenza:

F₀ = 0

F₁ = 1

F_i = F_i−1 + F_i−2, ∀i ≥ 2.

Teorema 4 (Lamé). Se a > b ≥ 0 e l’algoritmo di Euclide applicato alla coppia (a, b), esegue k ≥ 1 iterazioni, allora a ≥ F_k+2 e b ≥ F_k+1.

Dimostrazione. Dimostriamo il teorema per induzione, sul numero k di chiamate ricorsive

Caso base: k = 1. Poiché viene eseguita una chiamata ricorsiva, si ha che b ≠ 0. Quindi b ≥ 1 = F₂. Inoltre, poiché a > b si ha che a ≥ 2 = F₃.

Il caso base può verificarsi dopo una serie di chiamate ricorsive. In tutte queste chiamate b sarà sempre maggiore di (a mod b), quindi la condizione a > b varrà sempre. Questo è fondamentale per la verifica del caso base.

Passo induttivo: Supponiamo il teorema vero per k − 1 chiamate ricorsive, e dimostriamolo per k chiamate ricorsive. Cioè supponiamo che se euclide(b, a mod b) esegue k − 1 iterazioni allora b ≥ F_k+1 e b ≥ F_k, e dimostriamo che euclide(a, b) è tale da soddisfare la condizione a ≥ F_k+2. Poiché a > b (in qualsiasi chiamata ricorsiva) avremo che ⌊a/b⌋ ≥ 1, da cui:

a ≥ b + (a − ⌊a/b⌋b) = b + (a mod b) ≥ F_k+1 + F_k = F_k+2.

Capitolo 1. Richiami di algebra 7

Grazie al teorema di Lamé, sappiamo che F_k+2 ≤ a e poiché, come è ben noto, F_i ≈ ((1 + √5) / 2)ⁱ, si ha:

F_k+2 ≤ a ⇔ ((1 + √5) / 2)^k+2 ≤ a ⇔ k ≤ log a − 2