Teoria dei numeri e Crittografia: lezione del 26 ottobre 2011 Nota storica: il più grande numero primo conosciuto attualmente è il numero 243.112.609-1

(1)

Teoria dei numeri e Crittografia: lezione del 26 ottobre 2011

Nota storica: il più grande numero primo conosciuto attualmente è il numero 2

^43.112.609

-1 (è uno dei cosiddetti numeri di Mersenne della forma 2

ⁿ

-1, che studieremo in seguito). Esso ha 12.978.189 cifre (in base 10) ed è stato trovato nell’Agosto 2008 nell’ambito del progetto GIMPS (Great Internet Mersenne Primes Search: vedere il sito www.mersenne.org).

Un test di primalità è un algoritmo che permette di testare se un numero naturale a>1 dato in input è primo o no: l’output di un tale algoritmo è dunque “a è primo” oppure “a non è primo”..

Il più “ingenuo” dei test di primalità consiste ovviamente nell’effettuare le divisioni di a per i numeri naturali j=2,3,…,a-1 : se per uno di tali j la divisione ha resto 0 l’output è “a non è primo”;

in caso contrario l’output è “a è primo”. Se x=L(a) è la lunghezza binaria dell’input, ogni divisione ha complessità di ordine non superiore ad O(x

²

), ma il numero di divisioni, come funzione dell’input a, è f(a) = (a-2) (nel caso peggiore): poiché 2

^x-1

-2 ≤ a-2 < 2

^x

-2, se consideriamo il numero di divisioni come funzione g(x) della lunghezza binaria x, in termini di ordine si ha

O(2

^x

) = O(2

^x-1

-2) ≤ O(g(x)) ≤ O(2

^x

-2)=O(2

^x

)

dunque il numero di divisioni ha ordine esponenziale e tale algoritmo non è perciò “efficiente”.

Osservazione. Il ragionamento applicato sopra si può applicare in tutte le situazioni simili: se una funzione f(a) dell’input a è di ordine lineare, la stessa funzione, considerata come funzione della lunghezza binaria x di a, è di ordine esponenziale O(2

^x

); con lo stesso ragionamento si può dimostrare che più in generale se f(a) è di ordine polinomiale di grado m, allora la stessa funzione, considerata come funzione della lunghezza binaria x di a, è di ordine esponenziale O((2

^m

)

^x

).

Il test di primalità sopra esposto può essere reso più efficiente limitandosi per esempio ad input a dispari (un numero pari a non è primo tranne nel caso banale a=2) ed effettuando quindi le divisioni solo per i valori dispari j con 1<j<a, ma anche in questo caso il numero delle divisioni è di ordine lineare rispetto ad a, quindi di ordine esponenziale rispetto ad x.

Una efficienza ancora superiore si può ottenere con la seguente osservazione: se a non è primo esiste un suo divisore non banale ≤ a (se infatti a=bc con b,c divisori non banali di a, e se per assurdo fosse b, c > a , seguirebbe a>( a )

²

, contraddizione). Dunque nell’algoritmo precedente si potrebbero effettuare solo le divisioni per i valori j con 1<j ≤ a quindi stavolta il numero di divisioni sarebbe di ordine O( a )<O(a) come funzione di a, ma purtroppo ancora di ordine esponenziale O((2

^1/2

)

^x

) come funzione di x .

Problema

1) Esiste un test di primalità di complessità non superiore alla polinomiale ?

Il problema è rimasto aperto per molto tempo: dagli esempi precedenti era chiaro come la strategia migliore fosse quella di trovare una proprietà “intrinseca” dei numeri primi che si potesse testare con un algoritmo di complessità polinomiale, e non quella di trovare un eventuale divisore non banale dell’input.

Il problema 1) è stato infine risolto nel 2003 da Agrawal, Kayal, Saxena nel loro articolo “Primes in P”, con la costruzione di un test di primalità di complessità polinomiale, ormai noto come “test AKS” (test di cui ci occuperemo in seguito).

I test di primalità (così come sono stati da noi finora) definiti sono test di primalità deterministici

nel senso che, dato in input un numero naturale a>1, essi forniscono come output “a è numero

primo” se e solo se l’input a è un numero primo.

(2)

Esistono però i cosiddetti test di primalità probabilistici nei quali vi è la scelta casuale di alcuni elementi utilizzati durante l’esecuzione dell’algoritmo e nei quali, se l’input a è primo, l’output è sempre (correttamente) “a è un numero primo”, ma se a non è primo l’output può essere talvolta (non correttamente) “a è un numero primo”, e la probabilità di tale errore è maggiorata da una costante C<1 indipendente sia dall’input che dagli elementi casuali. In questo caso eseguendo k volte il test sullo stesso input a, se l’output fosse tutte le volte “a è primo” si potrebbe dichiarare che l’input a è effettivamente un numero primo con una probabilità di errore maggiorata da C

^k

(quantità che si può rendere piccola a piacere).

Sono ben noti da tempo test di primalità probabilistici di complessità polinomiale (come il test di Rabin-Miller, anche questo oggetto in futuro del nostro studio, nel quale la costante C è 1/4).

E’ anche utile notare che esistono test di primalità deterministici di complessità polinomiale, ma che sono validi solo per numeri naturali particolari (per esempio i numeri di Fermat della forma 2

ⁿ

+1, oppure i numeri di Mersenne della forma 2

ⁿ

-1): anche di questi test parleremo in seguito.

Un algoritmo di fattorizzazione è invece un algoritmo che, dato in input un numero naturale a>1, calcola tutti i fattori primi della sua fattorizzazione.

In generale un algoritmo di fattorizzazione si limita, dato l’input a>1, a cercare un divisore non banale b di a (se b non esiste si conclude che a è primo e che ha la sola fattorizzazione banale a=a): una volta trovato b si pone c = a/b in modo che si abbia a = bc, e si applica di nuovo l’algoritmo ai fattori b, c : così procedendo dopo un numero finito di passi l’algoritmo trova i fattori primi della fattorizzazione di a.

Illustreremo in seguito vari algoritmi di fattorizzazione più o meno efficienti (algoritmo di Fermat, algoritmo di Pollard etc….).

Problema

2) Esiste un algoritmo di fattorizzazione di complessità non superiore alla polinomiale ?

Al contrario del problema 1), il problema 2) attualmente non è stato risolto (e molti matematici sono convinti che non abbia soluzione).

Distribuzione dei numeri primi

Nella successione dei numeri naturali, i numeri primi sono distribuiti in modo irregolare.

Si possono per esempio costruire intervalli di k naturali consecutivi (con k numero naturale arbitrariamente grande) che non contengono nessun numero primo: basta considerare i k numeri naturali consecutivi della forma (k+1)!+j dove j assume i k valori 2,3,…,k+1 (ognuno di essi è multiplo di j, perché j(k+1)!, quindi non è primo).

Se ordiniamo in ordine crescente i numeri primi in una successione p

1

, p

2

, ….., p

n

,….. (quindi p

1

=2, p

₂

=3, p

₃

=5, etc..) non esiste attualmente una formula algebrica che permetta di calcolare il numero primo p

_n

di posto n, ma si può dare un maggiorante (un po’ “grezzo”) per l’ordine di grandezza di p

n

:

Teorema.

Per ogni numero naturale n si ha p

_n

≤ 2

⁽²^n-1⁾

.

Dimostrazione:Per induzione su n (II

^a

forma). Per n=1 si ha p

1

=2= 2

⁽²^1-1⁾

. Dato n>1, supponiamo la tesi vera per ogni k=1,….,n-1, e dimostriamola per n: se poniamo a=(

n-1 i i=1

∏ p )+1, per il Teorema

(3)

di Fattorizzazione unica esisterà un primo p divisore di a, e sarà p ≠ p

₁

,p

₂

,…,p

_n-1

(altrimenti si avrebbe p1, contraddizione), dunque (essendo i primi p

_i

ordinati in modo crescente) :

p

_n

≤ p ≤ a =(

n-1 i i=1

∏ p ⁾⁺¹ ^≤ ⁽

^n-1 ⁽²^i-1⁾

i=1

∏ 2 ⁾⁺¹⁼

n-1 i-1 i=1

2

 

 



∑



+1 (per l’ipotesi induttiva).

Ma è facile dimostrare (usando la I

^a

forma dell’ induzione) che

n-1 i-1 i=1

∑ 2 ⁼²

^n-1

-1 , dunque:

p

_n

≤ 2

⁽²^n-1^-1)

+1=

(2n-1)

2 2 +1 ≤

(2n-1)

2 2 +

(2n-1)

2 2 = 2

⁽²^n-1⁾

e si ha la tesi.

Nota: il maggiorante 2

⁽²^n-1⁾

per p

_n

è molto “debole”, e in generale 2

⁽²^n-1⁾

è molto più grande di p

_n

; per esempio per n=4 si ha p

₄

=7 ma 2

⁽²^4-1⁾

=256.

Nell’ambito dello studio della distribuzione dei numeri primi, può essere interessante valutare il numero di primi in un certo intervallo [0,x] della semiretta positiva dell’asse reale. Poniamo, per ogni reale x>0 :

π (x) = {p / p è primo, p ≤ x}

(dunque π (x) è il numero dei primi non superiori al numero reale x).

Per esempio π (22,3)= {p / p è primo, p ≤ 22,3}={2,3,5,7,11,13,17,19}=8

Non esistono attualmente formule algebriche per il calcolo esatto di π (x). Per esempio, usando i computers, si è verificato che :

π ₍₁₀

¹⁴

) = 3.204.941.750.802

(i valori massimi attualmente calcolati sono relativi a valori di x intorno a 10

²²

).

Sfruttando il Teorema precedente, possiamo trovare un minorante (anche questo un po’ “grezzo”) per π _(x):

Teorema.

Per ogni reale x>0 si ha π _(x) ≥  _log

₂

_(log

₂

_x)  _+1.

Dimostrazione:

Sia n=  log

₂

(log

₂

x)  +1: dunque n è il più grande intero tale che n ≤ log

₂

(log

₂

x)+1

o equivalentemente

n-1 ≤ log

₂

(log

₂

x), 2

^n-1

≤ log

₂

x, 2

⁽²^n-1⁾

≤ x.

Nella successione (crescente) dei primi, si ha (per il teorema precedente) che il numero primo p

n

di posto n è ≤ 2

⁽²^n-1⁾

; dunque:

p

1

<p

2

<….<p

n

≤ ₂

⁽²^n-1⁾

≤ _x.

Poiché almeno gli n primi distinti p

₁

, p

₂

, …., p

_n

sono ≤ x, si conclude che n ≤π (x) e si ha la tesi.

Nota: il minorante  _log

₂

_(log

₂

_x)  _{+1 per} π (x) è molto “debole”, e in generale  _log

₂

_(log

₂

_x)  +1 è molto più piccolo di π (x); per esempio per x=10

⁹

si ha  _log

₂

_(log

₂

_x)  _{+1=5 ma} π _(x) ≈ _5x10

⁷

_.

Nel corso del tempo, i matematici hanno cercato funzioni che “approssimassero” la funzione π _(x).

Il risultato più famoso è il seguente, che si dimostra con metodi analitici (e del quale omettiamo la

dimostrazione):

(4)

Teorema di Hadamard-De La Vallé Poussin.

Considerata la funzione f(x)=x/log(x) (definita per x>0, x ≠ 1) dove log(x) è il logaritmo neperiano, si ha:

x

lim π(x) =1

→∞

f(x)

Quindi, per x abbastanza grande, il rapporto “percentuale” π(x)

f(x) è “abbastanza vicino” ad 1, e in questo senso f(x)=x/log(x) è una buona approssimazione di π _(x).

Per esempio f(10

¹⁴

) ≈ 3.102.103.442.166,

14 14

π(10 )

f(10 ) ≈ 3.204.941.750.802

3.102.103.442.166 ≈ 1.033.

Una funzione che approssima ancora meglio π (x) è la funzione (definita per x ≥ _2):

li(x) =

x

2

1 dt log(t)

∫

detta “logaritmo integrale”.

In pratica il valore li(x) misura l’area sottesa dalla curva del grafico della funzione 1/log(t) relativamente all’intervallo [2,x].

Anche per tale funzione si può dimostrare che si ha

x®¥

lim π(x) =1

li(x) , ma per esempio:

li(10

¹⁴

) ≈ 3.204.942.065.692

14 14

π(10 )

li(10 ) ≈ 3.204.941.750.802

3.204.942.065.692 ≈ 0,9999999

(approssimazione migliore di quella ottenuta con la funzione x/log(x)).

Per x>7 la funzione li(x) sembra approssimare sempre per eccesso π (x): con i moderni calcolatori si è arrivati al calcolo relativo a valori di x intorno a 4 ⋅ 10

²²

, e si è sempre verificato che li(x)> π (x).

Molti matematici (tra cui Gauss e Riemann) congetturarono che ciò fosse vero per ogni valore x>7, ma Littlewood (1914) dimostrò che la differenza li(x)- π (x) cambia segno infinite volte per x che tende a infinito (dimostrazione non costruttiva). Tuttavia non è stato ancora trovato effettivamente un valore di x per cui li(x)< π (x). Nel 1933 Skewes dimostrò che il più piccolo di tali x è < 10

⁽¹⁰³⁴⁾

(un numero con 10

³⁴

+1 cifre in base 10). Tale maggiorazione è stata nel tempo migliorata: nel 2000 si é dimostrato che il più piccolo di tali x è <1,4 ⋅ 10

³¹⁶

(un numero però ancora al di là delle capacità dei calcolatori moderni).

Calcoliamo approssimativamente la probabilità che, scelto casualmente un numero naturale y di n cifre (in base 10), esso sia primo. Si ha 10

^n-1

≤ y <10

ⁿ

, quindi i numeri naturali di n cifre sono in numero di (10

ⁿ

-10

^n-1

)=9 ⋅ ₁₀

^n-1

, mentre fra di essi i valori primi sono in numero di π ₍₁₀

ⁿ

_)- π ₍₁₀

^n-1

_);

utilizzando l’approssimazione di π (x) mediante x/log(x), la probabilità che y sia primo è:

[ π ₍₁₀

ⁿ

_)- π ₍₁₀

^n-1

_{)]/( 9} ⋅ ₁₀

^n-1

₎ ≈ _[(10

ⁿ

_/log(10

ⁿ

_{))- (10}

^n-1

_/log(10

^n-1

_))]/(9 ⋅ ₁₀

^n-1

_{) =}

= [(10

ⁿ

/nlog(10))- (10

^n-1

/(n-1)log(10))]/(9 ⋅ ₁₀

^n-1

_{) =}

= (9n-10)/[9n(n-1)log(10)] ≈ 1/[nlog(10)] (perché (9n-10) ≈ _9(n-1)).

Tenendo conto che log(10) ≈ 2,3, la probabilità che un numero x di n cifre in base 10, scelto

casualmente, sia primo è ≈1/[2,3n]. Per esempio la probabilità che un numero di 100 cifre in base

(5)

Teoria dei numeri e Crittografia: lezione del 26 ottobre 2011 Nota storica: il più grande numero primo conosciuto attualmente è il numero 243.112.609-1

Teoria dei numeri e Crittografia: lezione del 26 ottobre 2011

Nota storica: il più grande numero primo conosciuto attualmente è il numero 2

-1 (è uno dei cosiddetti numeri di Mersenne della forma 2

-1, che studieremo in seguito). Esso ha 12.978.189 cifre (in base 10) ed è stato trovato nell’Agosto 2008 nell’ambito del progetto GIMPS (Great Internet Mersenne Primes Search: vedere il sito www.mersenne.org).

Un test di primalità è un algoritmo che permette di testare se un numero naturale a>1 dato in input è primo o no: l’output di un tale algoritmo è dunque “a è primo” oppure “a non è primo”..

Il più “ingenuo” dei test di primalità consiste ovviamente nell’effettuare le divisioni di a per i numeri naturali j=2,3,…,a-1 : se per uno di tali j la divisione ha resto 0 l’output è “a non è primo”;

in caso contrario l’output è “a è primo”. Se x=L(a) è la lunghezza binaria dell’input, ogni divisione ha complessità di ordine non superiore ad O(x

), ma il numero di divisioni, come funzione dell’input a, è f(a) = (a-2) (nel caso peggiore): poiché 2

-2 ≤ a-2 < 2

-2, se consideriamo il numero di divisioni come funzione g(x) della lunghezza binaria x, in termini di ordine si ha

O(2

) = O(2

-2) ≤ O(g(x)) ≤ O(2

-2)=O(2

)

dunque il numero di divisioni ha ordine esponenziale e tale algoritmo non è perciò “efficiente”.

Osservazione. Il ragionamento applicato sopra si può applicare in tutte le situazioni simili: se una funzione f(a) dell’input a è di ordine lineare, la stessa funzione, considerata come funzione della lunghezza binaria x di a, è di ordine esponenziale O(2

); con lo stesso ragionamento si può dimostrare che più in generale se f(a) è di ordine polinomiale di grado m, allora la stessa funzione, considerata come funzione della lunghezza binaria x di a, è di ordine esponenziale O((2

)

).

Una efficienza ancora superiore si può ottenere con la seguente osservazione: se a non è primo esiste un suo divisore non banale ≤ a (se infatti a=bc con b,c divisori non banali di a, e se per assurdo fosse b, c > a , seguirebbe a>( a )

, contraddizione). Dunque nell’algoritmo precedente si potrebbero effettuare solo le divisioni per i valori j con 1<j ≤ a quindi stavolta il numero di divisioni sarebbe di ordine O( a )<O(a) come funzione di a, ma purtroppo ancora di ordine esponenziale O((2

)

) come funzione di x .

Problema

1) Esiste un test di primalità di complessità non superiore alla polinomiale ?

Il problema 1) è stato infine risolto nel 2003 da Agrawal, Kayal, Saxena nel loro articolo “Primes in P”, con la costruzione di un test di primalità di complessità polinomiale, ormai noto come “test AKS” (test di cui ci occuperemo in seguito).

I test di primalità (così come sono stati da noi finora) definiti sono test di primalità deterministici

nel senso che, dato in input un numero naturale a>1, essi forniscono come output “a è numero

primo” se e solo se l’input a è un numero primo.

(quantità che si può rendere piccola a piacere).

Sono ben noti da tempo test di primalità probabilistici di complessità polinomiale (come il test di Rabin-Miller, anche questo oggetto in futuro del nostro studio, nel quale la costante C è 1/4).

E’ anche utile notare che esistono test di primalità deterministici di complessità polinomiale, ma che sono validi solo per numeri naturali particolari (per esempio i numeri di Fermat della forma 2

+1, oppure i numeri di Mersenne della forma 2

-1): anche di questi test parleremo in seguito.

Un algoritmo di fattorizzazione è invece un algoritmo che, dato in input un numero naturale a>1, calcola tutti i fattori primi della sua fattorizzazione.

Illustreremo in seguito vari algoritmi di fattorizzazione più o meno efficienti (algoritmo di Fermat, algoritmo di Pollard etc….).

Problema

2) Esiste un algoritmo di fattorizzazione di complessità non superiore alla polinomiale ?

Al contrario del problema 1), il problema 2) attualmente non è stato risolto (e molti matematici sono convinti che non abbia soluzione).

Distribuzione dei numeri primi

Nella successione dei numeri naturali, i numeri primi sono distribuiti in modo irregolare.

Se ordiniamo in ordine crescente i numeri primi in una successione p

, p

, ….., p

,….. (quindi p

=2, p

=3, p

=5, etc..) non esiste attualmente una formula algebrica che permetta di calcolare il numero primo p

di posto n, ma si può dare un maggiorante (un po’ “grezzo”) per l’ordine di grandezza di p

:

Teorema.

Per ogni numero naturale n si ha p

≤ 2

.

Dimostrazione:Per induzione su n (II

forma). Per n=1 si ha p

=2= 2

. Dato n>1, supponiamo la tesi vera per ogni k=1,….,n-1, e dimostriamola per n: se poniamo a=(

∏ p )+1, per il Teorema

di Fattorizzazione unica esisterà un primo p divisore di a, e sarà p ≠ p

,p

,…,p

(altrimenti si avrebbe p1, contraddizione), dunque (essendo i primi p

ordinati in modo crescente) :

p

≤ p ≤ a =(

∏ p )+1 ≤ (

∏ 2 )+1=

2

∑

+1 (per l’ipotesi induttiva).

Ma è facile dimostrare (usando la I

forma dell’ induzione) che

∑ 2 =2

-1 , dunque:

p

≤ 2

+1=

∏ p ⁾⁺¹ ^≤ ⁽

∏ 2 ⁾⁺¹⁼

∑ 2 ⁼²

π ₍₁₀

Sfruttando il Teorema precedente, possiamo trovare un minorante (anche questo un po’ “grezzo”) per π _(x):

Per ogni reale x>0 si ha π _(x) ≥  _log

_(log

_x)  _+1.

≤ ₂

≤ _x.

Nota: il minorante  _log

_(log

_x)  _{+1 per} π (x) è molto “debole”, e in generale  _log

_(log

_x)  +1 è molto più piccolo di π (x); per esempio per x=10

si ha  _log

_(log

_x)  _{+1=5 ma} π _(x) ≈ _5x10

_.

Nel corso del tempo, i matematici hanno cercato funzioni che “approssimassero” la funzione π _(x).