Per n=1 si ha p1=2=2(21-1)

(1)

Teoria dei numeri e Crittografia: lezione del 13 aprile 2011 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 p1, p2, ….., pn,….. (quindi p1=2, p2=3, p3=5, etc..) non esiste attualmente una formula algebrica che permetta di calcolare il numero primo pn di posto n, ma si può dare un maggiorante (un po’ “grezzo”) per l’ordine di grandezza di pn:

Teorema.

Per ogni numero naturale n si ha pn₂⁽²^n-1⁾.

Dimostrazione:Per induzione su n (II^a forma). Per n=1 si ha p1=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 di Fattorizzazione unica esisterà un primo p divisore di a, e sarà pp1,p2,…,pn-1 (altrimenti si avrebbe p1, contraddizione), dunque (essendo i primi pi ordinati in modo crescente) :

pn p  a =( ^n-1 i i=1

p ^{)+1  (} ^n-1 ⁽²^i-1⁾

i=1

2 ⁾⁺¹⁼ ^n-1i=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:

pn₂⁽²^n-1^-1)+1=

(2n-1)

2

2 +1

(2n-1)

2

2 +

(2n-1)

2

2 =₂⁽²^n-1⁾ e si ha la tesi.

Nota: il maggiorante ₂⁽²^n-1⁾ per pn è molto “debole”, e in generale ₂⁽²^n-1⁾è molto più grande di pn; per esempio per n=4 si ha p4=7 ma ₂⁽²^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 :

(10¹⁴) = 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.

(2)

Per ogni reale x>0 si ha (x)  log2(log2x)+1.

Dimostrazione:

Sia n=log2(log2x)+1: dunque n è il più grande intero tale che nlog2(log2x)+1

o equivalentemente

n-1log2(log2x), 2^n-1log2x, ₂⁽²^n-1⁾x.

Nella successione (crescente) dei primi, si ha (per il teorema precedente) che il numero primo pn di posto n è ₂⁽²^n-1⁾; dunque:

p1<p2<….<pn₂⁽²^n-1⁾ x.

Poiché almeno gli n primi distinti p1, p2, …., pn sono x, si conclude che n(x) e si ha la tesi.

Nota: il minorante log2(log2x)+1 per (x) è molto “debole”, e in generale log2(log2x)+1 è molto più piccolo di (x); per esempio per x=10⁹ si ha log2(log2x)+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):

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 π(x)

lim =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, π(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).

(3)

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^{(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 x di n cifre (in base 10), esso sia primo. Si ha 10^n-1x<10ⁿ, quindi i naturali di n cifre sono in numero di (10ⁿ-10^n-1), mentre fra di essi i valori primi sono in numero di (10ⁿ)-(10^n-1); utilizzando l’approssimazione di (x) mediante x/log(x), la probabilità che x sia primo è:

[(10ⁿ)-(10^n-1)]/(10ⁿ-10^n-1)  [(10ⁿ/logⁿ(x))- (10^n-1/log^n-1(x))]/(910^n-1) = (9n-10)/[9n(n-1)log(10)]  1/[nlog(10)].

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 10 sia primo è 1/230: se scegliamo casualmente 230 numeri di 100 cifre, statisticamente dovremmo aspettarci che uno di essi sia primo.

Quindi per trovare un numero primo di un fissato numero n di cifre (in base 10), si può scegliere casualmente un numero di n cifre, sottoporlo a un “test di primalità” e se il test non è superato cambiare la scelta del numero, e così via: statisticamente dovrebbero bastare circa 2,3n tentativi per trovare un numero primo.

Congruenze aritmetiche.

Ricordiamo la teoria delle congruenze aritmetiche.

La nozione di divisore (e simmetricamente quella di multiplo) si estende facilmente dall’insieme N dei numeri naturali all’insieme Z dei numeri interi relativi: dati gli interi relativi a,bZ si dice che a è divisore di b (o che b è multiplo di a) e si scrive ab, se esiste un intero relativo cZ tale che ac=b.

Fissato un intero relativo m (detto modulo), e dati i numeri interi relativi a,b, diremo che a è congruo b modulo m (e scriveremo ab (mod m)) se m(a-b).

In questo modo definiamo nell’insieme Z degli interi relativi una relazione, detta appunto congruenza modulo m, che è una relazione di equivalenza (come si dimostra facilmente).

Poiché è facile verificare che la congruenza modulo m coincide con la congruenza modulo –m, possiamo limitarci a studiare il caso di m0.

Poiché inoltre sono banali i casi m=0 (la congruenza modulo 0 non è altro che la relazione di eguaglianza) ed m=1 (nella congruenza modulo 1 tutti gli interi sono congrui fra loro) ci limiteremo a studiare il caso m>1.

Per ogni aZ si può costruire la classe di equivalenza rappresentata da a (detta classe di congruenza modulo m rappresentata da a):

[a]m = { xZ / xa (mod m) } = { xZ / x-a=km, con kZ } = { xZ / x=a+km, con kZ } (se non vi è possibilità di equivoco sul modulo m, useremo semplicemente il simbolo [a])

Per la teoria generale delle relazioni di equivalenza, dati a,bZ si ha [a]=[b] ab (mod m), e inoltre le classi di congruenza modulo m formano una partizione dell’insieme Z .

Teorema.

Fissato il modulo m>1, le classi di congruenza modulo m distinte sono tutte e sole le seguenti:

[0], [1], ……, [m-1] (*)

(4)

Dimostrazione:

Le classi (*) sono distinte: se per assurdo fosse [a]=[b] con 0b<a<n, si avrebbe ab (mod m), dunque 0<a-b<m sarebbe un multiplo di m (contraddizione).

Per ogni aZ la classe di congruenza [a] coincide con una delle classi (*): infatti se a>0 allora, dividendo a per m con quoziente q e resto r si ha a=mq+r , a-r=mq, ar (mod m), [a]=[r], con r compreso fra i valori 0,1,…,m-1; se invece a<0 allora, dividendo (-a) per m con quoziente q e resto r si ha -a=mq+r , a-(m-r)=m(-q-1), am-r (mod m), [a]=[m-r], con m-r compreso fra 1,…,m-1 (se r>0) oppure (se r=0) con [a]=[m]=[0].

Poiché 0,1,…,m-1 sono i possibili resti delle divisioni per m, le classi di congruenza modulo m sono anche dette classi resto modulo m, e il loro insieme è indicato con Zm : per il Teorema precedente si ha Zm = { [0], [1], ……, [m-1] }, e la cardinalità di Zm è uguale al modulo m.

Nella dimostrazione del Teorema, per ogni intero relativo aZ si è costruito un (unico) intero t compreso fra i valori 0,1,…,m-1 tale che [a]=[t] (o equivalentemente tale che at (mod m)): tale t è detto riduzione modulo m dell’intero a ed è indicato con a mod m .

Dato comunque aZ, un algoritmo per il calcolo della sua riduzione modulo m è indicato nella dimostrazione del Teorema ed esso comporta una divisione e (al più) una sottrazione: per quanto sappiamo sulla complessità degli algoritmi che eseguono tali operazioni, il calcolo di una riduzione modulo m si potrà dunque effettuare con una complessità non superiore alla polinomiale (in particolare non superiore alla quadratica).