Liceo Scientifico “Immacolata” di Pinerolo
Mercoledì 18 dicembre 2013
IMI-MATH ++
Numeri primi e milioni di dollari
Numeri primi e sicurezza su Internet
Il metodo
RSA
(1978)
(si basa sulla “difficoltà” di scomporre in fattori primi)
Adi Shamir
Ron Rivest
Leonard Adleman
E’ così difficile
scomporre in fattori primi?
11.639 = ???
11.639 = 103 · 113
E’ così difficile
scomporre in fattori primi?
Due problematiche:
1) Trovare metodi rapidi di fattorizzazione
(ne esistono centinaia…)
2) Sapere se un numero è primo oppure no
(i cosiddetti “test di primalità”)
Decifrare un messaggio segreto
A=2
B=3
C=5
D=7
E = 11
F = 13
G = 17
H = 19
I = 23
L = 29
M = 31
N = 37
O = 41
P = 43
Q = 47
R = 53
S = 59
T = 61
U = 67
V = 71
Z = 73
3604
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
Distribuzione dei numeri primi
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
…..
I numeri primi sono infiniti
(Euclide III sec. a.C.)
La loro distribuzione “sembra” casuale
La loro distribuzione nasconde
un sacco di curiosità
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
La congettura dei primi “gemelli”
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
…..
Esistono infinite coppie di numeri
primi “gemelli” (cioè la cui differenza
è uguale a 2) ?
Boh !
(questo non è un teorema, bensì una congettura:
i matematici ci stanno lavorando da millenni…ma
ancora non hanno raggiunto una dimostrazione
della sua verità o falsità)
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
La congettura di Bertrand (1845)
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
…..
Fra un numero n e il suo doppio 2n
esiste sempre almeno un numero
primo?
Sì !
questo è un teorema: il teorema di Bertrand.
Dimostrato in vari modi diversi da vari grandi
matematici fra i quali il russo Chebychev (nel 1850),
l’indiano Ramanujan (nel 1917) e l’ungherese
Erdos (nel 1932)
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
La congettura di Legendre (1830 circa)
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
…..
Fra due quadrati perfetti successivi
n2 e (n+1)2
esiste sempre almeno un numero
primo?
Congettura aperta…
Strane “razze” di numeri primi…
• I numeri primi di Fermat
• I numeri primi di Mersenne
I numeri primi di Fermat
Un numero si dice “di Fermat” se è del tipo:
I più piccoli numeri di Fermat sono:
I numeri di Fermat sono tutti primi?
No, ad esempio F5 non lo è
Pierre
de Fermat
“il principe dei
dilettanti”
(1601-1665)
Esistono altri primi del tipo “di Fermat” più grandi di 65.537 ?
Nessuno li ha ancora trovati ma neppure dimostrato che non ne esistano!
I numeri primi di Mersenne
Un numero si dice “di Mersenne” se è del tipo:
I più piccoli numeri di Mersenne sono:
Padre Marin
Mersenne
(1588-1648)
Scrivi i seguenti numeri di Mersenne….
Sono tutti primi?
Prova a formulare una congettura: quali sono i numeri
di Mersenne primi?
I numeri primi di Mersenne
Un po’ di risposte…
• I numeri di Mersenne non sono tutti primi
(se n non è primo anche 2n-1 non lo è)
• Congettura: se n è primo allora anche 2n-1 è primo
• La congettura è falsa: 211-1 non è primo !
Great Internet Mersenne
Prime Search
• Allo stato attuale non si sa se i numeri di Mersenne primi sono infiniti!
Ne sono stati trovati 47, il più grande dei quali (trovato nell’agosto 2008
all’Università della California, grazie al sistema GIMPS) è 243.112.609-1
e contiene quasi 13 milioni di cifre.
Tieni presente che
un quotidiano
contiene meno di 1
milione di lettere
Come guadagnarsi fama immortale…
1) Dimostrare (o confutare) la congettura dei
primi gemelli
2) Dimostrare (o confutare) la congettura di
Legendre
3) Rispondere alla domanda: ci sono infiniti primi
di Fermat?
4) Rispondere alla domanda: ci sono infiniti primi
di Mersenne?
5) Trovare un numero primo maggiore
del “mostro” 243.112.609-1
Buon lavoro
e….auguri !
…dove cercare un po’ di news
aggiornate sui numeri primi?
Ad esempio sul sito (in inglese):
http://primes.utm.edu/largest.html
Prossimo appuntamento
GIOVEDI 30 GENNAIO 2014
Scommettiamo che il Toro vince lo Scudetto?
Scommesse e calcolo delle probabilità
Il metodo di fattorizzazione di Fermat
Devo fattorizzare il numero n = 987
x
30
31
32
33
34
35
36
37
x2
900
961
1024
1089
1156
1225
1296
1369
1) Cerco il più piccolo quadrato perfetto x2 maggiore di n
2) Controllo se x2-n è a sua volta un quadrato
1024 – 987 = 37 no
3) Riprovo con quadrati via via più grandi
1089 – 987 = 102 no
Pierre
1156 – 987 = 169 sì 169 = 132
de Fermat
4) Inizio la scomposizione:
(1601-1665)
1156 – 987 = 169
cioè
987 = 1156 – 169 = 342 – 132 = (34 + 13)·(34 - 13) = 47 · 21 = 47 · 7· 3
Il metodo di fattorizzazione di Fermat
Problema:
fattorizzare 2.457
2.457 = 2601 – 144 =
512 – 122 =
(51 + 12)·(51 -12) =
63 · 39 =
7 ·32·13·3 = 7 ·33·13
x
46
47
48
49
50
51
52
53
x2
2116
2209
2304
2401
2500
2601
2704
2809