Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico...

49
Sorprendenti applicazioni di Algebra e Geometria Ciro Ciliberto, Universit ` a di Roma Tor Vergata PISTOIA,SETTEMBRE 2013 Ciro Ciliberto, Universit ` a di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Transcript of Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico...

Page 1: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Sorprendenti applicazioni di Algebra eGeometria

Ciro Ciliberto, Universita di Roma Tor Vergata

PISTOIA, SETTEMBRE 2013

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 2: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Vorrei parlare ...

... di matematica solitamente ritenuta, dagli stessi matematici diprofessione, molto astratta: cioe ALGEBRA e GEOMETRIA.

Il termine ALGEBRA deriva dal titolo del libro del matematicoarabo persiano Muhammad ibn Musa al–Kwarizmi (780–850),intitolato Al-Kitab al-Jabr wa-l-Muqabala, cioe Compendio sulCalcolo per Completamento e Bilanciamento, che tratta larisoluzione delle equazioni di primo e di secondo grado in vistadi applicazioni a problemi molto concreti.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 3: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

L’algebra ...

... e in particolare l’aritmetica o teoria dei numeri, fu importatain occidente nel secolo XIII per motivi assai pratici, cioe per fardi conto negli affari, principalmente da Leonardo Fibonacci(1170–1250), autore del Liber Abaci e Practica Geometriae.

Il primo a usare il termine algebra nel mondo occidentale fu ilmaestro d’abaco fiorentino Raffaello di Giovanni Canacci,autore dei Ragionamenti di Algebra (1490).

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 4: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Geometria ...

... viene dal greco

γεωµετρια

che significa misura della terra. Dunque le sue origini moltoconcrete sono fuori di ogni dubbio.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 5: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Nel 1940, G. H. Hardy scrive in “A mathematician’sapology” ...

... Gauss e altri matematici possono essere giustificati nelrallegrarsi del fatto che vi sia soprattutto una scienza, la teoria deinumeri, quella che loro hanno coltivato, la cui lontananza dalleordinarie attivita umane ne preservi la dolcezza e purezza.

Ma Hardy si sbagliava: gia durante la seconda guerra mondiale AlanTuring, inventore dell’informatica teorica, che era stato collega diHardy a Cambridge, lavorava come crittografo per i servizi segretibritannici per decifrare, usando tecniche algebriche, in particolareteoria dei numeri, i messaggi in codice dei tedeschi trasmessi con lamacchina Enigma.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 6: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Crittografia

La crittografia si occupa del seguente:

ProblemaCome si fa a comunicare in modo segreto e sicuro?

Come si fa a inviare messaggi cifrati che possano esserefacilmente decifrati dai destinatari ma non da chi non siaautorizzato?

Questo problema e estremamente attuale ai giorni nostri, in cuile comunicazioni sono essenziali, frequenti, facili e moltorapide, e richiedono riservatezza, ma sono anche moltovulnerabili.

ApplicazioniSono ubique, in ambito militare, industriale, privato ...

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 7: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

La crittografia nell’antichita

Erodoto (Alicarnasso, V sec. a.C.), Le Storie, Libro V eLibro VII: steganografia (procedura che consiste nelnascondere i messaggi).

Svetonio (II sec. d.C.), Vite dei Cesari: Giulio Cesare, perscopi militari, usava semplici modelli matematici per lacrittografia (che consiste nel nascondere non il messaggioma il suo significato).

Il tipico esempio consiste nello spostare di tre lettere,rispetto alla posizione nell’alfabeto, ogni lettera delmessaggio da inviare.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 8: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Equivalenti numerici delle 26 lettere

a −→ 0 h −→ 7 o −→ 14 u −→ 20b −→ 1 i −→ 8 p −→ 15 v −→ 21c −→ 2 j −→ 9 q −→ 16 w −→ 22d −→ 3 k −→ 10 r −→ 17 x −→ 23e −→ 4 l −→ 11 s −→ 18 y −→ 24f −→ 5 m −→ 12 t −→ 19 z −→ 25g −→ 6 n −→ 13

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 9: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Aritmetica modulare (I)

Scegliamo un numero naturale

n ∈ N = {1,2, ....}

Ad ogni numero intero

x ∈ Z = {...,−2,−1,0,1,2, ....}

possiamo associare

x mod n ∈ Zn = {0,1,2, ...,n − 1}

che e il resto della divisione di x per n.

Esempi

3 mod 2 = 1, 3 mod 4 = 3, 100 mod 9 = 1

7 mod 5 = 2, 11 mod 3 = 2, 137 mod 6 = 5

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 10: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Aritmetica modulare (II)

Con i numeri di Zn possiamo operare sommandoli,sottraendoli e moltiplicandoli e poi prendendo il resto delladivisione per n;

il cifrario di Cesare consiste nel sommare ad ogni numerodi Z26 un fissato numero C, che e la chiave per cifrare. Lachiave per decifrare e C′ = −C = n − C;

questo sistema di cifratura si puo raffinare in vari modi,rendendolo piu complicato (L. B. Alberti XVI sec., B. deVigenere XVII sec.);complesse macchine prima meccaniche, poielettro–meccaniche, per cifrare e decifrare con sistemiconsimili sono state usate nel corso della storia fino atempi recenti, ad es. la macchina Enigma.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 11: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Crittoanalisi

La crittoanalisi consiste nello sviluppare tecniche atte adecifrare messaggi cifrati, di cui non conosciamo la chiave.Ad esempio, come si fa a decifrare un messaggio in codiceinviato col cifrario di Cesare, se non conosciamo la chiave?Si usa l’analisi delle frequenze.

Lettera % Lettera % Lettera %

a 11,74 h 1,54 q 0,51b 0,92 i 11,28 r 6,38c 4,50 l 6,51 s 4,98d 3,73 m 2,52 t 5,63e 11,79 n 6,88 u 3,02f 0,95 o 9,83 v 2,10g 1,65 p 3,05 z 0,49

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 12: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Un esempio di crittoanalisi (I)

Vogliamo decifrare il messaggio:

IN DNHHN OFZHHRIRGN ON A DNHHATA LAZLCA

Frequenza delle lettere nel messaggio:

Lettera Occor-renze Lettera Occor-

renze Lettera Occor-renze

A 5 H 6 Q 0B 0 I 2 R 2C 1 L 2 S 0D 2 M 0 T 1E 0 N 6 U 0F 1 O 2 V 0G 1 P 0 Z 2

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 13: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Un esempio di crittoanalisi (II)

L’analisi delle frequenze suggerisce che:

A=i, N=a, I=l, Z=o, R=u, H=t

Otteniamo:

la Datta OFottuluGa Oa i DattiTi LioLCi .

Con un po’ di buonsenso perveniamo alla soluzione:

la gatta frettolosa fa i gattini ciechi

Metodo analogo per la interpretazione di linguesconosciute: es. lineare B cretese (A. Evans, 1900).

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 14: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Quanto costano crittografia e crittoanalisi?

I numeri si rappresentano con scrittura posizionale in unadata base b, che e numero intero maggiore di 1.

Di solito usiamo b = 10:

1.498.742 = 1 ·106 +4 ·105 +9 ·104 +8 ·103 +7 ·102 +4 ·101 +2 ·100.

I computer usano la base b = 2:

(1111110110000)2 = 1 · 212 + 1 · 211 + 1 · 210 + 1 · 29 + 1 · 28+

+ 1 · 27 + 0 · 26 + 1 · 25 + 1 · 24 + 0 · 23 + 0 · 22 + 0 · 21 + 0 · 20

che in base 10 si scrive 8.112.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 15: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

La lunghezza dei numeri

La lunghezza L(n) di un numero n e il numero di cifre cheoccorrono per scriverlo in base 2. La lunghezza e unamisura della grandezza di un numero.

Notiamo che L(n) e in generale molto minore di n.Precisamente, si ha

L(n) ∼ log2 n

Ad esempio

L(8.112) = 12.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 16: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Come si fanno le operazioni?

Riporti 1 1 1 1 1 11 0 1 1 1 1 1 1 +

1 0 1 1 =

1 1 0 0 1 0 1 0

1 1 1 0 1 ×1 1 0 1 =

1 1 1 0 11 1 1 0 1 - -

1 1 1 0 1 - - -

1 0 1 1 1 1 0 0 1

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 17: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Algoritmi e loro complessita

Il termine Algoritmo ha origine dal nome di Muhammad ibnMusa al–Kwarizmi.

• Un algoritmo (deterministico) A e una procedura di calcolo connumeri interi, consistente in una successione finita di operazionielementari, volta a risolvere con certezza un problema di calcolo;

• la complessita di A e il numero di operazioni elementari che occorreeffettuare per eseguire A;

• il tempo T (A) per eseguire A e proporzionale alla sua complessita;

• A e polinomiale se la sua complessita per eseguire calcoli connumeri di lunghezza k e approssimativamente kd , con d numerointero positivo;

• A e esponenziale se la sua complessita per eseguire calcoli sunumeri di lunghezza k e approssimativamente 2k (cioe praticamentepari al numero stesso).

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 18: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Algoritmi polinomiali

In generale costa poco effettuare algoritmi polinomiali.Ad esempio

T (a + b) = costante ·max{L(a),L(b)}T (a · b) = costante · (L(a) + L(b))

e la costante dipende dallo strumento di calcolo.Quindi, effettuare somme e prodotti costa poco.Vi sono algoritmi polinomiali per effettuare sottrazioni,divisioni e per il calcolo di MCD e MCM.La crittografia classica, che e basata su questi algoritmi,costa poco.Ma allora costa poco anche la crittonalisi: dunque lacrittografia classica e molto vulnerabile.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 19: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Ad esempio...

... ecco 200 numeri tra 1 e 1.000.000, generati a caso dalcomputer:

651789,106737,549047,590588,189111,334832,664168,81364,624419,737973,873545,559792,643004,820024,461744,865331,510367, 675227,353689,256245,953389,924572,525925,986892,395998, 802914,453642,57974,755766,257215,977252,943634,960154,62604, 112900, 711544,962059,865516,624106,390715,479251,956418,494787,427643,237209,195559,712266,936699, 741422,180394,270653,636106,34453,268619,154640,215232,694682,997579, 160255, 603540,685489,311714,503197,543597,925731, 130972,81364,980960,246087,757874, 113785,251885,310348,911910, 14202,507086,958763, 521543,747215,825884,247586,31167,87149,896038,696722, 128184, 500851,960796,747612,309093,530278,548056,929428,579874, 407458,976429,856543,527658,31403,442276,726631495074,65420,869822,38929,855607,761661,46068,253922,333916,364426,94574,104329,864189,829905,975230,543589,228939,119623,414781,180070,31044,751512,916063,119692,586026,964607,262675,927807,678508,866942,239677,889715,44069,400565,403182,20896,897446,79287,325602,698195,760643,4533,375022,70172,278585,434374,439845,361287,227234,42067,716457,284318,920152,342427,219109,489634,566960,190650,625899,586313,851322,349578,458325,513274,458413,54285,155256,264543,935403,771700,795635,86881,623206,692723,817266,412336,147342,691355,438272,323100, 262429,204178,824438,964016,265764,865808,655728,569467,577996,574447,382042,929291,479344,980752,386127,689869, 988139,511037,139324

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 20: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

In un attimo ...

... il computer da la loro somma:

102443688

... il loro prodotto3817613921743663396461023728148070950128460848907404534775059486995780760294664686020947503766379577190868582315549334626088272924287953983074570549819491116081787793594992408306647428312570276743300736401201379452493013180592482794632323742162610484738340541828409730066428573675486481301338826179180174134216116803148485244736946268055000361108018554221051804486628454354289632833796941299258402203044710484806516877290123270505802745947338401172753717297170697088275273951424035873449644385986644603902726453927163709088171930618910337282434902120011677042563438365907964820667342442190425948769153053547295075561240625141338876419063054801468668571714707419607995613338887013695878852603294931426696012237956531822730181865654711207387929877430854521900300497711635752380501076740715903525831450195757872505299756182277476217106448992291841129958779170672354194650464692161108458000959302713628461928856400394636514002482790905213926846860206803689175712881345537908762916694516217772347555855068177161715790159570311630195541229502136442597487291213399976309517090553856000000000000000000000000000000000000000

... e il loro minimo comune multiplo...

775411562345633118884011825279727809041947048263406633371827088854666480491200623157399948134263471508442383878276784487320972242032026284160746057644333275189460902018419903148373686648347323754423487958549146783406677446261861958729596734835420459653208469181692602894610044782886750162031643029315735009183564028776433718916181036909411554961087385219988961778179175453343103102930420397909805111491496976267873779846965639944631538092736904360691453295561868427868889149871789543098171582898856898030823605905938673133291508218838803751821218979892739106520639396870149779289825794237542836591707574297713571086273497417517323960102453489279607930643795330770260660125247766610410262407179353364463 1065344794530197318391006434719532335691345612800

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 21: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Quali algoritmi costano molto?

EsempioDecomporre un numero nel prodotto dei suoi fattori primi.

Ogni numero si puo fattorizzare, in modo unico nelprodotto di numeri primi.Essenzialmente c’e un unico algoritmo per ottenere questafattorizzazione: il crivello di Eratostene.Esso consiste nel provare a dividere un numero n per tutti inumeri da 2 a

√n.

La complessita di esecuzione del crivello di Eratostene suun numero n e

n log2 n

dunque (piu che) esponenziale, cioe molto piu grande diquel che occorre per sommare o moltiplicare numeri dellalunghezza di n.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 22: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Esponenziale contro polinomiale

Nella prima riga della tabella compare la complessita dell’algoritmo afronte della lunghezza n dell’input. Nelle righe successive la durata afronte di vari valori di n, supponendo che il tempo occorrente pereseguire ogni operazione elementare sia di 10−9 secondi.

n log2 n n log2 n n2 2n n!

10 3 · 10−9 s 3 · 10−8 s 10−7 s 10−6 s 3 · 10−3 s

102 7 · 10−9 s 7 · 10−7 s 10−5 s 4 · 1013 a > 10100a

103 10−8 s 10−5 s 10−3 > 10100a > 10100a

104 1.3 · 10−8 s 10−4 s 10−1 s > 10100a > 10100a

105 1.7 · 10−8 s 2 · 10−3 s 10 s > 10100a > 10100a

106 2 · 10−8 s 2 · 10−2 s 17 m > 10100a > 10100a

Osservazione

Il numero di protoni nell’universo e ∼ 1079.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 23: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Un commento sul crivello di Eratostene

la complessita n log2 n non e poi male se operiamo sunumeri non troppo grandi. Ad esempio, se usiamo un buonPC:

Input: fattorizzare il numero di Mersenne 267 − 1.

Output: dopo una frazione di secondo otteniamo

267 − 1 = 193707721 · 761838257287

Lo stesso risultato fu ottenuto da Frank Cole, 1903,Meeting of the American Mathematical Society in SanFrancisco: “Three years of Sundays”.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 24: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

L’importanza di essere primo

Inumeri primi sono infiniti (Euclide, III sec. AC) e sono imattoni costitutivi dei numeri, perche da loro si ottengono,per moltiplicazione, tutti gli altri numeri.L’individuazione e la distribuzione dei numeri primi sonoproblemi basilari della matematica: il primo e risolto, ilsecondo presenta ancora vaste zone d’ombra.Uno dei sette Problemi del Millennio, posti all’attenzionedei matematici dal Clay Mathematics Institute il 24 maggio2000 con un premio di un milione di dollari per la soluzionedi ciascuno di essi, riguarda la cosiddetta Ipotesi diRiemann, una congettura formulata da Bernard Riemannnel 1859, la cui soluzione getterebbe piena luce sulladistribuzione dei numeri primi.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 25: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Secondo K. F. Gauss (Disquisitiones Aithmeticae,1801) ...

[...] Il problema di distinguere i numeri primi dai numeri composti edi decomporre questi ultimi nei loro fattori primi e ben noto essereuno dei piu importanti ed utili in matematica.

[...] La dignita della scienza stessa sembra richiedere che siaesplorata ogni via possibile per la soluzione di un problema cosıcelebre ed elegante.

[...] Le tecniche finora note richiederebbero una fatica intollerabileperfino per il calcolatore piu infaticabile.

K. F. Gauss (1777–1855) B. Riemann (1826–1866)

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 26: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

I numeri di Mersenne

Anticamente si riteneva che, se p e primo, lo e anche

Mp = 2p − 1

Questo e vero per p = 2,3,5,7,17,19, ma non per

M11 = 23 · 89

M. Mersenne (1588–1648) in CogitataPhysico–Mathematica (1644): M31 e primo, piu alcunecongetture sbagliate, come M67 e primo.Per i numeri di Mersenne Mp esiste l’efficace test diprimalita di Lucas–Lehmer: Lehmer prova negli anni ’30che M127 ∼ 1039 e primo.

M. Mersenne (1588–1648)Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 27: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Numeri da record!

Il piu grande numero primo noto e il numero di Mersenne

257.885.161 − 1, ha 17.425.170 cifre decimali

Trovato da Curtis Cooper, University of Central Missouri, il25 gennaio 2013 dopo 39 giorni di calcolo ininterrottonell’ambito del progetto Great Internet Mersenne PrimeSearch (GIMPS) che e un progetto di calcolo condiviso suInternet su larga scala.I primi dieci piu grandi numeri primi noti sono numeri diMersenne.Per informazioni, cfr. i siti

http://primes.utm.edu/http://www.mersenne.org/

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 28: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

M. Agrawal, N. Kayal, N. Saxena, Primes is in P, Annals of Mathematics, 160

(2004), 781–793: algoritmo AKS

E un algoritmo polinomiale che determina se n e primo in untempo polinomiale ∼ log11

2 n.

Dato un numero, AKS ci informa se ne esiste un divisore nonbanale. Se sı, sappiamo che esiste un fattore primo, ma non nesappiamo calcolare nessuno! Dunque AKS non risolve del tuttoil problema posto da Gauss perche non da la fattorizzazione.

Ad esempio, dato il numero di 700 cifre decimali

2607830780868022916308984891583983740019185236231188098180748811837301747567752972343601598430715445926120611346885459493819186339522276968732517825116797280831468531488413501914255924186919004485697212098055248894827232391934704186300241457051415102159089508470349648578019380333704378629883554897430746227580850721325853462541132778299346723917315981564028838315577754103949251018022445296387742757536413880007898514314394551834747323118699312218240749704240998824335321513431274346415243270989181522798350782776143117923784501643281377066102366283275427247656093327047332320535343869428339690920820103706172366146980656332645865182805428509313925437362888694972833255865000872790401925982193943935195803375472867585458086952845705993

In pochi passi di calcolo l’algoritmo AKS ci informa che ne esisteun divisore non banale. Pero l’ algoritmo AKS non ci dice cometrovare un tale divisore.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 29: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Nuove esigenze in crittografia

Nei cifrari classici la decifratura e simmetrica rispetto allacifratura sia da un punto di vista logico, sia da un punto divista computazionale.In particolare i sistemi crittografici classici riguardano loscambio di messaggi tra due soli utenti e sono basati sulloscambio di una chiave che consente cifratura e decifratura.Oggi invece c’e l’esigenza che possano comunicare fraloro piu soggetti che non si conoscono tra loro e che quindinon hanno avuto, in linea di principio, la possibilita discambiarsi chiavi private di cifratura.E pertanto indispensabile trovare nuovi, e piu sicuri,metodi per crittare i messaggi. Questo e l’obiettivo dellacrittografia a chiave pubblica.Paradossalmente, essa e basata proprio sulla difficolta dideterminare i fattori primi di numeri grandi.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 30: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Crittografia a chiave pubblica

Un cifrario a chiave pubblica permette di divulgare ilmetodo ed anche la chiave di cifratura, senza per questorivelare il modo di decifrare.

Infatti, per decifrare, e necessario essere in possesso diinformazioni aggiuntive oltre a quelle rese pubbliche.

Tali informazioni sono tenute segrete. Senza di loro lacomplessita di calcolo della decifratura e presumibilmentetale da renderne implausibile l’esecuzione.

L’idea su cui cio si basa e semplice: il sapere farefacilmente una certa operazione non implica che sappiamofare altrettanto facilmente anche l’operazione inversa.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 31: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Un paio di esempi

Si pensi all’elenco telefonico di una grande citta.E facile trovare il numero di una persona se neconosciamo il cognome, ma e in pratica impossibile risaliredal numero al cognome della persona.Si pensi ora di avere a disposizione due numeri primi p e qmolto grandi, e pressocche di eguale grandezza: p ∼ q.Il loro prodotto

n = pq ∼ p2 ∼ q2

e facile da calcolare, ed e ancora piu grande.D’altra parte, se conosciamo n, senza sapere che e ilprodotto di p e q, e ne cerchiamo i fattori primi con ilcrivello di Eratostene, saremo costretti ad effettuare circap ∼ q prove, il che richiede un tempo enorme, ed e inpratica impossibile da effettuare con gli attuali sistemi dicalcolo.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 32: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Il sistema RSA

E basato sulla difficolta di fattorizzare numeri con fattoriprimi grandi.Ideato da W. Diffie e M. E. Hellman (1976).Realizzato da L. M. Adleman, R. L. Rivest, A. Shamir delMassachusetts Institute of Technology (1978).

Applicazioni:

spedizione di messaggi cifrati tra innumerevoli utenti;autentica elettronica della firma;accesso ad archivi segreti o sistemi di sicurezza;accesso a servizi come carte di credito, programmitelevisivi a pagamento, telefonia cellulare, ecc.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 33: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Sensi unici e trappole

Da un punto di vista matematico, la realizzazione deicrittosistemi a chiave pubblica e basata sul concetto difunzione a senso unico.Si tratta in sostanza di una funzione biettiva definitamediante un calcolo facile da fare, ma tale che il calcolodella sua inversa risulta in pratica impossibile da effettuareperche la sua complessita e troppo grande.Si parla invece di funzione trappola se con qualcheinformazione aggiuntiva diventa computazionalmentefattibile effettuare anche il calcolo della inversa.Queste funzioni si usano per la cifratura in un sistema achiave pubblica.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 34: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Iscrizione al sistema RSA

Ci iscriviamo fornendo la nostra chiave pubblica dicifratura.La chiave e una coppia di numeri interi positivi (n,e), dove:n e prodotto di due numeri primi grandi p e q checonosciamo solo noi;e non ha fattori primi in comune con p − 1 e con q − 1.Per ogni utente U, la chiave (nU ,eU) viene pubblicata in unelenco di dominio pubblico.Non viene pero resa pubblica la fattorizzazione n = p · qche e il dato indispensabile per ottenere la chiave didecifratura.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 35: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Come funziona

Vogliamo inviare un messaggio a Beatrice, la cui chiave e(nB,eB) = (1003,3). Si ha

1003 = nB = pB · qB = 17 · 59

Supponiamo il messaggio consista del numero

P = 11

Cifriamo P mandando a Beatrice

C = PeB mod nB = resto della div. di PeB per nB

cioe

C = 328

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 36: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Come fa Beatrice a decrittare?

Sfruttando la sua conoscenza della fattorizzazione dinB = 1003, Beatrice determina, e tiene segreta, la chiaveper decrittare che e un numero dB tale che

(PeB)dB mod nB = P,per ogni numero P

Osservazione cruciale: determinare dB sostanzialmenteequivale a trovare la fattorizzazione di nB.In questo caso

dB = 619

e quindi

CdB = 328619 mod 1003 = 11

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 37: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Sicurezza del sistema RSA (I)

Nel 1977 Rivest, Shamir e Adleman sfidarono i lettori dellarivista Scientific American a decifrare un messaggio, il checorrispondeva a fattorizzare il numero a 129 cifre decimali:

11438162575788886766923577997614661201021829672124

23625625618429357069352457338978305971235639587050

58989075147599290026879543541

Cio secondo loro avrebbe richiesto un tempo enorme.Nel 1994 Arjen K. Lenstra riesce a trovare la soluzione(due fattori, uno con 64 e uno con 65 cifre decimali), con latecnica del crivello quadratico polinomiale multiplo.Per organizzare il lavoro, Lenstra ebbe bisogno di centinaiadi collaborazioni, impegnando per circa 48 ore molticalcolatori coordinati via Internet.Il messagio di Rivest, Shamir e Adleman non aveva sensocompiuto!

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 38: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Sicurezza del sistema RSA (II)

Pertanto: algoritmi di fattorizzazione piu efficienti ocomputer piu veloci (ad esempio il computer quantistico),possono mettere in pericolo i nostri sistemi di sicurezza.Un sistema ritenuto sicuro oggi puo non esserlo domani!

In particolare: se esistessero algoritmi polinomiali (tipol’AKS) per la fattorizzazione dei numeri, tutti i nostri sistemidi sicurezza sarebbero eludibili: la nostra organizzazionesociale sarebbe a rischio!

Quindi: c’e la necessita di nuove idee matematiche percreare sistemi crittografici piu sicuri. La ricerca in merito emolto attiva e usa strumenti algebrici e geometrici assairaffinati, come quelli usati da A. Wiles per dimostrarel’Ultimo Teorema di Fermat, ovvero idee della fisicaquantistica (crittografia quantistica).

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 39: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

L’Ultimo Teorema di Fermat

L’Ultimo Teorema di Fermat afferma che non esistono soluzioniintere positive all’equazione:

xn + yn = zn se n > 2.

L’ipotesi fu formulata da Pierre de Fermat (1601–1665) nel 1637.

Egli non fornı una dimostrazione, ma scrisse, ai margini di unacopia dell’Arithmetica di Diofanto (III–IV sec. d.C.):

Dispongo di una meravigliosa dimostrazione di questoteorema, che non puo essere contenuta nel marginetroppo stretto della pagina.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 40: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

La dimostrazione di A. Wiles

Una dimostrazione fu cercata da molti matematici per piudi 350 anni.Solo nel 1994 Andrew Wiles riuscı a trovarne una, cheutilizza idee algebrico–geometriche e raffinate tecnichemoderne certamente fuori della portata di Fermat.La dimostrazione di Wiles mette in luci sorprendentirelazioni dell’Ultimo Teorema di Fermat con la Ipotesi diRiemann e quindi con la distribuzione dei numeri primi.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 41: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

La Geometria Algebrica ...

... puo pensarsi come la naturale prosecuzione del camminointrapreso da R. Descartes (1596–1650) con l’introduzionedelle coordinate cartesiane.

Essa riguarda lo studio di curve, superficie, etc. descritte daequazioni algebriche.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 42: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Curve ellittiche

Sono le curve del piano i cui punti hanno coordinatecartesiane (x , y) che sono soluzioni di una equazione deltipo

y2 = x3 + ax + b

con x3 + ax + b = 0 avente tre soluzioni distinte.

Le curve ellittiche giocano un ruolo fondamentale nelladimostrazione di Wiles del Teorema di Fermat.

Si puo lavorare prendendo le coordinate in Zp, con pprimo.

In tal caso la curva ha un numero finito di punti: ci sonoalgoritmi (deterministici) per calcolarne il numero (cfr. R.Schoof) e algoritmi (probabilistici) per trovarne.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 43: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Legge di gruppo sulle curve ellittiche

Le curve ellittiche posseggono una operazione di addizione chele rende dei gruppi:

x

y

r

p+q

q

q�����

��������������

qq

p

q-

6

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 44: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Curve ellittiche e crittografia

Nel fare crittografia a chiave pubblica si sostituisce Z o Zncon una curva ellittica, sulla quale si puo operareaddizionando i punti, moltiplicandoli per numeri interi, etc.Il vantaggio e che si hanno molte curve ellittiche adisposizione, e se ne possono, ad esempio, utilizzarevarie, cambiando cosı chiave di crittaggio. Cio rende lacrittoanalisi molto piu problematica.Le curve ellittiche, e piu in generale curve algebriche,definite da equazioni del tipo

f (x , y) = 0

con f (x , y) polinomio in x e y , vengono usate anche inteoria dei codici, la disciplina che si occupa di correggeregli errori di trasmissione di dati su canali con disturbi ditrasmissione.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 45: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Cifrari di Vernam (one time pad)

Un cifrario inattaccabile:

p = p1p2 . . . pr messaggio binario in chiaro;k = k1k2 . . . kr la chiave, stringa binaria della stessalunghezza del messaggio, costituita da cifre casuali da nonutilizare MAI DUE VOLTE;la cifratura consiste nel sostituire il messaggio p colmessaggio c = c1c2 . . . cr dove:

ci = pi + ki mod 2, i = 1, . . . r .

Esempio:

p = 01001, k = 11010, c = 10011.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 46: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Il pregio della casualita

La casualita della chiave rende:

enorme la complessita della crittoanalisi;impossibile rintracciare il messaggio giusto p a partire dac.Esempio: A partire da c = 10011 tutti i messaggi in chiaro

00000, 00001, 00011, 00111, ecc.,

sono ugualmente probabili!

C. E. Shannon (1949) ha provato che ogni cifrarioinattaccabile e di questo tipo.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 47: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Il punto debole

Il tallone d’Achille di Vernam:

generazione delle chiavi;trasmissione della chiave: e un serpente che si mangia lacoda!la fisica quantistica supera quest’ultimo ostacolo econsente tale trasmissione (protocollo di C. H. Bennett-G.Brassard, 1984): questo e il campo della crittografiaquantistica di recente sviluppo.

M. W. Baldoni, C. Ciliberto, G. M. Piacentini Cattaneo,Aritmetica, crittografia e codici, Springer–Verlag Italia,2006.

M. W. Baldoni, C. Ciliberto, G. M. Piacentini Cattaneo, Unosguardo alla crittografia quantistica, Lettera MatematicaPRISTEM, 59 (2006), 22–34.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 48: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Conclusione

All’atto dell’unita d’Italia, Luigi Cremona (1830–1903),nominato professore di Geometria Superiorenell’Universita di Bologna esorta nella sua prolusione:

Respingete da voi, o giovani, le malevole parole di coloro che aconforto della propria ignoranza o a sfogo d’irosi pregiudizi vichiederanno con ironico sorriso a che giovino questi ad altri studi,e vi parleranno dell’impotenza pratica di quegli uomini che siconsacrano al progresso di una scienza prediletta.

Le molteplici e utilissime applicazioni della matematicateorica mostrano che oltre che ignoranza e pregiudizi,occorre combattere la scarsa lungimiranza dei detrattoridella cultura e della scienza pura.

Solo chi ha una solida cultura di base ed e padrone diraffinate teorie puo aspirare a sfruttare a fondo, in modoconsapevole e umano, i benefici della tecnologia.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria

Page 49: Sorprendenti applicazioni di Algebra e Geometria Il Futuro... · Essenzialmente c’e un unico algoritmo per ottenere questa` fattorizzazione: ilcrivello di Eratostene. Esso consiste

Il Premio Turing 2013 a Silvio Micali

Silvio Micali (Palermo, 1954)Professore presso il MIT di Boston

Laureato nel 1978 all’Universita di Roma, dove e statoallievo del prof. Corrado Bohm. Ha ottenuto il Ph.D. inInformatica presso l’Universita della California (UCLA) diBerkeley nel 1983.Le sue ricerche sono indirizzate all’uso di tecnichealgebriche e combinatoriche per la crittografia e lasicurezza informatica. Nel 2013 ha ricevuto il PremioTuring (il piu importante riconoscimento internazionale perl’informatica), insieme a Shafi Goldwasser.

Ciro Ciliberto, Universita di Roma Tor Vergata Sorprendenti applicazioni di Algebra e Geometria