NUMERI PRIMI

Carlo Toffalori, Camerino, 2009-10

L’aritmetica:

- l’insieme N dei numeri naturali 0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, … - addizione, moltiplicazione (sottrazione e divisione)

Dante, Convivio “L’arismetrica… del suo lume tutte si illuminano le scienze” Leopardi, Zibaldone “La certezza che dà l’aritmetica”

L’alfabeto 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Borges, Funes, o della memoria: “il primo stimolo gli venne dallo scontento che per il 33 ci volessero due segni e due parole, in luogo d’una sola parola e d’un solo segno” Leopardi, Zibaldone: “che sarebbe l’aritmetica se ogni numero si dovesse significare con una cifra diversa, e non colla diversa composizione di pochi elementi”

La rappresentazione in base 10:

1723 = 1 · 103 + 7 · 102 + 2 · 101 + 3 · 100.

Da notare:

- si fa riferimento al numero delle dita delle 2 mani ( per contare ) - un numero N ha lunghezza in base 10 che è la parte intera del suo logaritmo in base 10 più

uno Non l’unica possibile! Rappresentazione alternativa in base 2

0,1 ⇒ 0, 1, 10, 11, 100, 101, 110, 111, 1000, ...

11001 = 1 · 104 + 1 · 103 + 0 · 102 + 0 · 101 + 1 · 100 ( = 25 in base 10 )

Da notare: la lunghezza di N in base 2 è la parte intera del suo logaritmo in base 2 più uno:

• maggiore che in base 10 • sostanzialmente proporzionale tramite il logaritmo in base 10 di 2.

Al mondo ci sono 10 categorie di persone: quelli che capiscono la numerazione in base 2 e gli altri.

Una proprietà fondamentale dei naturali: il Principio di induzione (Peano-Dedekind, 1888-89) “Se una proprietà è vera per 0 e si trasmette da ogni naturale n al successore n + 1 (dunque da 0 a 1, da 1 a 2, e così via), allora la proprietà è vera per ogni naturale” Le operazioni in N: addizione + , moltiplicazione ·, sottrazione – e divisione :

Lewis Carroll, Oltre lo specchio “- Sai fare l’addizione? Quanto fa uno più uno più uno più uno più uno più uno più uno più uno? - Non lo so, ho perso il conto.”

Beatles, Come together, “One and one and one is three”

Raymond Queneau, Quaderni del collegio di patafisica

“In tutti i tentativi fatti per provare che 2 + 2 = 4 non si è mai tenuto conto della velocità del vento”

Bertrand Russell, gli effetti di 2 + 2 = 5

Il “costo” delle operazioni

Una convenzione ragionevole: nel calcolo di +, ·, –, : si intende passo elementare, dal costo unitario, ogni singola operazione sulle cifre. Dunque:

8723 + 2734 = 11457 richiede 5 passi

8723 × 734 = 34892 26169 61061 = 6402682 richiede 22 passi

Allora: - il costo di addizione e sottrazione è al più lineare rispetto alla lunghezza dei numeri che si

sommano e sottraggono; - il costo di moltiplicazione e divisione è al più quadratico rispetto alla lunghezza dei numeri

che si moltiplicano o dividono. Costo quadratico ha anche la ricerca di massimo comune divisore e minimo comune multiplo se si usa l’algoritmo di Euclide.

Un numero naturale N > 1 si dice

- primo se gli unici divisori di N sono 1 e N, - composto altrimenti

Numeri primi: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

Teorema fondamentale dell’aritmetica Ogni numero naturale N > 1 si decompone in uno ed un solo modo (a meno dell’ordine dei fattori) nel prodotto di numeri primi.

15 = 3 · 5, 18 = 2 · 32 , 24 = 23 · 3, 32 = 25 , … La moltitudine dei numeri primi…

Quale è il primo più grande?

Se non altro, 2 è l’unico primo pari (“the oddest prime”, Zassenhaus). A parte gli scherzi, “infinite” dimostrazione dell’infinità dei primi.

La più classica: quella di Euclide.

Siano p(0)= 2 < p(1) = 3 < … < p(s) una qualunque collezione finita di numeri primi, vediamo come costruirne uno nuovo. Consideriamo P = p(0) · p(1) · … · p(s) + 1 che è evidentemente > 1 e dunque, per il teorema fondamentale dell'aritmetica, ha qualche fattore primo p. Ma p non coincide con nessuno tra p(0), p(1), …, p(s), altrimenti divide il loro prodotto p(0) · p(1) · … · p(s) e dunque P – p(0) · p(1) · … · p(s) cioè 1. Variazioni sul tema: Kummer (1878), Stieltjes (1890).

Strategia alternativa Costruiamo per ogni naturale s arbitrariamente grande degli interi a(1), a(2), …, a(s) > 1 a due a due primi tra loro. Per ogni i = 1, 2, …, s sia p(i) un fattore primo di a(i). Allora p(1), p(2), …, p(s) sono a due a due distinti. Goldbach (1730): gli infiniti numeri di Fermat

( )n2F n 2 1= +

(n numero naturale) sono a due a due primi tra loro. Vale per ogni n F(n+1) = F(0) · F(1) · … · F(n) + 2 (si prova per induzione su n). Segue che, per m < q, F(m) divide F(q) – 2. Sia allora p un eventuale fattore primo comune di F(m) e F(q), allora p divide anche la differenza 2, dunque p = 2. Ma allora F(m) e F(q) sono pari, mentre ogni numero di Fermat è evidentemente dispari.

La dimostrazione di Hurwitz (1891)

Fissato s, consideriamo

s! + 1, s! · 2 + 1, …, s! · s + 1

che sono a due a due primi tra loro: infatti per 1 = i < j = s, un eventuale fattore primo p di s!· i + 1 e s!· j + 1 divide anche la loro differenza s! (j – i). Ma 0 < j – i < s, quindi p divide in ogni caso s!, di conseguenza ogni suo multiplo, come s!· i, e in definitiva s!· i + 1 – s!· i = 1: ma questo è chiaramente assurdo.

La dimostrazione di Thue (un incastro combinatorio)

Da trovare: per ogni naturale k > 1, almeno k + 1 primi. Sia n = 2 k2. Si verifica:

• 1 + n = 1 + 2 k2 < 22k (confrontare i grafici rispetto a k < 1), • (1 + n)k < (22k)k = 2n (elevare alla k).

Adesso contiamo il numero s dei primi minori o uguali di 2n. Vogliamo mostrare che s > k.

• Notiamo che tutti i numeri interi da 1 a 2n si decompongono in fattori primi con questi s primi, con esponenti che vanno da 0 fino a n, dunque assumono n+1 possibili valori.

• Ricordiamo che questa decomposizione è unica. • Osserviamo che ci sono (n+1)s possibili decomposizioni. • Deduciamo 2n = (n+1)s.

A questo punto, se s = k, si ha

2n = (n+1)s = (n+1)k < 2n, il che è assurdo. Dunque s > k. La dimostrazione di Eulero e l’avvento della teoria analitica dei numeri

Se p è primo, p > 1 quindi 0 < 1/p < 1. Ne segue che la serie geometrica di ragione 1/p converge (per k che va da 0 a 8 ) a

Sk 1/pk = 1/(1–1/p) = p/(p-1). Adesso supponiamo che p(1), … , p(s) siano primi a 2 a 2 distinti. Il prodotto per i= 1, …, s delle somme infinite Sk(i) 1/p(i)k(i) (per k(i) che va da 0 a 8 ) è definito e vale

? i p(i)/(p(i) – 1) (i = 1, … ,s).

Ma questo prodotto eguaglia anche Sm 1/m per m che varia tra i naturali non nulli che si decompongono in fattori primi tra p(1), …, p(s), dunque tra tutti i naturali non nulli se p(1), …, p(s) esauriscono i primi. Ma la serie Sm 1/m diverge; quindi i numeri primi sono infiniti.

La dimostrazione di Washington (1980) e l’uso della teoria algebrica dei numeri Consideriamo l’anello A che estende il dominio di integrità Z degli interi con a = radice di – 5. Si compone di tutti i numeri complessi della forma a + b a con a, b interi. In esso 6 ha due decomposizioni distinte nel prodotto di fattori irriducibili (ovvero non nulli né invertibili, e non esprimibili nel prodotto di fattori tutti non invertibili)

6 = 2 · 3 = (1 – a) · (1 + a). Allora A non è un dominio a fattorizzazione unica e quindi non è neppure un dominio a ideali principali. Ma

• A è in ogni caso un dominio di Dedekind e ha un’infinità di ideali primi,

• ciascun intero primo appartiene ad al più un numero finito di questi ideali. Si conclude che c’è un’infinità di interi primi. La successione dei primi è irregolare e imprevedibile

• Tra 11 e 20 ci sono quattro primi: 11, 13, 17, 19 (e quattro è il numero massimo possibile di primi tra 10 numeri consecutivi = 10, visto che tra essi dobbiamo certamente escludere i numeri pari e i multipli di 5).

• D'altra parte tra 107 e 107 +100 (dunque su 101 numeri consecutivi) solo 2 risultano primi, e cioè 107 + 19 e 107 + 79.

Due primi consecutivi si chiamano gemelli se la loro differenza è 2 (dunque uno è p e l’altro è p+2). “Tra i numeri primi ce ne sono alcuni ancora più speciali. I matematici li chiamano primi gemelli: sono coppie di numeri primi che se ne stanno vicini, anzi quasi vicini, perché tra di loro

vi è sempre un numero pari che gli impedisce di toccarsi per davvero. Numeri come l'11 e il 13, come il 17 e il 19, il 41 e il 43. […] Mattia pensava che lui e Alice erano così, due primi gemelli, soli e perduti, vicini ma non abbastanza per sfiorarsi davvero. A lei non l'aveva mai detto.” (Paolo Giordano, La solitudine dei numeri primi) Esempi: 3 e 5, 5 e 7, 11 e 13, 17 e 19, … Controesempi: 7 e 11, 13 e 17, 19 e 23, 23 e 29, … Non è chiaro quante siano le coppie di primi gemelli (infinite?). E ancora… “Postulato di Bertrand” (1845), poi teorema di Chebyshev (1850): tra un intero positivo e il suo doppio c’è sempre almeno un numero primo.

D’altra parte, per ogni intero positivo s si possono trovare s numeri consecutivi nessuno dei quali è primo. Basta considerare

• (s + 1)! + 2 > 2, divisibile per 2, dunque composto, • (s + 1)! + 3 > 3, divisibile per 3, dunque composto,

… … … • (s + 1)! + s + 1 > s + 1, divisibile per s +1, dunque composto.

I primi nelle progressioni aritmetiche Osserviamo: in N

• solo un primo è pari, cioè della forma 2n con n naturale, • ci sono infiniti primi dispari, cioè della forma 2n + 1 con n naturale.

Il teorema di Dirichlet (1837)

Siano a > 0, b due interi primi tra loro. Allora ci sono infiniti primi nella progressione aritmetica a·n + b, per n naturale. Un caso “facile”: a = 4, b = 3 (equivalentemente b = – 1) In altre parole: ci sono infiniti primi congrui 3 modulo 4.

Basta ripetere l’argomento di Euclide, opportunamente modificato. Siano p(1), …, p(s) primi tra loro distinti e tutti congrui 3 modulo 4. Poniamo

• P = p(1) · … · p(s) + 2 se s è pari e quindi p(1) · … · p(s) = 1 (mod 4), • P = p(1) · … · p(s) + 4 se s è dispari e quindi p(1) · … · p(s) = 3 (mod 4).

In ogni caso P = 3 (mod 4), in particolare dispari. Quindi i suoi fattori primi sono tutti dispari (congrui 1 o 3 modulo 4). Inoltre:

• nessuno di loro si trova tra p(1), …, p(s), altrimenti divide p(1) · … · p(s), dunque 4 o 2, cioè è 2,

• almeno uno di loro è congruo 3 modulo 4, altrimenti P = 1 (mod 4). Un caso molto più complicato: a qualunque, b = 1. In altre parole: ci sono infiniti primi congrui 1 modulo a per ogni a.

Si chiede aiuto alla teoria algebrica dei numeri. In particolare si fa riferimento al polinomio ciclotomico F a(x), quello che ha per radici le radici primitive complesse a-esime dell’unità:

• soddisfano xa – 1 • ma non xd – 1 per d divisore proprio di a.

Si dimostra • F a(x) è un polinomio monico a coefficienti interi, irriducibile in Z[x] e in Q[x], • F a(0) = 1 mentre |F a(x)| > 1 per ogni intero positivo x.

Ciò premesso, supponiamo come nei casi precedenti che p(1), …, p(s) siano primi tra loro distinti e congrui 1 modulo a. Stavolta poniamo

N= a · p(1) · … · p(s).

Allora F a(N) è intero e anzi F a(N) = F a(0) = 1 (mod N). Inoltre |F a(N)| > 1. Sia p un fattore primo di |F a(N)|. Allora p non divide N (altrimenti p divide 1), in particolare p non sta tra p(1), …, p(s) e p non divide a. Ma un risultato di Legendre assicura allora che p = 1 (mod a). La dimostrazione di Dirichlet: usa la teoria analitica dei numeri. Una prova “elementare”: Selberg, 1949.

Curiosità… Siano a, b interi primi tra loro, a > 0.

• Quale è il primo più piccolo tra gli infiniti che stanno nella progressione a·n + b? • Quale è la densità dei primi in questa progressione?

E ancora: • Fissato a, quale è il massimo primo p(a) che è minimo tra i primi di a·n + b al variare di b?

Linnik, 1944: esistono due costanti intere positive M e c tali che, per ogni a abbastanza grande, p(a) < c · aM . Due problemi Input comune: un naturale N = 2

L’output atteso • Primalità: N è primo o composto? • Fattorizzazione: la decomposizione di N in fattori primi (il primo passo: per N composto

dispari, un divisore proprio d di N diverso da 1 e N).

Luca Della Robbia: Euclide e Pitagora (Geometria e Aritmetica)

Un algoritmo elementare per entrambi i casi (noto già agli antichi Greci)

• Si prende 1 < d < N e si divide N per d. • Se la divisione è esatta per qualche d, si deduce che N è composto (e anzi si trova un suo

divisore d diverso da 1 e N) • Se la divisione non è esatta per nessun d, si deduce che N è primo.

Gauss, Disquisitiones Aritmeticae, 1801 (articolo 329) “ Il problema di separare i primi dai composti e di decomporre i secondi nei loro fattori primi è conosciuto essere uno dei più importanti e utili in Matematica. La dignità stessa della scienza sembra richiedere di esplorare ogni possibile mezzo per la soluzione di un problema così elegante e famoso ” Perchè questa esigenza due millenni dopo i Greci? Gauss: “Le tecniche conosciute in precedenza richiederebbero una fatica intollerabile anche per i più instancabili calcolatori.”

Da prevedere per l’algoritmo “elementare”: N – 2 divisioni, una per ogni possibile d = 2, …, N – 1. Ma la lunghezza di N in base 2 (o 10) è all’incirca il suo logaritmo in quella base! Dunque le divisioni richieste per N sono all’incirca (2 o 10) elevato alla lunghezza di N. Possibili scorciatoie

• Basta esplorare 1 d N< ≤ (infatti se N = d ·q con d, q > 1, allora d N≤ oppure d N′ ≤ ). • Se d non funziona, neppure 2d, 3d, ... vanno bene.

Ma i guai restano! Prevedibili fino a N 1− divisioni: una quantità ancora esponenziale rispetto alla lunghezza di N.

Le potenze del 2 Sissa e l’invenzione degli scacchi: come ricompensa

• 1 chicco di grano sul primo quadro della scacchiera • su ogni nuovo quadro, il doppio dei chicchi del precedente.

Apparentemente, una domanda modesta. In realtà • 1 + 2 + 22 + 23 + … + 263 = 264 – 1 chicchi di grano: oltre 18 miliardi di miliardi, quel che

la terra produrrebbe in tre millenni!

Dante, Paradiso, Canto 28 “L’incendio suo seguiva ogni scintilla, ed eran tante che ’l numero loro più che ’l doppiar degli scacchi s’immilla.”

Il Crivello di Eratostene

Moltiplicare è più semplice che dividere (?) Dato l’input N > 1,

• si scrivono i numeri da 2 a N disposti su righe, da 2 a 10, da 11 a 20, … • si considera 2 e si sottolineano tutti i suoi multipli più grandi, • si considera il minimo numero sopravvissuto 3 e si sottolineano i suoi multipli più grandi, • si considera il minimo nuemro sopravvissuto 5 e si sottolineano i suoi multipli più grandi, • si prosegue fino a raggiungere N.

I numeri sopravvissuti (non sottolineati) sono i primi = N: N è primo se è uno di loro.

N = 101: primo o composto?

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

• Gli stessi problemi di tempo.. • Risorse inaccessibili anche di spazio (cioè di memoria)

Ricerca di algoritmi più rapidi e accessibili che eventualmente scindano i due problemi di Primalità e Fattorizzazione

Da notare: per N composto,

• la Primalità richiede di sapere che N è, appunto, composto, • la Fattorizzazione vuole tutta la decomposizione in fattori primi di N, o almeno un divisore

d di N diverso da 1e N. Un intermezzo Input: un naturale N > 1 e un primo p Da chiarire: p divide N? Supponiamo N rappresentato in base 10

N = ak · 10k + ak-1 · 10k-1 + … + a1 · 10 + a0

(dove k e gli ai sono numeri naturali e ak ? 0). Esempi

1. p = 2: N è divisibile per 2 se e solo se lo è a0 2. p = 3: N è divisibile per 3 se e solo se lo è la somma ak + ak-1 + … + a1 + a0 3. p = 5: N è divisibile per 5 se e solo se lo è a0 4. p = 11: N è divisibile per 11 se e solo se lo è la somma (-1)k ak + (-1)k-1 ak-1 + … – a1 + a0

La spiegazione? Si lavora modulo p.

1. p = 2: tutte le potenze di 10 sono pari, cioè congrue 0 modulo 2, dunque N = a0 (mod 2) 2. p = 3: tutte le potenze di 10 sono congrue 1 modulo 3, dunque N = ak + ak-1 + … + a1 + a0

(mod 3) 3. p = 5: tutte le potenze di 10 sono congrue 0 modulo 5, dunque N = a0 (mod 5) 4. p = 11: si nota 10k = (-1)k (mod 11), nel senso che 100 = 1 = + 1 (mod 11), 101 = 10 = -1 (mod

11) e così via, quindi complessivamente N = (-1)k ak + (-1)k-1 ak-1 + … – a1 + a0 (mod 11) Un analogo criterio per altri primi p? Esempio: p = 7 Si ha

100 = 1 (mod 7), 101 = 3 (mod 7), 102 = 9 = 2 (mod 7), 103 = 6 (mod 7), 104 = 4 (mod 7), 105 = 5 (mod 7),

106 = 1 (mod 7), … Complessivamente

N = a0 + 3a1 + 2a2 + 6a3 + 4a4 + 5a5 + a6 + … (mod 7) Quindi N è divisibile per 7 se e solo se lo è a0 + 3a1 + 2a2 + 6a3 + 4a4 + 5a5 + a6 + … Impossibile da ricordare!

Altri esempi • p = 101. Si ha

100 = 1 (mod 101), 101 = 10 (mod 101), 102 = 100 = -1 (mod 101), 103 = -10 (mod 101),

104 = 1 (mod 101), 105 = 10 (mod 101), …

Complessivamente N = a0 + 10a1 – a2 – 10a3 + a4 + 10a5 – a6 + … (mod 101), dunque N è divisibile per 101 se e solo se lo è a0 + 10a1 – a2 – 10a3 + a4 + 10a5 – a6 + …

• Sia ora p una potenza 2n di 2. Per n > 1, p non è primo, ma il principio resta valido. Si nota

allora che p = 2n divide tutte le potenze di 10 con esponente maggiore o uguale a n. Si deduce che N è divisibile per 2n se e solo se lo è an-1 · 10n-1 + … + a1 · 10 + a0. Ad esempio, per controllare se 8763985412317765432 è divisibile per 32 = 25 basta fare riferimento a 65432.

Torniamo a Primalità e Fattorizzazione: possibile separare i due problemi!

Il piccolo teorema di Fermat Se N è primo, allora ogni intero a primo con N soddisfa aN-1 = 1 (mod N). Cenni sulla dimostrazione. Si prova più in generale che, per ogni intero a (primo o no con N) vale aN = a (mod N), cioè N divide aN – a = a · (aN-1 –1). Se dunque N è primo con a, cioè non divide a, segue che N divide aN-1 – 1, cioè appunto aN-1 = 1 (mod N). Dunque è da dimostrare aN = a (mod N) per ogni a. Lecito assumere a = 0. Si procede allora per induzione su a.

• I casi a = 0 e a = 1 sono ovvi. • Supponiamo la tesi vera per a e proviamola per a + 1. Ci basta un minimo di calcolo

combinatorio. Dal teorema binomiale (a + 1)N = aN + 1 (mod N). Dall’ipotesi induttiva (a + 1)N = a + 1 (mod N).

Da notare Se facciamo riferimento alla lunghezza di N, è “rapido” controllare che

• a, N primi tra loro (l’algoritmo di Euclide richiede tempi al più quadratici), • aN-1 = 1 (mod N) (basta una divisione, dunque ancora un tempo quadratico).

C’è poi • un elevamento a potenza a ? aN-1 (mod N).

Ma qui non occorrono eseguire N-2 (troppe!) moltiplicazioni di a per se stesso, basta procedere (rapidamente) con successivi elevamenti al quadrato o moltiplicazioni per a. Esempio. N = 101. Per ogni intero a

a100 = (a50)2 = ((a25)2)2 = (((a12)2 · a)2)2 = = ((((a6)2)2· a)2)2 = (((((a3)2)2)2· a)2)2 =

= (((((a2 · a)2)2)2· a)2)2 si ottiene a partire da 1 con 3 moltiplicazioni per a e 6 elevamenti al quadrato.

Curiosità Sia N > 0 un intero. Vogliamo controllare se N è primo. Possiamo assumere N dispari (se N è pari, la risposta è facile). Fissiamo a primo con N, ad esempio a = 2 (visto che N è dispari). Domanda: se vale aN-1 = 1 (mod N), N è primo? Da notare: la congruenza aN-1 = 1 (mod N) è “rapida” da verificare. La risposta: NO, ci sono numeri N composti che soddisfano aN-1 = 1 (mod N) e perciò sono chiamati pseudoprimi in base a. Un esempio (Sarrus): 341 = 11 · 31 è pseudo primo in base 2 (ma non in base 3). Una nuova domanda: se vale aN-1 = 1 (mod N) per ogni intero a primo con N, N è primo? Da notare: anche se ogni singola congruenza aN-1 = 1 (mod N) è “rapida” da verificare, le congruenze da controllare possono arrivare, per N primo, a N – 1 (troppe rispetto alla lunghezza di N). La risposta: comunque NO, ci sono numero composti (dispari) N che soddisfano aN-1 = 1 (mod N) per ogni intero a primo con N. Sono chiamati pseudoprimi di Carmichael (1912)

Esempi

• 561 = 3 · 11 · 17 (lo pseudoprimo di Carmichael più piccolo) • 1105 = 5 · 13 · 17 • 1729 = 7 · 13 · 19 • Ancora: 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745,

63973, 75361, 101101, …

La caratterizzazione degli pseudoprimi di Carmichael (Korselt) • Sono prodotti di fattori primi distinti (almeno 3) • Se p è un loro fattore primo, allora p – 1 divide N – 1

Infatti • 2, 10, 16 dividono 560 • 4, 12, 16 dividono 1104 • 6, 12, 18 dividono 1728

Una ricetta per costruire pseudoprimi di Carmichael (Chernick, 1939)

• Si prende un intero positivo m • Si calcolano 6m + 1, 12 m + 1, 18 m + 1 • Se tutti e tre sono primi, se ne fa il prodotto: questo è uno pseudoprimo di Carmichael.

Löh e Niebuhr, 1989: uno pseudoprimo di Carmichael con

16142049 cifre e 1101518 fattori primi!

Un risultato sorprendente: Teorema di Alford, Granville, Pomerance (1994) Ci sono infiniti pseudoprimi di Carmichael. La densità degli pseudoprimi di Carmichael Per ogni reale positivo x, poniamo

CN(x) = numero degli pseudoprimi di Carmichael minori o uguali a x. Allora per x abbastanza grande, CN(x) = x2/7.

Granville

Teorema di Wilson

Per ogni intero N > 1, N è primo se e solo se (N – 1)! = – 1 (mod N). Cenni sulla dimostrazione Sia (N – 1)! = – 1 (mod N). Per N composto, sia p un suo fattore primo. Allora 1 < p < N, dunque p divide anche (N – 1 )! quindi 1. Segue che N è primo. Viceversa, sia N primo. Gli N – 1 interi da 1 a N – 1 sono tutti invertibili modulo N. Gli unici inversi di se stessi sono 1 e N – 1, infatti, siccome gli interi modulo N formano un campo, x2 = 1 (mod N) ammette solo due soluzioni modulo N, che sono appunto 1 e N – 1 (ovvero – 1 modulo N). Gli altri N – 3 interi si suddividono in coppie, in cui ogni elemento è l’inverso dell’altro modulo N. Complessivamente, allora, (N – 1)! = – 1 (mod N). Commenti

• Col Teorema di Wilson, si può controllare la primalità di N senza bisogno di considerarne la fattorizzazione.

• La verifica richiede comunque il calcolo di (N – 1)!, dunque N – 2 moltiplicazioni (“troppe” rispetto alla lunghezza di N).

Una generalizzazione di Eulero del piccolo teorema di Fermat

La f di Eulero: per ogni intero positivo N,

f (N) = numero delle classi di resto modulo N di interi primi con N = numero degli interi tra 1 e N primi con N.

Dunque

• f (1) = 1

• per N > 1, f (N) = N – 1 ( = N – 1 se e solo se N è primo). Ancora:

a) se N è la potenza ph di qualche primo p (per h intero positivo), allora f (N) = ph-1 · (p – 1) (infatti ci sono ph interi tra 1 e N, e di questi ph-1 sono multipli di p, ovvero non sono primi con p; ne restano ph – ph-1 = ph-1 · (p – 1);

b) se N = d · q con d, q primi tra loro, f (N) = f (d) · f (q).

Su questa base si organizza il seguente algoritmo per il calcolo di f : per ogni input N intero positivo,

• si decompone N nel prodotto di potenze di fattori primi distinti ph; • queste potenze sono a 2 a 2 prime tra loro, dunque per b) f (N) è il prodotto delle f (ph); • ogni singola f (ph) si calcola con a).

Esempio N = 24. Allora

• 24 = 23 · 3 • f (24) = f (23)· f (3) • f (23) = 22 · (2 – 1) = 4, f (3) = 3 – 1 = 2, quindi f (24) = 4 · 2 = 8.

Essenziale: il ricorso alla decomposizione di N in fattori primi. Il teorema di Eulero Sia N un intero maggiore di 1 (primo o composto). Allora per ogni intero a primo con N vale

af(N) = 1 (mod N). Il collegamento col piccolo teorema di Fermat: ricordare che per N primo f (N) = N – 1. Altri algoritmi di primalità basati sul piccolo teorema di Fermat?

Carl Pomerance: “la congruenza di Fermat è così semplice che è un peccato doverci rinunciare”

Lucas, 1876 Sia a un intero. Supponiamo

(i)a N –1 = 1 (mod N) (in particolare a è primo con N) (ii) N – 1 è il minimo intero positivo con questa proprietà, cioè am = 1 (mod N) non vale più

per 1 = m < N – 1. Allora N è primo. La motivazione: a ha periodo moltiplicativo N – 1 modulo N, dunque ci sono N – 1 interi invertibili modulo N distinti modulo N. Dunque N è primo. Il difetto nella pratica: nei casi peggiori, N congruenze da verificare (“troppe” se riferite alla lunghezza di N).

Lucas 2, 1891 Sia a un intero. Supponiamo

(i)a N –1 = 1 (mod N) (in particolare a è primo con N) (ii) am = 1 (mod N) non vale per nessun divisore proprio m di N – 1.

Allora N è primo. La motivazione: se vale (i), il periodo moltiplicativo di a modulo N è un divisore di N – 1. Il difetto nella pratica: nei casi peggiori si richiede la conoscenza di tutti i divisori di N – 1, dunque la decomposizione di N – 1 in fattori primi. Brillhart, Selfridge, 1967 Sia a un intero. Supponiamo

(i)a N –1 = 1 (mod N) (in particolare a è primo con N) (ii) per ogni divisore primo q di N – 1, non vale a(N – 1)/q = 1 (mod N).

Allora N è primo. La motivazione: al variare di q tra i fattori primi di N – 1, i numeri della forma (N – 1)/q, costituiscono i divisori “massimali” di N – 1. Se vale am = 1 (mod N) per qualche divisore proprio m di N – 1, allora la stessa proprietà si trasmette a un divisore proprio massimale di N – 1 multiplo di m.

Il difetto nella pratica: di nuovo, nei casi peggiori si ha bisogno di conoscere tutti i fattori primi di N – 1. Un'altra elegante caratterizzazione dei primi. Sia N, a due interi, N > 1, a primo con N. Allora N è primo se e solo se i due polinomi xN + a e (x + a)N hanno i coefficienti di ugual grado a 2 a 2 congrui modulo N. La dimostrazione: usa sostanzialmente gli stessi argomenti di quella del piccolo teorema di Fermat. Il difetto: le coppie di coefficienti da confrontare sono N + 1 (troppe!) Meglio far chiarezza sui problemi di primalità e fattorizzazione!

Una parentesi computazionale Un punto da chiarire

• Quali problemi si possono risolvere? • Quali problemi sono “semplici” da risolvere?

Il ruolo del calcolatore nel mondo moderno

Illustri precursori: Leibniz, Dissertatio de arte combinatoria, 1666 “Calculemus!”

“Io chiamo calcolo qualunque notazione che rappresenti il ragionamento, quand’anche non avesse alcun rapporto con i numeri” L’applicazione di modelli matematici al di fuori della matematica, anche nello studio dell’algebra del pensiero Passare “dai ragionamenti complicati ai calcoli semplici, dai vocaboli di significato vago ed incerto a caratteri determinati”

Verso

• una “lingua characteristica” (un linguaggio scientifico universale)

• un “calculus ratiocinator” (un calcolo della ragione)

Si anticipano Intelligenza artificiale e Deduzione automatica.

Dubbio: si può calcolare “tutto”? I teoremi di incompletezza, Gödel , 1931

Sia S una teoria matematica fondata su assiomi e regole di dimostrazione e come tale capace di dedurre i suoi teoremi. Supponiamo che S

(i)tratti dei numeri naturali, della loro addizione e della loro moltiplicazione, (ii) sia coerente (= priva di contraddizioni), (iii) sia accessibile alla mente umana.

Allora esistono affermazioni sui numeri naturali che S non sa né provare né confutare. In certi casi, S non sa neppure autocertificare la propria coerenza. I limiti della ragione anche di fronte ai numeri naturali… e insieme la coscienza di questi limiti.

L’idea: le proposizioni sui numeri diventano numeri Lo strumento: il teorema fondamentale dell’aritmetica Due citazioni (libere)

• L. Kronecker: “i numeri interi sono i soli creati da Dio”

• A. Weil: “i teoremi di incompletezza di Gödel dimostrano l’esistenza di Dio e anche quella del demonio”

Ancora negli anni trenta: difficoltà a risolvere problemi classici di matematica e logica Due esempi famosi

• Il 10° problema di Hilbert: determinare un procedimento per stabilire, per ogni polinomio a coefficienti interi (di qualunque grado, in qualunque numero x di variabili), se questo polinomio ha o no radici intere.

Per intendersi 2x + 4, x2 – 1, x2 + y2 – 1, … 2x + 5, x2 – 2, x2 + y2 + 1, …

sono tutti polinomi a coefficienti interi, ma quelli della prima riga hanno anche radici intere e quelli della seconda no (eppure la differenza tra i primi e i secondi è quasi impalpabile). C’è un algoritmo generale che sa distinguere i primi polinomi dai secondi?

• L’Entscheidungsproblem (il Problema della decisione): determinare un procedimento per

stabilire quali enunciati della logica del 1° ordine sono validi e quali no

Una soluzione positiva: basta produrre un algoritmo che funziona

Una soluzione negativa: bisogna escludere ogni possibile procedimento

Da chiarire preliminarmente: che cosa è un algoritmo?

Meglio: quali sono i problemi che hanno un algoritmo di soluzione (calcolo)? I contributi di Turing, Church, Kleen, Godel, ... (1936)

Il concetto chiave: la Macchina di Turing

• Informalmente: una vecchia macchina da scrivere

• In germe: il primo prototipo di calcolatore moderno (10 anni prima dell’ENIAC di John Von Neumann)

• Formalmente: un programma con semplici istruzioni (stato, lettura) ? (stato, lettura, spostamento)

La Tesi di Church-Turing “Un problema si può calcolare se e solo se c’è una macchina di Turing che lo calcola”

Argomenti a favore

• L’assenza di controesempi • L’equivalenza con altri approcci alla computabilità (il lambda calcolo di Church, la

ricorsività di Godel-Kleene, ... ) • Il proposito dichiarato di simulare il comportamento della mente umana (il modello

dell’impiegato diligente)

In realtà il modello di Turing è • discreto • deterministico.

Oggi nuovi orizzonti, talora alternativi

• nanocomputazione (calcolo in ambienti microscopici) • computazione naturale (il sistema nervoso) • computazione quantistica.

Comunque sulla base della tesi di Turing

• soluzione negativa del Decimo Problema di Hilbert: nessun algoritmo possibile (Matijasevic, 1970, Davis, Putnam, Julia Robinson)

• soluzione negativa dell’ Entscheidungsproblem (Church, 1936) • impossibilità di decidere gli enunciati del primo ordine su addizione e moltiplicazione veri o

falsi tra i numeri naturali (Tarski: si collega al teorema di incompletezza di Godel). In compenso possibile decidere gli enunciati del primo ordine su addizione e moltiplicazione veri o falsi tra i reali, o anche tra i complessi (Tarski, anni ‘40)

Tarski

Ma un teorema devastante Fischer e Rabin, 1970: qualunque algoritmo di decisione per gli enunciati del primo ordine sull’addizione veri o falsi tra i reali (equivalentemente tra i complessi) impiega talora tempo almeno esponenziale nella lunghezza dell’enunciato da esaminare

Possibile in teoria, ma non in pratica! Un esempio dalla Crittografia

• la macchina Enigma, • Turing a Bletchley Park: la necessità di una crittoanalisi rapida!

Del resto lo sappiamo già: tempi esponenziali di attesa sono proibitivamente lunghi! L’attenzione

• non più sui problemi risolubili (in teoria) • ma sui problemi risolubili a costo accessibile nella pratica?

La teoria della complessità computazionale: il costo delle computazioni!

Da chiarire preliminarmente

a) Quale parametro per misurare il “costo”? Tempo? Memoria? Energia? Altro? La risposta più ragionevole (ma non l’unica): il tempo! b) Quale agente di calcolo? Macchine di Turing classiche? Probabilistiche? Interattive? Altro?

La cinquecento o la Ferrari? Una risposta sorprendente ma sensata: la macchina di Turing (nelle varie accezioni).

A questo punto: che significa “tempo rapido”?

Karp

Cook

La Tesi di Edmonds-Cook-Karp (Von Neumann, Rabin, Cobham) A livello di slogan: rapido = polinomiale In termini più rigorosi: un algoritmo opera rapidamente se e solo se opera in tempi al più polinomiali rispetto alla lunghezza dell’input. Si fa riferimento a polinomi di grado positivo a coefficienti interi e coefficiente di grado massimo positivo. Facile da accettare: “esponenziale” significa “lento” Discutibile: (al più) “polinomiale” significa “rapido”

Motivi di perplessità

• 1018 è una stima per largo eccesso del tempo del mondo in secondi dall’inizio a oggi secondo la teoria del Big Bang

• Ci sono polinomi di grado 1018… • Anche 1018 x è un polinomio (di grado 1) …

Quanto rapido è un algoritmo che richiede questi tempi polinomiali di lavoro? La tesi di Edmonds-Cook-Karp: da accettare per pigrizia più che per convinzione, non c’è in teoria una proposta più convincente Comunque… P = classe dei problemi che si risolvono in tempo al più polinomiale rispetto alla lunghezza dell’input.

Una classe non così ampia come si vorrebbe

Qualche esempio

1. Calcolo delle operazioni elementari (addizione, sottrazione, moltiplicazione, divisione tra numeri naturali)

2. Calcolo del massimo comun divisore (algoritmo delle divisioni successive di Euclide, tempo al più quadratico)

3. 2-COL Ricordare: un grafo è una coppia G = (V, E) dove

• V è un insieme non vuoto (l’insieme dei vertici)

• E è una relazione binaria antiriflessiva simmetrica su V (le coppie di E sono i lati del grafo). Si dice che G è 2-colorabile se esiste una funzione c di V in {1, 2} (i due colori) tale che, per v, w vertici opposti dello stesso lato (v, w) in E, c(v) ? c(w) (c si dice allora una 2-colorazione di G). 2-COL Input: un grafo finito G = (V, E). Output: G è o no 2-colorabile?

Un algoritmo: Si sceglie un vertice v e gli si assegna un colore arbitrario, ad esempio 1 (notare che una 2-colorazione di G si preserva per le permutazioni dei colori 1 e 2). I vertici collegati a v da qualche lato di E assumono allora colore 2, quelli adiacenti a quest’ultimi tornano ad avere colore 1… Effetto domino: tempo al più polinomiale

E il problema della primalità? Distinguere i primi dai composti (e i composti dai primi)? Da chiarire (sta in P, ma la prima dimostrazione risale solo al 2002…) Il paradiso dei problemi in P… L’inferno dei problemi fuori di P… Ma anche: un limbo di problemi né manifestamente in P né manifestamente fuori

• 3-COL

Variante di 2-COL con 3 colori 1, 2, 3 (la 3-colorabilità) Non più attuabile un algoritmo con l’effetto domino

Algoritmo di forza bruta (analisi di tutti i casi possibili) - Numero delle possibili 3-colorazioni di di n vertici: 3n (definite a meno di permutazioni dei 3

colori) - Numero delle permutazioni dei 3 colori: 3!=6 Dunque: un numero esponenziale di casi.

In compenso, se una 3-colorazione c esiste - è rapida da suggerire (basta dire c(v) per ogni v in V), - è rapida da controllare.

Come nei quiz televisivi: talora basta un aiutino!

• Fattorizzazione Input: un naturale N > 1 (dispari) Output: la decomposizione di N in fattori primi o almeno, per N composto, un divisore d di N diverso da 1 e da N. L’algoritmo elementare: esponenzialmente lungo In compenso, se N è composto e quindi ammette un divisore d come richiesto, allora d - è rapido da presentare (perché minore di N), - è rapido da controllare (basta una divisione, quella di N per d). Come per 3-COL.

Una generalizzazione NP = classe dei problemi la cui soluzione è rapida da ottenere con un po’ d’aiuto: se la risposta è positiva, c’è una informazione chiave t rapida da presentare col cui aiuto è rapido controllare la risposta. Ovvio: P è contenuto in NP Un problema rapido da risolvere senza bisogno di aiuto resta rapido da risolvere con un po’ di aiuto.

Esempi in NP (ma non manifestamente in P) • 3-COL • Fattorizzazione

P=NP? Uno dei Sette Problemi del Millennio della Matematica, 2000

I più complicati problemi di NP: quelli NP-completi

Un problema S è NP-completo se: • sta in NP • per ogni problema S di NP, c’è un algoritmo che traduce in tempo al più polinomiale istanze

di S in istanze di S e istanze positive di S in istanze positive di S (così che, se c’è un algoritmo che risolve S in tempo al più polinomiale, se ne ottiene uno analogo anche per S combinando quello di S con la procedura di traduzione).

Un esempio: 3COL Invece: non è chiaro se Fattorizzazione è NP-completo

3COL

P

Esempi: 3COL, FATTORIZZAZIONE NP∈

Chiaro: se 3COL P∉ , allora P NP≠

NP

Anche in NP

• Il problema di riconoscere i composti dai primi Input: un naturale N > 1 Output: stabilire se N è composto o no. Come per la fattorizzazione, se N è composto, basta affidarsi a un suo divisore non banale - rapido da presentare (perché minore di N), - rapido da controllare (basta una divisione). Attenzione! - Vedremo che il problema in questione sta addirittura in P. - La procedura non funziona se il problema diventa quello (complementare) di primalità, cioè

riconoscere i primi dai composti: se N è primo, non c’è divisore che possa confermarlo e bisogna scorrere la lista dei numeri naturali da 2 a N – 1 per essere certi che nessuno divide N.

In realtà

• Il problema di primalità (riconoscere i primi dai composti) sta in NP.

Si fa riferimento al criterio di primalità di Brillhart e Selfridge: per testimoniare che un dato input N > 1 è primo servono - un intero a primo con N, compreso tra 1 e N (quindi rapido da presentare); - il complesso dei divisori primi q di N – 1 (ciascuno rapido da presentare; per ognuno di loro

si controlla rapidamente che la congruenza a(N – 1)/q = 1 (mod N) non vale); - non basta! Ci vuole la certificazione che ciascun q è primo (lo stesso problema che per N).

Per fortuna il numero h dei divisori primi di N soddisfa certamente 2h = N, da cui segue che h = log2 N. Allo stesso modo si vede che il numero di iterazioni del procedimento è lineare nella lunghezza di N.

Conclusione: tra teoremi di Gödel, P e NP, ci sono argomenti sufficienti per ribadire la complessità dei numeri naturali in generale, e dei numeri primi in particolare.

I misteri dei primi…

Intanto, qualche preliminare. Residui q uadratici. Per p primo dispari

• p – 1 è pari, • p – 1 classi modulo p di interi primi con p.

Come si distribuiscono tra loro i quadrati? Esattamente a metà!

• (p – 1)/2 sono quadrati residui quadratici modulo p • (p – 1)/2 non sono quadrati non residui quadratici modulo p

Da confrontare con N (dove i quadrati sono molto più rari)

Cenni sulla dimostrazione I p – 1 interi modulo p primi con p sono le potenze di uno opportuno g di loro

1, g, g2, …, gp – 2 Dunque, per ogni i < p – 1, gi è un quadrato se e solo se i è pari.

Come trovare g (Gauss, Disquisitiones Arithmeticae, articoli 73, 74)

• Si sceglie un intero a con 1 < a < p e si calcolano le potenze con esponente positivo a, a2, a3, … di a modulo p fino ad incontrare la prima at = 1 (mod p). Se t = p – 1, allora possiamo porre g = a.

• Altrimenti si prende un intero b, 1 < b < p, non congruo modulo p a nessuna delle potenze di a. Si procede come per a determinando il minimo intero positivo s per cui bs = 1 (mod p). Se s = p – 1, possiamo porre g = b.

• In ogni caso s non divide t altrimenti bt = 1 (mod p) e b finisce con l’essere una delle t potenze distinte di a modulo p (eventualità già esclusa): infatti il polinomio xt –1 ammette al più t radici distinte modulo p, e le potenze di a modulo p esauriscono già queste radici.

• Se dunque d denota il minimo comune multiplo di t e s, d = t' · s' dove t' divide t, s' divide s e t', s' sono primi tra loro. Si pone

a' = at/t' (mod p), b' = bs/s' (mod p), c = a' · b' e si osserva che c ha periodo d = t' · s' modulo p. Se quindi d = p – 1, si può scegliere g = c.

• Altrimenti si continua il procedimento. Il meccanismo deve interrompersi dopo al più un numero finito di passi. Gauss illustra l’algoritmo con un esempio: per p = 73, trova g = 5.

Il simbolo di Legendre: per ogni intero a, (a/p) è • 0 se a non è primo con p (cioè a = 0 (mod p)), • 1 se a è residuo quadratico modulo p, • – 1 se a è non residuo quadratico modulo p.

Un altro teorema di Eulero Per p primo dispari e a intero, (a/p) = a(p – 1)/2 (mod p). Attenzione! Per p composto, la congruenza è falsa per almeno metà degli interi a modulo p primi con p. Un calcolo rapido del simbolo di Legendre (a prescindere dal teorema di Eulero) Si basa su due semplici osservazioni…

1) (a/p) = (r/p) dove r è il resto della divisione di a per p (dunque, a meno di una divisione si può assumere 0 = r < p)

2) (a · b /p) = (a/p) · (b/p) (dal teorema di Eulero) … e su due teoremi impegnativi

3) (2/p) = 1 se e solo se p = ± 1 (mod 8) (dunque (2/p) = – 1 per p = ± 3 (mod 8)) 4) (Legge di reciprocità quadratica) per q primo dispari, (q/p) = (p/q) se e solo se p = 1

(mod 4) oppure q = 1 (mod 4) (dunque (q/p) = – (p/q) se e solo se p = q = 3 (mod 4)).

Esempi • (2/3) = (2/5) = – 1, (2/7) = 1 • (3/5) = (5/3) [= (2/3) = 1], (3/7) = – (7/3) [= – (1/3) = – 1]

La legge di reciprocità quadratica

• enunciata da Eulero, 1783 • accostata da Legendre, 1785 • dimostrata da Gauss diciannovenne, 1796 – e Gauss nel corso della sua vita ne diede 8

dimostrazioni differenti!)

Un possibile algoritmo di calcolo di (a/p) • si sostituisce a col suo resto r nella divisione per p (costo: quello della divisione) • si decompone r in fattori primi, rappresentando (r/p) come prodotto di fattori (2/p) e (q/p)

con q < p primo dispari • si usano 3 per (2 / p) e 4 per i vari ( q/ p) con q dispari.

La decomposizione di r in fattori primi: evitabile! Radici quadrate modulo p. Per p primo dispari, ogni quadrato modulo p primo con p ha esattamente 2 radici quadrate modulo p:

se x2 = a2 (mod p), allora x = ± a (mod p), inoltre a e –a non sono congrui modulo p. Infatti, se il primo p divide x2 – a2 = (x –a) · (x + a), allora p divide x – a oppure x + a. Inoltre p non può dividere a – (– a) = 2 · a perché è primo tanto con 2 quanto con a. In particolare

se x2 = 1 (mod p), allora x = ± 1 (mod p), inoltre 1 e –1 non sono congrui modulo p. Non sempre vero per p composto! Ad esempio

x2 = 1 (mod 8) per x = ± 1 (mod 8) ma anche per x = ± 3 (mod 8).

I primi di Fermat

Le potenze di 2 1, 2, 4, 8, 16, 32, 64, …, 2m , … I loro successori 2, 3, 5, 9, 17, 33, 65, …, 2m + 1, … Osserviamo: se m ha un fattore dispari d > 1, cioè se m non è potenza di n, allora 2m + 1 è composto. Supponiamo infatti m = q · d e notiamo

2m + 1 = 2q·d + 1 = (2q )d + 1d = (2q + 1) · …

Esempi 23 + 1 = 9 è composto, 25 + 1 = 33 è composto, 26 + 1 = 65 è composto, … Invece

• 022 1 3+ = è primo

• 122 1 5+ = è primo

• 222 1 17+ = è primo

• 322 1 257+ = è primo

• 422 1 65537+ = è primo.

Poniamo: per ogni naturale n ( ) n2F n 2 1= + l’n-mo numero di Fermat. Notare: i numeri di Fermat sono tutti dispari. Una congettura di Fermat: tutti i numeri di Fermat sono primi.

La smentita di Eulero ( ) 52F 5 2 1 641 6700417= + = ⋅ è composto!

La strategia di Eulero 1) Caratterizzazione dei possibili divisori primi di F(n) per n = 5: hanno la forma h · 2n+1 + 1

(risultato migliorato da Lucas k · 2n+2 + 1) 2) Applicazione a n = 5 641 = 5 · 27 + 1 = 10 · 26 + 1

La dimostrazione di 1) Sia p un fattore primo di F(n). Tanto per cominciare, p è dispari. Inoltre

2 alla 2 alla n = – 1 (mod p) quindi

2 alla 2 alla n + 1 = 1 (mod p) in altre parole il periodo moltiplicativo di 2 modulo p è 2n+1 . Dal piccolo teorema di Fermat segue che 2n+1 divide p – 1. Siccome n = 5, 8 divide p – 1. Segue che il simbolo di Legendre (2/p) vale 1. Dal teorema di Eulero sul simbolo di Legendre

2(p-1)/2 = (2/p) = 1 (mod p). Quindi il periodo 2n+1 di n modulo p divide anche (p – 1)/2. Perciò p – 1 = k · 2n+2 per qualche k e di conseguenza p = k · 2n+2 + 1.

Altre proprietà dei numeri di Fermat Il test di Pepin, 1877 Sia n > 1. Allora F(n) è primo se e solo se 3(F(n) – 1)/2 = – 1 (mod F(n)). Cenni sulla dimostrazione Se vale 3(F(n) – 1)/2 = – 1 (mod F(n)), quadrando si deduce 3F(n) – 1 = 1 (mod F(n)) e anzi che il periodo di 3 modulo F(n) è proprio F(n) – 1. Dai test di Lucas segue che F(n) è primo. Viceversa, sia F(n) primo, allora vale il teorema di Eulero

3(F(n) – 1)/2 = (3/F(n)) (mod F(n)). Dalla legge di reciprocità quadratica, (3/F(n)) = (F(n) / 3). Per n > 1 è facile osservare che F(n) = 2 (mod 3) [si prova infatti per induzione su n che F(n) – 1 = 1 (mod 3)], quindi (F(n) /3 ) = (2/3) = – 1. In conclusione 3(F(n) – 1)/2 = – 1 (mod F(n)). Un test

- non semplice da controllare (richiede da calcolare un triplo esponenziale) - tuttavia utile nella pratica (ma per F(n) composto non indica nessun fattore di F(n))

Ancora

I numeri di Fermat sono a 2 a 2 primi tra loro (la proprietà che abbiamo già usato per dimostrare l’infinità dei primi) Addirittura, per ogni n, F(n) = F(0) · F(1) · … · F(n – 1) + 2 Cenni sulla dimostrazione Per induzione su n > 0. Il caso n = 1 è evidente, F(1) = 5 = 3 + 2 = F(0) + 2. Supponiamo la tesi vera per n e proviamola per n + 1. Infatti F(0) · F(1) · … · F(n – 1) · F(n) + 2 = (F(n) – 2) · F(n) + 2 = F(n)2 – 2· F(n) + 2 che, usando la definizione di F(n), si dimostra facilmente eguagliare F(n+1). Dunque, se m < n, un fattore primo di F(m) e F(n) è anche divisore di 2, cioè coincide con 2. Ma ogni numero di Fermat è dispari.

I numeri di Fermat: primi o composti? Aggiornamenti dal sito http://www.prothsearch.net/fermat.html

News Flash! On October 9, 2009 Takahiro Nohara discovered another new factor

of a Fermat number: 1814649 · 212827 + 1 divides F12825. This is his sixth factor so far.

The other most recently discovered factors

Date Divisibility Discoverer

Jul 18, 2009 8962167624028624126082526703 · 222 + 1

divides F19 David Bessell (GIMPS)

Apr 18, 2009 71007 · 249490 + 1 divides F49488 Takahiro Nohara

Mar 31, 2009 659 · 2617815 + 1 divides F617813 Eric Embling (PG)

Prime Fermat numbers

F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537

Completely factored Fermat numbers, F(m) = k · 2n + 1

m k n Year Discoverer

5 5 7 1732 L. Euler

52347 7 1732 L. Euler

6 1071 8 1855 T. Clausen; F. Landry 1880

262814145745 8 1855 T. Clausen; F. Landry & H. Le Lasseur 1880

7 116503103764643 9 1970 M. A. Morrison & J. Brillhart

11141971095088142685 9 1970 M. A. Morrison & J. Brillhart

8 604944512477 11 1980 R. P. Brent & J. M. Pollard

[59 digits] 11 1980 R. P. Brent & J. M. Pollard

9 37 16 1903 A. E. Western

[46 digits] 11 1990 A. K. Lenstra, M. S. Manasse & a larger team

[96 digits] 11 1990 A. K. Lenstra, M. S. Manasse & a larger team

10 11131 12 1953 J. L. Selfridge

395937 14 1962 J. Brillhart

[37 digits] 12 1995 R. P. Brent

[248 digits] 13 1995 R. P. Brent

11 39 13 1899 A. Cunningham

119 13 1899 A. Cunningham

10253207784531279 14 1988 R. P. Brent

434673084282938711 13 1988 R. P. Brent

[560 digits] 13 1988 R. P. Brent & F. Morain

46 digit k = 3640431067210880961102244011816628378312190597

37 digit k = 1137640572563481089664199400165229051

Complete factorizations in standard notation

F5 = 641 · 6700417

F6 = 274177 · 67280421310721

F7 = 59649589127497217 · 5704689200685129054721

F8 = 1238926361552897 · P62

F9 = 2424833 · 7455602825647884208337395736200454918783366342657 · P99

F10 = 45592577 · 6487031809 · 4659775785220018543264560743076778192897 · P252

F11 = 319489 · 974849 · 167988556341760475137 · 3560841906445833920513 · P564

Factorizations known to be incomplete

m k n Year Discoverer

12 7 14 1877 I. M. Pervushin; E. Lucas

397 16 1903 A. E. Western

973 16 1903 A. E. Western

11613415 14 1974 J. C. Hallyburton & J. Brillhart

76668221077 14 1986 R. Baillie

13 41365885 16 1974 J. C. Hallyburton & J. Brillhart

20323554055421 17 1991 R. E. Crandall

6872386635861 19 1991 R. E. Crandall

609485665932753836099 19 1995 R. P. Brent

15 579 21 1925 M. Kraitchik

17753925353 17 1987 G. B. Gostin

1287603889690528658928101555 17 1997 R. E. Crandall & C. van Halewyn

16 1575 19 1953 J. L. Selfridge

180227048850079840107 20 1996 R. E. Crandall & K. Dilcher

17 59251857 19 1978 G. B. Gostin

18 13 20 1903 A. E. Western (Prime: P. Seelhoff 1886)

9688698137266697 23 1999 R. E. Crandall, R. J. McIntosh & C. Tardif

19 33629 21 1962 H. Riesel

308385 21 1963 C. P. Wrathall

8962167624028624126082526703 22 2009 D. Bessell & G. F. Woltman

21 534689 23 1963 C. P. Wrathall

23 5 25 1878 I. M. Pervushin

Incomplete factorizations in standard notation

F12 = 114689 · 26017793 · 63766529 · 190274191361 · 1256132134125569 · C1187

F13 = 2710954639361 · 2663848877152141313 · 3603109844542291969 ·

319546020820551643220672513 · C2391

F15 = 1214251009 · 2327042503868417 · 168768817029516972383024127016961 · C9808

F16 = 825753601 · 188981757975021318420037633 · C19694

F17 = 31065037602817 · C39444

F18 = 13631489 · 81274690703860512587777 · C78884

F19 = 70525124609 · 646730219521 · 37590055514133754286524446080499713 · C157770

F21 = 4485296422913 · C631294

F23 = 167772161 · C2525215

Problemi aperti

1. Quanti sono i primi di Fermat? Infiniti (Eisenstein 1844)? 2. Quanti sono i composti di Fermat? Infiniti?

Un teorema famoso (Gauss, Disquisitiones Arithmeticae, articoli 365, 366) Sia N un intero = 3. Allora è possibile costruire con riga e compasso un poligono regolare di N lati se e solo se N = 2h · p(0) · p(1) · … · p(r) con h, r numeri naturali, p(0), p(1), …, p(r) primi di Fermat tra loro distinti.

Dunque

• la costruzione è possibile per N = 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, … • … ma non per N = 7, 9, 11, 13, 18, 19, 21, 22, 23, 25, …

I primi di Mersenne

Le potenze di 2 1, 2, 4, 8, 16, 32, 64, …, 2m , … I loro predecessori 0, 1, 3, 7, 15, 31, 63, …, 2m – 1, … Osserviamo: se m è composto, allora 2m – 1 è composto. Supponiamo infatti m = q · d con 1< q, d < m e notiamo

2m – 1 = 2q·d – 1 = (2q )d – 1d = (2q – 1) · … Esempi: 24 – 1 = 15 è composto, 26 – 1 = 63 è composto, … Tuttavia: se m è primo, non è detto che 2m – 1 lo sia. Esempio: m = 11 è primo, 211 – 1 = 2047 = 23 · 89 no (già noto a Mersenne). Per ogni intero m > 1, poniamo M(m) = 2m – 1 m-mo numero di Mersenne. I primi di Mersenne secondo Mersenne (1640) M(m) con m = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 Una lista con

• errori (per m = 67, 257 M(m) è composto), • omissioni (m = 61, 89, 107).

Un criterio utile Un divisore n di M(m) (per m primo) deve soddisfare n = ± 1 (mod 8), n = 1 (mod m). Cenni sulla dimostrazione Possiamo supporre m > 1, n primo. L’ipotesi che n divide M(m) si traduce scrivendo 2m = 1 (mod n). Inoltre m è il minimo naturale con questo proprietà perché m è primo. Per il piccolo teorema di Fermat, siccome anche n è primo, m divide n – 1, ovvero

n = 1 (mod m). In dettaglio n – 1 = k · m per qualche k = 2·h pari (m è dispari mentre n – 1 è pari perché n come divisore di M(m) è dispari). Allora

(2/n) = 2(n – 1)/2 = 2h ·m = (2m)h = 1 (mod n).

Segue n = ± 1 (mod 8).

Nuovi record tra i primi di Mersenne

• M(13), Eulero, 1722 • M(127), Lucas, 1876 • M (11213), Gillies, 1963 • M(216091), Slowinski, 1985

Un’accelerazione negli ultimi anni: oggi 47 primi di Mersenne noti Gli ultimi record: scoperti grazie al software open source GIMPS (Great Internet Mersenne Primes Search).

Dal sito http://www.mersenne.org

Table of Known Mersenne Primes Let M(p) = 2p-1 and P(p) = 2p-1(2p-1). The list of all known primes p for which M(p) is a Mersenne prime (therefore P(p) is a perfect number) follows:

## p (exponent)

digits in Mp

digits in Pp

year discoverer notes

1 2 1 1 ---- ----

2 3 1 2 ---- ----

3 5 2 3 ---- ----

4 7 3 4 ---- ----

5 13 4 8 1456 anonymous

6 17 6 10 1588 Cataldi

7 19 6 12 1588 Cataldi

8 31 10 19 1772 Euler

9 61 19 37 1883 Pervushin

10 89 27 54 1911 Powers

11 107 33 65 1914 Powers note

12 127 39 77 1876 Lucas

13 521 157 314 1952 Robinson

14 607 183 366 1952 Robinson

15 1279 386 770 1952 Robinson

16 2203 664 1327 1952 Robinson

17 2281 687 1373 1952 Robinson

18 3217 969 1937 1957 Riesel

19 4253 1281 2561 1961 Hurwitz

20 4423 1332 2663 1961 Hurwitz

21 9689 2917 5834 1963 Gillies

22 9941 2993 5985 1963 Gillies

23 11213 3376 6751 1963 Gillies

24 19937 6002 12003 1971 Tuckerman [Tuckerman71]

25 21701 6533 13066 1978 Noll & Nickel [NN80]

26 23209 6987 13973 1979 Noll "

27 44497 13395 26790 1979 Nelson & Slowinski [Slowinski79]

28 86243 25962 51924 1982 Slowinski [Ewing83]

29 110503 33265 66530 1988 Colquitt & Welsh [CW91]

30 132049 39751 79502 1983 Slowinski

31 216091 65050 130100 1985 Slowinski

32 756839 227832 455663 1992 Slowinski & Gage et al. (web page)

33 859433 258716 517430 1994 Slowinski & Gage

34 1257787 378632 757263 1996 Slowinski & Gage (web page)

35 1398269 420921 841842 1996 Armengaud, Woltman, et al. (GIMPS) (web page)

36 2976221 895932 1791864 1997 Spence, Woltman, et al. (GIMPS)

(web page)

37 3021377 909526 1819050 1998 Clarkson, Woltman, Kurowski et al. (GIMPS, PrimeNet) (web page)

38 6972593 2098960 4197919 1999 Hajratwala, Woltman, Kurowski et al. (GIMPS, PrimeNet) (web page)

39 13466917 4053946 8107892 2001 Cameron, Woltman, Kurowski et al. (GIMPS, PrimeNet)

(web page)

?? 20996011 6320430 12640858 2003 Shafer, Woltman, Kurowski et al. (GIMPS, PrimeNet) (web page)

?? 24036583 7235733 14471465 2004 Findley, Woltman, Kurowski et al. (GIMPS, PrimeNet)

(web page)

?? 25964951 7816230 15632458 2005 Nowak, Woltman, Kurowski et al. (GIMPS, PrimeNet) (web page)

?? 30402457 9152052 18304103 2005 Cooper, Boone, Woltman, Kurowski et al. (GIMPS, PrimeNet)

(web page)

?? 32582657 9808358 19616714 2006 Cooper, Boone, Woltman, Kurowski et al. (GIMPS, PrimeNet) (web page)

?? 37156667 11185272 22370543 2008 Elvenich, Woltman, Kurowski et al. (GIMPS, PrimeNet)

(web page)

?? 42643801 12837064 25674127

2009 Strindmo, Woltman, Kurowski et al. (GIMPS, PrimeNet) (web page)

?? 43112609 12978189 25956377 2008 Smith, Woltman, Kurowski et al. (GIMPS, PrimeNet)

(web page

Un collegamento intrigante Un numero naturale N si dice perfetto se coincide con la somma dei suoi divisori più piccoli. Il tutto è la somma delle parti Esempi 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14, 496, 8128, … Controesempi

• Ogni numero primo (la somma dei divisori più piccoli è 1), 4 > 1 + 2, … • 12 < 1 + 2 + 3 + 4 + 6

Il caso del 6: S. Agostino

La genesi alla lettera

“In un numero perfetto di giorni, cioè in 6, Dio completò le opere fatte da lui” La città di Dio “Mediante il 6 è stata indicata la perfezione del creato” Numeri perfetti e primi di Mersenne Per ogni intero m > 1, M(m) = 2m – 1 è primo se e solo se M(m) · 2m–1 = (2m – 1) ·2m –1 è perfetto (pari).

(? ) Euclide Supponiamo 2m – 1 primo, allora i divisori di (2m – 1) ·2m –1 [compreso (2m – 1) ·2m –1] sono

• 1, 2, …, 2m – 1 , • 2m – 1, (2m – 1) ·2 , …, (2m – 1) ·2m –1

La loro somma è (1 + 2 + … + 2m – 1) ·(1 + 2m – 1) = (2m – 1) ·2m . Sottraendo (2m – 1) ·2m –1 (che è

la metà) si ottiene nuovamente (2m – 1) ·2m –1, come promesso. (? ) Eulero. Esempi

a) Per m = 2 e M(m) = 3, si ottiene 3 · 2 = 6 b) Per m = 3 e M(m) = 7, si ottiene 7 · 4 = 28 c) Per m = 5 e M(m) = 31, si ottiene 31 · 16 = 496 d) Per m = 7 e M(m) = 127, si ottiene 127 · 64 = 8128 e) Per m = 4 e M(m) = 15 (che non è primo), si ottiene 15 · 8 = 120 (che non è perfetto).

Da chiarire

• Quanti sono i numeri perfetti pari? Tanti quanti i primi di Mersenne • Esistono numeri perfetti dispari?

L’ultimo teorema di Fermat L’antefatto: l’equazione di Pitagora

x2 + y2 = z2 Omogenea di grado 2, coefficienti interi

Radici intere (a, b, c) (con a2 + b2 = c2 )

• banali: a = 0, b = ± c oppure b = 0, a = ± c • non banali (terne pitagoriche) i) siccome l’equazione è omogenea, se (a, b, c) è una soluzione intera, anche (ka, kb, kc) lo

è per ogni intero k diverso da 0 ii) una classificazione per a, b, c primi tra loro

a = 2r, b = r2 - s2, c = r2 + s2 con r > s > 0 interi primi tra loro e di parità opposta. Esempi - per r = 2 e s = 1, a = 4, b = 3, c = 5 - per r = 3 e s = 2, a = 12, b = 5, c = 13 - per r = 4 e s = 1, a = 8, b = 15, c = 17

Fermat, 1637-38, sul bordo di una pagina di un trattato di Diofanto “Cubum autem in duos cubos, et quadratoquadratum in duos quadratoquadratos, et nullam in infinitum ultra secondam potestatem in duos ejusdem nominis fas est dividere.Cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.”

“E’ impossibile suddividere una potenza cubica in cui potenze cubiche, e una potenza quarta in due potenze quarte e, in generale, ciascuna delle infinite potenze superiori alla seconda in due dello stesso grado. Della qual cosa ho trovato una dimostrazione meravigliosa. Ma il margine di questa pagina è troppo esiguo per contenerla.” L’equazione di Fermat

xn + yn = zn per n > 2 intero.

L’ultimo teorema di Fermat: nessuna soluzione (a, b, c) intera non banale!

Ultimo? Teorema?

J. L. Borges Abejacàn il Bojari, ucciso nel suo labirinto “Il teorema che Fermat non scrisse in margine a una pagina di Diofanto” L’ombra “Il teorema perduto di Fermat”

La prima dimostrazione: Andrew Wiles, 1994

Basta: n = 4 e n = p > 2 primo Infatti, per n = d · q con 1 < d, q < n, una soluzione non banale per n ne determina una per q (e d):

an + bn = cn con a, b, c non nulli implica (ad)q + (bd)q = (cd)q con ad, bd, cd non nulli.

n = 4: Fermat, il metodo della cascata

n = 3: Eulero, 1770 (il ruolo della teoria algebrica dei numeri)

• ci si allarga a Z[?(3)] con ?(3) = cos 2p/3 + i sen 2p/3 radice primitiva terza dell’unità, • si osserva che x3 + y3 si decompone in fattori irriducibili come

(x + y) · (x2 – x·y + y2) su Z ma come

(x + y) ·(x + ?(3)·y)·(x + ?(3)2 ·y) su Z[?(3)] dove x + y, x + ?(3)·y, x + ?(3)2 ·y sono a due a due “primi tra loro”,

• si deduce che, se (x + y) ·(x + ?(3)·y)·(x + ?(3)2 ·y) è un cubo z3, allora x + y, x + ?(3)·y, x + ?(3)2 ·y singolarmente sono dei cubi,

• si sfrutta il metodo della cascata.

Primi di Germain Sophie Germain

- una donna appassionata di matematica - si spaccia per uomo (Mr. Leblanc) per comunicare con Gauss - un posto a Gottingen? - una morte prematura (1776-1831)

1823: dimostra un caso particolare dell’ultimo teorema di Fermat per primi p tali che 2p + 1 è ancora primo Notevole Un approccio uniforme, valido non solo per un particolare esponente n, ma per una classe di esponenti. Oggi: si dice primo di Germain ogni primo p tale che 2p + 1 è ancora primo Esempi 3, 5, 11, 23, … Controesempi 7, 13, 17, 19, …

Curiosità (Dubner) • p = 8069496435 · 105072 + 1 • p = 394939394939 (2p + 1 = 789878789879)

Un problema aperto Quanti sono i primi di Germain? Infiniti? In compenso Ci sono infiniti primi che non sono di Germain (da approfondire) Dal sito http://primes.utm.edu/top20

Record Primes of this Type

rank Prime digits who when Comment

1 648621027630345 · 2253824-1 76424 x24 Nov 2009 Sophie Germain (p)

2 620366307356565 · 2253824-1 76424 x24 Nov 2009 Sophie Germain (p)

3 607095 · 2176311-1 53081 L983 Sep 2009 Sophie Germain (p)

4 48047305725 · 2172403-1 51910 L99 Jan 2007 Sophie Germain (p)

5 137211941292195 · 2171960-1 51780 x24 May 2006 Sophie Germain (p)

6 33759183 · 2123458-1 37173 L527 Jun 2009 Sophie Germain (p)

7 7068555 · 2121301-1 36523 L100 Jan 2005 Sophie Germain (p)

8 2540041185 · 2114729-1 34547 g294 Jan 2003 Sophie Germain (p)

9 1124044292325 · 2107999-1 32523 L99 Dec 2006 Sophie Germain (p)

10 112886032245 · 2 108000-1 32523 L99 Dec 2006 Sophie Germain (p)

11 38588805195 · 2100002-1 30115 L95 Dec 2009 Sophie Germain (p)

12 15744710163 · 2100002-1 30114 L95 Dec 2009 Sophie Germain (p)

13 35909079387 · 2100000-1 30114 L95 Dec 2009 Sophie Germain (p)

14 18912879 · 298395-1 29628 p94 Nov 2002 Sophie Germain (p)

15 3364553235 · 288888-1 26768 L652 Jan 2009 Sophie Germain (p)

16 10495740081 · 283125-1 25034 L99 Feb 2006 Sophie Germain (p)

17 61078155 · 282002-1 24693 L99 Feb 2006 Sophie Germain (p)

18 1213822389 · 281131-1 24432 g250 Aug 2002 Sophie Germain (p)

19 64670473 · 274146+1 22328 L446 Jan 2009 Sophie Germain (p)

20 232197 · 273457-1 22119 L983 Sep 2009 Sophie Germain (p)

Visto che ci siamo Primi gemelli Ricordiamo: due primi si dicono gemelli se uno è p, l’altro p + 2. Una caratterizzazione notevole (Clement, 1949) Per p > 1, p e p+2 formano una coppia di primi gemelli se e solo se 4 ((p – 1)! + 1) = – p (mod p·(p+2)).

Un problema aperto Quanti sono i primi gemelli? Infiniti? In compenso Ci sono infiniti primi p per cui p + 2 non è primo (da approfondire) Dal sito http://primes.utm.edu/top20

Record Primes of this Type

rank prime digits who when comment

1 65516468355 · 2333333-1 100355 L923 Aug 2009 Twin (p)

2 2003663613 · 2195000-1 58711 L202 Jan 2007 Twin (p)

3 194772106074315 · 2171960-1 51780 x24 Jun 2007 Twin (p)

4 100314512544015 · 2171960-1 51780 x24 Jun 2006 Twin (p)

5 16869987339975 · 2 171960-1 51779 x24 Sep 2005 Twin (p)

6 33218925 · 2169690-1 51090 g259 Sep 2002 Twin (p)

7 307259241 · 2115599-1 34808 g336 Jan 2009 Twin (p)

8 60194061 · 2114689-1 34533 g294 Nov 2002 Twin (p)

9 108615 · 2110342-1 33222 L113 Jun 2008 Twin (p)

10 1765199373 · 2107520-1 32376 g182 Oct 2002 Twin (p)

11 318032361 · 2107001-1 32220 p100 May 2001 Twin (p)

12 4501763715 · 2100006-1 30115 L95 Dec 2009 Twin (p)

13 34776437961 · 2100001-1 30114 L95 Dec 2009 Twin (p)

14 156733989 · 2100007-1 30114 L95 Dec 2008 Twin (p)

15 1046619117 · 2100000-1 30113 L467 Oct 2007 Twin (p)

16 1807318575 · 298305-1 29603 g216 Mar 2001 Twin (p)

17 744678855 · 295000-1 28607 L922 Aug 2009 Twin (p)

18 23321624 · 353005-1 25298 p263 Dec 2009 Twin (p)

19 1035928263 · 283200-1 25055 p252 Nov 2009 Twin (p)

20 7473214125 · 283125-1 25033 L99 Feb 2006 Twin (p)

Torniamo all’ultimo teorema di Fermat

Primi regolari (Kummer) 1847, 1 marzo, Parigi, Académie des Sciences

• Gabriel Lamé annuncia una dimostrazione dell’ultimo teorema di Fermat. Si generalizza la prova di Eulero a ogni primo p > 2. Si lavora in Z[?(p)] (con ?(p)] = cos 2p/p + i sen 2p/p radice primitiva p-ma dell’unità) come se Z[?(p)] fosse un “dominio a ideali principali” e come tale un “dominio a fattorizzazione unica”.

• Dubbi di Liouville, Cauchy

1847, 24 maggio

• Ernst Kummer segnala per lettera un errore nella prova di Lamé: non è detto che Z[?(p)] sia un “dominio a ideali principali”.

• La condizione chiave perché la dimostrazione funzioni: p regolare.

Un primo p si dice regolare se, per ogni ideale I di Z[?(p)], se Ip è principale, anche I lo è. Il risultato di Kummer L’ultimo teorema di Fermat vale per ogni primo regolare p. Esempi di primi non regolari (Kummer) 37, 59, 67 (gli unici minori di 100), poi 101, 103, 131, 149, 157 Classificati tutti i primi regolari fino a 4 milioni Un record 8388019 (Buhler, Crandall, Sompolski 1991) Un problema aperto (Kummer) Quanti sono i primi regolari? Infiniti? In compenso (Jensen, 1915) Ci sono infiniti primi non regolari.

La congettura di Goldbach

1742

• C. Goldbach, lettera a Eulero: ogni numero naturale n = 6 è la somma di 3 primi • L. Eulero, risposta a Goldbach: equivalente provare che C. Goldbach, ogni numero pari m =

4 è la somma di 2 primi Infatti…

• Supponiamo che ogni numero pari m = 4 sia la somma di primi. Sia n un numero naturale = 6. Se n è pari, n = m + 2 con m pari, m = 4. Se n è dispari, n = m + 3 con m pari, m = 4. Per ipotesi m è comunque la somma di 2 primi p e q. Ma allora n è p + q + 2 nel primo caso e p + q + 3 nel secondo. Comunque n è la somma di 3 primi.

• Viceversa, supponiamo che ogni naturale n = 6 sia la somma di 3 primi. Sia m pari, m = 4. Allora m + 2 è ancora pari e m + 2 = 6. Così m + 2 è la somma di 3 primi. Di questi primi due sono dispari e il terzo è 2 (perché la loro somma m + 2 deve essere pari). Così m = (m + 2) – 2 è la somma di due primi.

La Congettura di Goldbach:

- basta un controesempio per smentirla - non bastano miliardi di esempi per confermarla

4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7, 12 = 5 + 7, 14 = 3 + 11, 16 = 5 + 11, …

2p = p + p per ogni primo p

Apostolos Doxiadis, Zio Petros e la Congettura di Goldbach

Varianti e risultati “parziali”

1) La congettura dispari di Goldbach: ogni numero dispari h = 7 è la somma di 3 primi. Vinogradov, 1937: vero per h abbastanza grande Cheng, Wang, 1989: vero per h = 1043000 (un limite ancora troppo grande per i computer)

2) Schnirelman, 1930: esiste s tale che ogni intero è la somma di al più s primi

Ramaré,1995: s = 6

3) Richert, 1949: ogni intero n > 6 è la somma di primi distinti

4) Schinzel, 1959: la congettura di Goldbach equivale a provare che ogni intero n > 17 è la somma di esattamente 3 primi distinti.

Come generare i primi Il problema: rappresentare in modo “elementare”

- la funzione che associa a ogni naturale n l’n-mo numero primo (in ordine di grandezza) - la funzione che a ogni primo associa il primo che lo segue (in ordine di grandezza)

Più in generale: determinare effettivamente una funzione “elementare” iniettiva dai naturali ai naturali la cui immagine contenga una grande varietà di primi. Varie possibili risposte Una curiosità (Eulero) Sia f(x) = x2 + x + 41. Allora

• per ogni naturale n = 39 f(n) è un numero primo (da 41 a 1601) • f(40) = 402 + 40 + 41 = (40 + 1) · 40 + 41 = 41·40 + 41 = 412 non è primo.

D’altra parte Per ogni polinomio non costante a coefficienti interi f(x) in una indeterminata x esistono infiniti numeri naturali n per cui |f(n)| non è primo. Cenni di dimostrazione Sia n(0) un numero naturale tale che |f(n(0))| è un primo p. Siccome limx? +8 |f(x)| = + 8 , esiste un numero naturale n(1) tale che, per ogni naturale n = n(1), vale |f(n)| > p. Sia allora h uno qualunque degli infiniti naturali per cui n(0) + h·p = n(1).

• Dato che f è un polinomio, f(n(0) + h·p) – f( n(0) ) è un multiplo di p. • D’altra parte |f(n(0) + h·p)| > p.

Si deduce che, per ogni h, f(n(0) + h·p) è composto. Torniamo alla soluzione del decimo problema di Hilbert

Due concetti senza apparente legame Per S insieme non vuoto di naturali

• S è ricorsivamente enumerabile: esiste un programma effettivo che elenca gli elementi di S • S è diofanteo: esiste un polinomio p(x, x1, …, xk ) a coefficienti interi tale che S si compone

di quei naturali n per cui p(n, x1, …, xk ) ammette radici naturali. Facile convincersi che, se S è diofanteo, allora S è ricorsivamente numerabile.

Il risultato chiave verso la soluzione del decimo problema di Hilbert (Matijasevic, Davis, Putnam, J. Robinson): S è ricorsivamente enumerabile se e solo se S è diofanteo.

Un’altra caratterizzazione degli insiemi diofantei (Putnam)

Sia S un insieme non vuoto di naturali. Allora S è diofanteo se e solo se esiste un polinomio q(x1, …, xm ) a coefficienti interi tale che, per ogni naturale n > 0, n sta in S se e solo se esistono naturali c1, …, cm per cui n = q( c1, …, cm ). Cenni sulla dimostrazione Se S è diofanteo e p(x, x1, …, xk ) è un polinomio che lo certifica tale, si pone

q(x, x1, …, xk ) = x · (1 –p2(x, x1, …, xk )). Allora per ogni n appartenente a S (uguale o diverso da 0), ci sono naturali a1, …, ak per cui p(n, a1, …, ak ) = 0. Ma allora

q(n, a1, …, ak ) = n · (1 –p2(n, a1, …, ak )) = n.

D’altra parte, sia n > 0 un naturale esprimibile nella forma

n = q(b, b1, …, bk) = b · (1 – p2 (b, b1, …, bk )) per una scelta opportuna di naturali b, b1, …, bk. Siccome n > 0, deve essere p (b, b1, …, bk ) = 0. Quindi n = b e p (n, x1, …, xk ) ha radici naturali b1, …, bk . Viceversa, dato q (x1, …, xm ), si pone p (x, x1, …, xm ) = q (x1, …, xm ) – x. Allora per ogni naturale n (uguale o diverso da 0), n appartiene in S se e solo se, per qualche scelta di c1, …, ck naturali, n = q (c1, …, cm ) ovvero p (n, c1, …, cm ) = 0. Facile convenire: l’insieme dei primi è ricorsivamente enumerabile (ed esclude 0). Lecito dedurne: c’è un polinomio a coefficienti interi q (x1, …, xk ) di cui i primi costituiscono i valori positivi. Un esempio esplicito? Jones, Sato, Wada, Wiens, 1976, 26 indeterminate, grado 25

Esempi non scritti esplicitamente - 21 indeterminate, grado 21 (Matijasevic) - 10 indeterminate, ma grado > 1045 (Matijasevic) - grado 5, ma 42 indeterminate (Jones, Sato, Wada, Wiens)

Scritto esplicitamente 12 indeterminate, grado 1397 (Matijasevic) Da notare: ricorsivamente enumerabili (dunque diofantei) anche gli insiemi dei

• primi di Fermat • primi di Mersenne • primi di Germain • primi p tali che p + 2 è ancora primo

Una strategia più rapida per generare i primi nella pratica Un criterio di primalità, Pocklington, 1914 Siano p un primo dispari, 1 < k < 2·(p+1) un intero che non è multiplo di p. Sia q = 2kp + 1. Allora q è primo se e solo se esiste un intero a tale che 1 < a < q, a(q – 1)/2 = – 1 (mod q) e q è primo con ak + 1. L’algoritmo: per ogni primo p, si prende k che soddisfa le condizioni indicate e si costruisce q = 2kp + 1. Nessuna certezza teorica a sostenere il meccanismo. Ma nella pratica funziona (purché si sappiano distinguere rapidamente i primi dai composti).

L’avvento della teoria analitica dei numeri Eulero: per ogni reale s > 1 la serie Sn 1/ns (per n che varia tra i naturali da 1 a + 8 ) converge: poniamo

?(s) = Sn 1/ns per s reale, s > 1.

Allora • ? è continua e differenziabile, • ?(s) ? 0 per ogni reale s > 1, • lims ? + 8 ?(s) = 1, • (il collegamento con i primi) per ogni s > 1, ?(s) = ? p 1/(1 – 1/ps) per p che varia tra i

numeri primi. Un teorema di Eulero (1737) e una nuova conferma dell’infinità dei primi Per p che varia tra i primi Sp 1/p = + 8 . Da confrontare con: Sn 1/n2 = p2 /6 (un altro famoso risultato di Eulero). La conclusione: i primi sono più frequenti dei quadrati.

Cenni sulla dimostrazione Da ricordare: per ogni primo p (e per k che varia tra i naturali) Sk 1/pk = 1 / (1 – 1/p). Dunque, per ogni intero N > 1,

S1=n=N 1/n = ? p=N Sk 1/pk = ? p=N 1/(1 – 1/p). D’altra parte

ln ? p=N 1/(1 – 1/p) = – Sp=N ln (1 – 1/p)

e per ogni p

– ln (1 – 1/p) = Sm 1/m·pm = 1/p + 1/p2 · Sk 1/pk = 1/p + 1/p2 · 1/(1 – 1/p) = = 1/p + 1/p·(p – 1) < 1/p + 1/(p – 1)2 .

Se ne deduce

ln S1=n=N 1/n = ln ? p=N 1/(1 – 1/p) < Sp=N 1/p + Sp=N 1/(p – 1)2 = = Sp 1/p + Sn 1/n2 = Sp 1/p + p2 /6 .

Ma per N che tende a + 8 anche log S1=n=N 1/n diverge a + 8 . Di conseguenza, al variare di p tra i primi, Sp 1/p = + 8 .

La distribuzione dei primi Poniamo per ogni x reale positivo, p(x) = numero dei primi = x. La funzione p cerca di chiarire la distribuzione dei primi. Legendre, 1798

p(x) = x / (ln x – A(x)) dove limx ? + 8 A(x) = 1,08366… Da notare: se limx ? + 8 A(x) esiste finito, p(x) coincide asintoticamente con x / ln x.

Gauss, 1792 (a quindici anni) p(x) coincide asintoticamente con il logaritmo integrale di x

Li(x) = ? 1/ln t dt con l’integrale che va da 2 a x. Se ne deduce che p(x) coincide asintoticamente con x / ln x.

Chebyshev, circa 1850

• Per ogni e > 0, esiste un reale x(0) > 0 tale che, per ogni reale x > x(0), (C' – e) x/ln x < p(x) < (C + e) x/ ln x

dove C' = 21/2 · 31/3 ·51/5 ·301/30 < 1 e C = 6/5 C' (stima migliorata, per esempio da Erdös, 1930:

(ln 2 – e) x/ln x < p(x) < (ln 4 + e) x/ ln x). • Il limite di p(x) / (x/ ln x) per x che tende a +8 , se esiste, è 1. • Per ogni intero N > 1, c’è sempre almeno un primo tra N e 2N (il postulato di Bertrand). • La funzione di Chebyshev ?(x) = Sp=x ln p (per x reale positivo).

Riemann Si allarga la funzione ? ai complessi.

• Si pone anzitutto ?(s) = Sn 1/ns = ? p 1/(1 – 1/ps)

per ogni numero complesso s con parte reale Re(s) > 1. • Si prolunga poi analiticamente ?(s) al semipiano Re(s) > 0 come ? e–u · us–1 du (con u che va

da 0 a 8 ), poi all’intero piano complesso.

Gli zeri di ?(s) • Tutti per Re(s) < 1. • Per Re(s) < 0, zeri banali – 2, – 4, – 6, … • Nella striscia critica 0 < Re(s) < 1?

L’ipotesi di Riemann (un altro problema del millennio, 2000) Gli zeri non banali di ?(s) sono tutti sulla retta critica Re(s) = ½ (e sono infiniti: provato da Hardy, 1914)

Dall’ipotesi di Riemann si deduce come corollario che p(x) coincide asintoticamente con x/ln x.

Hadamard, De la Vallée Poussin, 1896: Il teorema dei numeri primi

p(x) coincide asintoticamente con x / ln x Si usa la teoria analitica dei numeri. Ma nel 1949 Erdös e Selberg danno una dimostrazione “elementare”.

Altre stime asintotiche (tornando ai primi gemelli e ai primi di Germain…) Per ogni scelta di interi positivi a, b poniamo

Sa,b (x) = numero dei primi p = x tali che a·p + b è ancora primo (x reale positivo).

Esempi • S1,2 (x) = numero dei primi p = x tali che p + 2 è ancora primo (= numero delle coppie di

primi gemelli p, p + 2 con p = x) • S2,1 (x) = numero dei primi di Germain = x

Da notare: S1,2 viene denotata anche con p2

La costante dei primi gemelli C2 = ? p>2 (1 – 1/(p–1)2) = 0,6601618… (Wrench, 1991) Una congettura di Hardy-Littlewood, 1923 p2 (x) coincide asintoticamente con 2 C2 x/ln2 x.

Bombieri, Davenport, 1966: p2 (x) = 8 C2 x/ln2 x (1 + 0(ln ln x / ln x)) In ogni caso Sa,b (x) = C x/ln2 x per qualche costante C. Dunque limx ? + 8 Sa,b (x) / p(x) = 0. In questo senso i primi p tali che a·p + b è ancora primo hanno densità 0 tra tutti i primi. Come conseguenza ci sono infiniti primi p per cui a·p + b non è primo. In particolare:

• ci sono infiniti primi p per cui p + 2 non è primo, • ci sono infiniti primi che non sono di Germain.

Algoritmi rapidi di primalità (finalmente!) Input: un intero dispari N > 2 Output: N è primo o composto? Algoritmi probabilistici L'idea: sacrificare la precisione per aumentare la velocità. Dunque

• si ricorre all’aiuto di testimoni (rapidi da presentare) • si ammettono risposte sbagliate o incerte purché i tempi di lavoro siano accelerati • si cerca di rendere minima la probabilità di errore o di insicurezza (al variare dei testimoni)

Émile Borel: un evento che ha probabilità < 10-50 non accadrà mai, e se anche accade non sarà mai rilevato.

Algoritmi probabilistici

• tipo Montecarlo: risposte probabilmente vere in tempi certamente rapidi • tipo Las Vegas: risposte certamente vere in tempi probabilmente rapidi

In altre parole • nel primo caso è ammessa la possibilità che un testimone sbagli • nel secondo caso è ammessa la possibilità che un testimone dica “non lo so”

(entrambe da rendere minime!)

Un esempio di algoritmo Montecarlo per i primi: l’algoritmo di Miller-Rabin, 1978

Efficiente ma fallibile! I prerequisiti: se N è primo,

• le radici quadrate di 1 modulo N sono ± 1, • (il piccolo teorema di Fermat) per ogni intero a primo con N, aN – 1 = 1 (mod N).

Il procedimento È dato l’intero dispari N > 2, N dispari. Dunque N –1 è pari (da tenere presente!). Invochiamo un testimone a con 1 < a < N.

Miller

Rabin

Passo 1 Si calcola il massimo comune divisore di a e N.

• Se a non è primo con N, l’algoritmo risponde (correttamente) “N COMPOSTO” (in realtà si ottiene un divisore non banale di N: appunto, il massimo comune divisore di a e N)

• Se a è primo con N, si procede con i passi successivi. Passo 2 Si calcola aN – 1 modulo N.

• Se non vale aN – 1 = 1 (mod N), l’algoritmo risponde (correttamente) “N COMPOSTO” • Se invece aN – 1 = 1 (mod N), si va al passo successivo.

Passo 3 Si calcola a(N – 1)/2 modulo N (la radice quadrata di aN – 1 modulo N).

• Se a(N – 1)/2 non è congruo modulo N né a 1 né a – 1, l’algoritmo risponde (correttamente) “N COMPOSTO”.

• Se a(N –1)/2 = – 1 (mod N), l’algoritmo azzarda “N PRIMO”. • Lo stesso succede se a(N –1)/2 = 1 (mod N) ma (N – 1)/2 non è pari, cioè non si può

dimezzare ulteriormente tra gli interi. • Altrimenti, se a(N –1)/2 = 1 (mod N) ma (N – 1)/2 è pari, cioè (N – 1) /4 esiste tra gli interi ,

si va ai passi successivi. Passo 4 Come il passo 3, ma riferito ad a(N – 1)/4 modulo N (la radice quadrata di a(N – 1)/2 modulo N. Si prosegue finchè possibile. Numero complessivo di passi: al più logaritmico in N. Commento

• La risposta “N COMPOSTO” è sicura. • Quella “N PRIMO” può essere sbagliata.

Probabilità di errore dopo la consultazione di un testimone a: al variare di a, al più ¼ In altre parole: almeno 3 testimoni su 4 dicono la verità!

Tempi di lavoro Sono da calcolare - all’inizio un massimo comune divisore - poi per ogni passo un elevamento a potenza e una divisione. Complessivamente, tempi limitati da un polinomio di grado al più 5 rispetto alla lunghezza di N. D'altra parte, dopo la consultazione di 100 testimoni a con esito concorde “N PRIMO”, la probabilità di errore diventa

1/4100 < 10–50 .

Esempi 1) Sia N = 13. Ovviamente N – 1 = 12. Scegliamo a = 2. Allora

• 2 è primo con 13, • 212 = 4096 = 1 (mod 13), • 26 = 64 = – 1 (mod 13).

Dunque l’algoritmo dichiara “N PRIMO” e in effetti N è primo. 2) Sia N = 7, così N – 1 = 6. Facciamo ancora riferimento ad a = 2. Allora

• 2 è primo con 7, • 26 = 64 = 1 (mod 7), • 23 = 8 = 1 (mod 7)

dopo di che non è più possibile dividere l’esponente per 2. Dunque l’algoritmo dichiara “N PRIMO” e in effetti N è primo.

3) Sia adesso N = 561 (uno pseudoprimo di Carmichael – in altre parole, per ogni b primo con

N, b560 = 1 (mod 561)). Ricordiamo 561 = 561 = 3 · 11 · 17. Se dunque si sceglie a = 359, con un po’ di pazienza si controlla

• 359 è primo con 561, • 359560 = 1 (mod 561), • 359280 = 1 (mod 561), • 359140 = 1 (mod 561), • 35970 = 1 (mod 561), • 35935 = 1 (mod 561).

Siccome 35 non si può dividere ulteriormente per due, l’algoritmo, se ricorre ad a = 359, dichiara “N PRIMO” mentre N è composto. Ma se il testimone 359 non è attendibile, a = 2 lo è. Infatti

• 2 è primo con 561, • 2560 = 1 (mod 561), • 2280 = 1 (mod 561), • 2140 non è congruo né a 1 né a – 1 modulo 561.

Quindi il ricorso ad a = 2 dichiara correttamente “N COMPOSTO”.

Un altro algoritmo Montecarlo per i primi: l’algoritmo di Solovay-Strassen, 1977

Solovay

Strassen

Il fondamento: per N dispari,

• se N è primo, ogni intero a (in particolare primo con N) soddisfa (a/N) = a(N – 1)/2 (mod N), (Eulero)

• ma se N è composto, al più metà degli interi a modulo N primi con N soddisfa la stessa congruenza (Solovay-Strassen).

Il procedimento È dato l’intero dispari N > 2, N dispari. Invochiamo un testimone a con 1 < a < N.

Passo 1 Si calcola il massimo comune divisore di a e N.

• Se a non è primo con N, l’algoritmo risponde (correttamente) “N COMPOSTO”. • Se a è primo con N, si procede con i passi successivi.

Passo 2 Si calcolano (a/N) e a(N – 1)/2 modulo N.

• Se non vale (a/N) = a(N – 1)/2 (mod N), l’algoritmo risponde (correttamente) “N COMPOSTO”

• Se invece (a/N) = a(N – 1)/2 (mod N), si dichiara “N PRIMO”. Commento

• La risposta “N COMPOSTO” è sicura. • Quella “N PRIMO” può essere sbagliata.

Probabilità di errore dopo la consultazione di un testimone a: al variare di a, al più 1/2 In altre parole: almeno un testimone su 2 dice la verità! Tempi di lavoro Da calcolare - all’inizio un massimo comune divisore - poi un simbolo di Legendre, un elevamento a potenza e una divisione.

Tempi polinomiali. D'altra parte, dopo la consultazione di 200 testimoni a con esito concorde “N PRIMO”, la probabilità di errore diventa

1/2200 < 10–50 .

Algoritmo di Miller-Rabin: preferibile. Un algoritmo rapido e infallibile (finalmente!): l’algoritmo AKS (Agrawal, Kayal, Saxena), 2002

• Agrawal: informatico teorico, con interessi alla complessità computazionale • Kayal, Saxena: matematici, dottorandi di Agrawal.

Agosto 2002: l'algoritmo AKS • distingue se un dato intero N > 1 è primo o composto • lavora in tempo poco più che polinomiale di grado 8 rispetto alla lunghezza di N • soddisfa finalmente le richieste di Gauss (due secoli dopo la loro formulazione).

Il fondamento: una caratterizzazione dei primi che già conosciamo Per N, a interi primi tra loro, N > 1, N è primo se e solo se i due polinomi di grado N xN + a e (x + a)N hanno i coefficienti di ugual grado a 2 a 2 congrui modulo N. La difficoltà: N + 1 coppie di coefficienti da confrontare (troppe rispetto alla lunghezza di N). Idea: invece che xN + a e (x + a)N, confrontare i loro resti nella comune divisione per un polinomio xr – 1 con r opportuno e piccolo rispetto alla lunghezza di N (i resti hanno grado < r o sono nulli).

Conseguenze di AKS

Algoritmo di Bernstein-Berrizbeitia, 2004 • probabilistico di tipo Montecarlo • lavora in tempo poco più che polinomiale di grado 4 rispetto alla lunghezza di N • assolutamente affidabile quando risponde “N PRIMO” • talora fallibile (ma con bassa probabilità di errore) quando dichiara “N COMPOSTO”

Da usare in combinazione con l'algoritmo di Miller-Rabin Per ogni input N, si eseguono in parallelo su N i due algoritmi, ricorrendo a opportuni testimoni. - Se l’algoritmo di Bernstein-Berrizbeitia dichiara “N PRIMO”, si conclude che N è primo. - Se l’algoritmo di Miller-Rabin dichiara “N COMPOSTO”, si conclude N composto. Il caso disgraziato (rarissimo) L’algoritmo di Bernstein-Berrizbeitia dichiara “N COMPOSTO”, quello di Miller-Rabin “N PRIMO”: ripetere il procedimento con nuovi testimoni. Algoritmo di Lenstra-Pomerance, 2005 Un ulteriore miglioramento di AKS

• non probabilistico • richiede tempo di lavoro poco più che polinomiale di grado 6 rispetto alla lunghezza di N

(quanto di meglio si può attendere da AKS).

E il problema della fattorizzazione? La versione originaria Input: un intero N > 1 Output: la decomposizione di N in fattori primi Versione “ridotta” Input: N > 1 composto e dispari Output: un divisore d di N, 1 < d < N In realtà la questione chiave! Il motivo…

1. E’ rapido riconoscere i primi e i composti, e un numero primo N ha già la sua fattorizzazione N: dunque lecito assumere N composto.

2. Se N è pari, basta prendere d = 2: lecito supporre N dispari. 3. Una volta che è noto d, una divisione svela il quoziente q di N per d, N = d · q. A questo

punto - se d e q sono entrambi primi, N = d · q è la fattorizzazione cercata, - se d o q (o entrambi) sono composti, si applica di nuovo il procedimento a d e q. Alla fine si raggiunge la fattorizzazione cercata.

4. Il numero di possibili ripetizioni del meccanismo è al più logaritmico nella lunghezza di N. Quindi l’eventuale appendice di lavoro per d, q e oltre non aggrava di per sé i tempi complessivi.

Il guaio: i tempi di lavoro degli algoritmi oggi conosciuti per la versione “ridotta” sono esponenziali (o quasi) rispetto alla lunghezza dell'input N Gran spreco di strumenti teorici

• curve ellittiche, • frazioni continue, ...

nessuno capace di lavorare in tempo al più polinomiale nella lunghezza di N. Attenzione alla computazione quantistica ( P. Shor, 1994)!

L’algoritmo del letamaio (H.W. Lenstra)

“Ammettiamo di avere due numeri primi p ? q e il loro prodotto N = p · q e di smarrire p, q in un letamaio, così che ci rimane solo N. Deve essere sentito come una sconfitta della scienza il dover ammettere che l’algoritmo più rapido per recuperare p e q è quello di cercare nel letamaio” Quando ancora non c’erano i calcolatori: alcune famose decomposizioni in fattori primi

• Eulero, 1742: F(5) = 641 · 6700417 • Clausen, 1856: F(6) = 274177 · 67280421310721 • Landry, 1869: M(59) = 179951 · 3203431780337 • Cole, 1903: M(67) = 193707721 · 761838257287 (convegno dell'American Mathematical

Society a S. Francisco, “tre anni di domeniche”) • Poulet, 1923: M(73) = 439 · 2298041 · 9361973132609 (ma il fattore 439 era già stato

scoperto da Eulero).

Prima di concludere: qualche primo curioso… (Dubner)

Primi palindromi Hanno la forma a1 a2 … ak–1 ak con a1 = ak, a2 = ak–1 , … Un esempio semplice: 101 Più complicati

• 1011810 + 1465641·105092 + 1 (11811 cifre) • 1011310 + 4661664·105652 + 1 (11311 cifre)

Altri primi esotici…

• 72323252323272325252 · (103120 – 1) : (1020 – 1) (3120 cifre, tutte prime) • 1 uno, poi 2 due, 4 tre, 8 quattro, 16 cinque, 32 sei, 64 sette, 128 otto, 4220 nove

Con i soli 0 e 1 2700 uno seguiti da 3155 zero e da un uno finale: 5856 cifre complessive

Col solo 9 (e poco più)

• 1 uno iniziale, poi 7517 nove • 1 due iniziale, poi 9439 nove • 1 quattro iniziale, poi 8072 nove • 1 cinque iniziale, poi 4332 nove • 1 sette iniziale, poi 796 nove • 1 otto iniziale, poi 8415 nove

Ovviamente, non 3, 6 e 9 iniziali (se no il numero che si forma è multiplo di 3)

• 2874 nove, poi due, poi altri 2874 nove (palindromo!)

Applicazioni alla crittografia Crittografia = scrittura nascosta La codifica: dal messaggio in chiaro al messaggio cifrato La decodifica: dal messaggio cifrato al messaggio in chiaro Chiave di codifica, chiave di decodifica: l’una inversa dell’altra Un’utile convenzione: numeri al posto delle lettere

A 0 N 13 B 1 O 14 C 2 P 15 D 3 Q 16 E 4 R 17 F 5 S 18 G 6 T 19 H 7 U 20 I 8 V 21 J 9 W 22 K 10 X 23 L 11 Y 24 M 12 Z 25

La crittografia del duemila: non solo per le spie, ma per tutti

• Posta elettronica • Commercio elettronico • Voto telematico •

Il caso del commercio elettronico

• Un venditore Alice • Molti possibili acquirenti Bob • Pirati informatici Eve (da eavesdropper = chi origlia)

Ordini via Internet, pagamento con carta di credito: una corrispondenza da mantenere riservata

Varie asimmetrie • Un solo venditore, molti compratori • Nessuna distinzione dei ruoli tra acquirenti e pirati

Da distinguere

• codifica pubblica (a tutti è permesso ordinare prodotti) • decodifica privata (solo ad A è permesso ricevere gli ordini)

Ma codifica e decodifica restano operazioni l’una inversa dell’altra!

Crittografia a chiave pubblica: Diffie-Hellman, 1976

Il crittosistema più popolare: RSA (Rivest, Shamir, Adleman), 1978

Il fondamento Per p ? q primi grandi,

• “facile” moltiplicare p per q per ottenerne il prodotto N = p · q, • “difficile” decomporre N in fattori primi per recuperare p e q.

Anche

• “facile” generare e riconoscere i primi.

Alice si organizza • Sceglie due primi grandi p ? q e ne calcola il prodotto N. • Ricava anche f (N) = (p – 1)·(q – 1). • Sceglie due interi e, d uno inverso dell’altro modulo f (N).

e·d = 1 (mod f (N)) cioè e·d = k · f (N) + 1 per qualche intero k • Divulga N ed e (la chiave pubblica di codifica) • Conserva p, q, d (la chiave privata di decodifica).

Unità di messaggio: numeri naturali n Possiamo supporre: n < p, q, dunque n < N e, escluso il caso n = 0, n primo con p, q, N Come Bob codifica i suoi ordini

• Bob eleva ogni unità n di messaggio alla e modulo N n ? ne (mod N)

Come Alice decodifica i messaggi che le arrivano

• Alice eleva ogni unità m di messaggio alla d modulo N m ? md (mod N)

Perché si recupera il messaggio originale Da ricordare: per n primo con N,

nf(N) = 1 (mod N) dunque

nf(N) + 1 = n (mod N) (vero anche per n = 0). Ne deriva: per ogni unità di messaggio n,

(ne)d = ne·d = nk · f(N) + 1 = n (mod N).

La sicurezza da Eve

• Eve conosce N ed e. • Se intercetta un’unità di messaggio cifrato m, deve comunque estrarne la radice e-sima per

recuperare n La via maestra per ottenere n

• recuperare d ed elevare m alla d modulo f (N) • dunque ricavare f (N) = (p – 1)·(q – 1) • dunque ottenere p e q, cioè decomporre N = p · q in fattori primi

La sicurezza di RSA si basa allora

• sulla difficoltà di decomporre rapidamente in fattori primi • sull’assenza di algoritmi di calcolo di f che evitano di ricorrere alla fattorizzazione.

Qualche precauzione per Alice

• cambiare spesso N • evitare e, d piccoli

Parziali esposizioni della chiave privata mettono in pericolo la sicurezza del crittosistema.

Il primo crittosistema a chiave pubblica: Diffie, Hellman, 1976

Il fondamento Per p primo grande, gli interi non nulli a modulo p sono le potenze di uno opportuno g tra loro. Inoltre

• “facile” elevare g a un intero n, 0 < n < p – 1 per ottenere il generico a • “difficile” recuperare n da a = gn

Il problema del logaritmo discreto: gli stessi imbarazzi della fattorizzazione.

Alice e Bob si organizzano • Si accordano preventivamente sul primo p e su g • Ciascuno dei due sceglie un naturale < p – 1: n per Alice, m per Bob • Alice rende pubblico gn e mantiene riservato n; Bob rende pubblico gm e mantiene riservato

m • Ciascuno dei due calcola gn·m : Alice come (gm)n e Bob come (gn)m

La chiave che Alice e Bob condividono per impostare il loro crittosistema: gn·m

La sicurezza da Eve • Eve conosce gn e gm • Deve però ricavare gn·m.

La via maestra • recuperare n da gn (oppure m da gm) per ritrovarsi nelle stesse condizioni di Alice (Bob)

L’ipotesi di Diffie-Hellman Strategie alternative non sono computazionalmente più facili. La sicurezza del crittosistema si basa allora sulla difficoltà di calcolare i logaritmi discreti.