T e o r i a E l e m e n t a r e d e i
N u m e r i
Laurea Specialistica, anno 1, crediti 6.
Docente:
Laura Geatti
Quando avete deciso, fatemi sapere quale progetto scegliete. Magari mettetevi d'accordo: non implementate tutti lo stesso algoritmo.
Appello 4 : risultati html soluzioni pdf
ORARIO
2o semestre: 3 marzo - 28 giugno 2014.
LUNEDI
MARTEDI
MERCOLEDI
GIOVEDI
VENERDI
ore 9:30 - 11
Lezione
ore 16-18
Lezione
Ricevimento: Giovedi' ore 16-17:30, ufficio Geatti, oppure dopo le lezioni, per appuntamento, per e-mail.
Foto1 JPG
Foto2 JPG
Foto3 JPG
Foto4 JPG
Foto5 JPG
Foto6 JPG
Foto7 JPG
Foto8 JPG
PROGRAMMA
Obiettivi formativi: analizzare il funzionamento e la complessita' di vari algoritmi per la fattorizzazione di numeri interi o per la risoluzione del logaritmo discreto. Tali algoritmi sono gli ''antagonisti'' di diversi criptosistemi attualmente in uso. Argomenti:
Primalita' e fattorizzazione: complessita' a confronto, criptosistema RSA, test di primalita' di Miller-Rabin; Algoritmi per fattorizzare numeri: Metodo ρ di Pollard, metodo p–1, metodo delle curve ellittiche, crivello
quadratico; Logaritmo discreto: Baby-step-Giant-Step, calcolo dell'indice. Certificati di primalita': criterio di Pocklington, algoritmo di Goldwasser-Kilian. Programma dettagliato & Diario delle lezioni Testo di riferimento principale:
R. Crandall and
C. Pomerance Prime Numbers. A
computational perspective , Springer-Verlag 2002.
Prerequisiti: Corso di Algebra e Logica (Laurea Triennale in Ing. Informatica) AL2011 TEN 2012-13
ESAMI
L'esame consiste in un compito scritto e in un progetto.
Per partecipare agli scritti, è necessario iscriversi mediante il sito Delphi.
Portare un documento di riconoscimento.
Appello 1 : soluzioni pdf risultati html Appello 2 : Venerdi' 18 luglio, ore 10 - 12, Aula C4 (Edificio Didattico).
Appello 3 : martedi' 2 settembre, ore 10 - 12, Aula 2.
Appello 4 : risultati html soluzioni pdf
Attenzione: e' possibile usufruire di una sola delle due date di febbraio 2015:
Appello 5:
Appello 5bis:
Progetti (gruppi di due persone al massimo)
(più stelle = più difficile)
Metodo delle curve ellittiche (prima fase, seconda fase).
Logaritmo discreto (calcolo dell'indice).
Crivello quadratico.
Test di primalita' di Atkin.
ESERCIZI
Esercizi 2013-2014
Esercizi svolti
Esercizi1 (complessita') pdf Soluzioni pdf
Esercizi2 (numeri primi, numeri B-smooth) pdf Soluzioni pdf
Esercizi3 (gruppi, anelli, campi) pdf (vedi anche pdf e soluzioni pdf )
Esercizi4 (esercizi con PARI/GP, in aggiornamento...) rtf
Esercizi5 (curve ellittiche) pdf
Soluzioni pdf Curve ellittiche in pari/gp rtf
Esercizi6 (logaritmo discreto in Z * p ) pdf
Soluzioni pdf
Esercizi7 (crivello quadratico) pdf
Soluzioni pdf
Esercizi8 (criterio di Pocklington) pdf
Soluzioni pdf Esempio pdf
MATERIALE
Software
Testi
Articoli di carattere espositorio, conferenze
Ronald van Luijk : Number theory in cryptography
Presentazione, Universidad de los Andes, Bogota, settembre 2006.
Joe Malkevitch : Mathematics and internet security, Feature column of Am. Math. Soc., April 2006 link
L. Adleman :
conferenza all'ACM per il premio Turing 2002.
Victor Miller : Elliptic curve cryptography. Presentazione,
24 maggio 2007.
Carl Pomerance : Elliptic curves: applications and problems; conferenza
First Abel Conference, Univ. of Minnesota , January, 3-5 2011.
Materiale per argomenti
RSA
R. Schoof , Fattorizzazione e criptosistemi a chiave pubblica,
Didattica delle Scienze 137 (1988), 48–54.
pdf S. Robles , The RSA cryptosystem,
pdf Fotos R ivest,
S hamir, A dleman
Primalità
Stime sulla distribuzione dei numeri primi link
Il test di primalita' di Miller –
Rabin
su
Wikipedia .
Il test di primalita' di Agrawal-Kayal-Saxena in
Wikipedia .
R. Schoof , Four primality testing algorithms,
“Algorithmic number theory”
MSRI Publications 44 ,
Cambridge University Press 2008, 101–126.
pdf Criterio di Pocklington in
Wikipedia .
Algoritmo di Goldwasser-Kilian in
Wikipedia .
S.Goldwasser, J. Kilian , Primality Testing Using Elliptic Curves, Journal of the ACM, Vol.46, N.4, July 1999, pp.450-472 pdf
ECPP records PRIMO
Foto A grawal,
K ayal, S axena (Palo Alto, primavera 2004)
Fattorizzazione
Pollard ρ
Pollard ρ in
Wikipedia .
Pollard ρ web pages.
J. Pollard and R. Brent :
Factorization of the eighth Fermat number, Math. Comp. 36
(1980). (pdf , 4 p.)
BirthdayGrapher (solo per Mac) link
Metodo delle curve ellittiche
Curve Ellittiche in
Wikipedia
H. Lenstra :
Factoring integers with elliptic curves, Annals of Math. 126 , (1987) 649-673 pdf (l'introduzione e' chiara e accessibile)
William Stein , Elementary Number Theory, Ch.6 pdf R. Brent :
Factorization of the tenth Fermat number, Math. Comp. 68
(1999) 429–451. (pdf )
Metodo delle curve ellittiche in
Wikipedia .
Elliptic curve method web pages.
Elliptic Curve Tutorial di certicom link
P. Zimmerman :
The elliptic curve method. (April 2003)pdf
Ecmnet. Foto di Hendrik Lenstra.
Foto di Peter Montgomery.
Il crivello quadratico
Il crivello quadratico in
Wikipedia .
Carl Pomerance , Smooth numbers and the quadratic sieve, pdf .
Carl Pomerance , A tale of two sieves, pdf (La favola dei due crivelli).
La fattorizzazione di RSA129 (1994)
txt .
Esempio di fattorizzazione usando il crivello quadratico txt Spiegazione
pdf
Un altro esempio pdf Spiegazione
pdf
Radici quadrate modulo p . Algoritmo di Shanks-Tonelli
txt .
L'algoritmo di Shanks-Tonelli in Wikipedia .
Il Lemma di Hensel in Wikipedia .
Foto di Carl Pomerance
Logaritmo discreto
Il logaritmo discreto in Wikipedia .
Discrete logarithm web pages.
C. Pomerance : Elementary thoughts on discrete logarithms, “Algorithmic number theory”
MSRI Publications 44 ,
Cambridge University Press 2008, pdf .
Chris Studholme , The discrete log problem, june 2002,
pdf
Baby-step-Giant-step method in Wikipedia.
J. Pollard :
Monte Carlo methods for index computation (mod p), Math. Comp. 32
(1978). (Canguri, pdf , 7 p.).
Esempio di calcolo di un logaritmo discreto
(usando il metodo del calcolo dell'indice)txt .
Il logaritmo discreto sulle curve ellittiche
CerticomTutorial
Diffie-Hellman-Merkle key exchange in Wikipedia .
El Gamal
encryption in Wikipedia .
Foto di Dan Shanks
Foto di Taher ElGamal
Foto di Ralph Merkle, Martin Hellman, Whit Diffie.
Note
nota1 Aritmetica sui numeri interi.
nota2 Gruppi, anelli, campi e applicazioni.
Nota
sui gruppi abeliani finiti.
Nota sulla funzione φ di Eulero.
Nota sul metodo ρ di Pollard.
Nota sul metodo p-1 di Pollard.
Nota sul metodo delle curve ellittiche.
Nota
sulle radici primitive modulo p .
Nota sul "calcolo dell'indice" per la risoluzione del logaritmo discreto in Z p * .
Nota su esempi di applicazioni del logaritmo discreto alla crittografia.
Espansioni decimali di 1/n .
Nota sulla sommatoria Σ 1/p.
Nota sul Crivello Quadratico.
Nota sull'algoritmo di Shanks-Tonelli.
Nota sulle radici quadrate modulo p e modulo pk .
Nota "smooth numbers estimates".
NUMEROLOGIA & VARIE
Il corso di Teoria Elementare dei Numeri
Altro
L'associazione BEST 
