Università degli Studi di Trento
Facoltà di Scienze Matematiche, Fisiche e Naturali
PROGETTO LAUREE SCIENTIFICHE 2005-6
LABORATORIO di NUMERI, CODICI, CRITTOGRAFIA
Se si chiede a uno studente delle superiori di trovare il massimo
comun divisore fra due numeri interi a e b, è facile che per prima cosa
pensi a fattorizzare a (e b), e quindi cominci a dividere il numero a per
2, per 3, per 5, ecc. Se questo va bene in linea di principio, si
vede subito che per numeri “grandi” il tempo richiesto, anche con
le più ottimistiche stime sulla potenza di calcolo disponibile,
diventa intollerabile. Invece un classico algoritmo, dovuto a
Euclide, è molto più rapido. La rapidità di un algoritmo si può
misurare in modo soddisfacente mediante la nozione di complessità, che
spiega anche perché preferiamo formule "chiuse" tipo n*(n+1)/2 a formule
"aperte" tipo 1 + 2 + ... + n. Il fatto che alcune operazioni matematiche,
molto semplici da fare, richiedano molto tempo per essere disfatte
è alla base di molti metodi crittografici effettivamente usati nella
pratica. Di alcuni di essi si riesce a dare una descrizione
ragionevolmente completa, basata su un’idea di Gauss, quella del calcolo
dei resti. È una cosa con cui abbiamo già una familiarità giornaliera:
se il mio orologio fa le 10, so che fra 5 ore farà le 3; per fare
questo ho sommato 10 + 5 = 15, e poi ho preso il resto della divisione
per 12. Questa semplicissima idea è alla base del famoso metodo RSA
di crittografia a chiave pubblica. Fra gli argomenti che verranno trattati
in questo laboratorio vi sono la scomposizione di un numero in fattori
primi, i test di verifica di primalità, l’algoritmo di Euclide, la
complessità di algoritmi su numeri interi, la crittografia, la teoria
dei numeri, in particolare il metodo RSA, e si imparerà a giocare a
testa o croce per telefono, utilizzando un teorema scoperto dai matematici
cinesi oltre 1700 anni fa.
Gruppo di lavoro - Istituti Scolastici
Andrea Caranti (Università degli studi di Trento),
Sandro Mattarei (Università degli studi di Trento),
Willem de Graaf (Università degli studi di Trento),
Marco Galvan (SSIS),
Lorenza Zeni (Liceo “Galilei”-Trento),
Franca Bosetti (Liceo “Galilei”-Trento),
Antonella Frisanco (I.T.I. “Buonarroti” – Trento),
Antonella Rigon (I.T.I. “Buonarroti” – Trento),
Fernanda Piffer (I.T.I. “Marconi” – Rovereto),
Giorgio Pavana (I.T.I. “Marconi” – Rovereto),
Antonella Ceccato (Liceo “Brocchi” – Bassano),
Amedeo Alfine (Liceo “Brocchi” – Bassano),
Stelvio Andreatta (Liceo “Brocchi” – Bassano),
Ettore Brunello (Liceo “Brocchi” – Bassano).
accesso alla documentazione online
indietro ...