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
AVVISO
21 dicembre 2018: nuovo numero primo record: 282589933 -1
link
ORARIO
1o semestre: 24 settembre 2018 - 18 gennaio 2019.
LUNEDI
MARTEDI
MERCOLEDI
GIOVEDI
VENERDI
ore 9:30 - 11:15
Lezione
ore 14-16
Lezione
Ricevimento: dopo le lezioni in aula, per appuntamento, per e-mail. Il venerdi' dopo la lezione posso fermarmi presso gli edifici didattici.
PROGRAMMA
Obiettivi formativi: analizzare il funzionamento e la complessita' di vari algoritmi per la fattorizzazione di numeri interi e 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 1 ,
2 ,
3 ,
4 .
Testi di riferimento principali: R. Crandall and
C. Pomerance Prime Numbers. A computational perspective , Springer-Verlag 2002. L. Washington:
Elliptic Curves: Number Theory and and Cryptography, , Chapman and Hall /CRC 2003.
Prerequisiti: Calcolo modulo n . Vedi: Corso di Algebra e Logica (Laurea Triennale in Ing. Informatica) AL2015
ESAMI
L'esame consiste in un compito scritto e in un progetto.
Il voto del compito vale fino al 10 ottobre 2019. Chi fa lo scritto in settembre, si porti avanti col progetto per tempo.
Per partecipare agli scritti, è necessario iscriversi mediante il sito Delphi.
Portare un documento di riconoscimento.
Sessione invernale appello1: Risultati html Soluzioni pdf
appello2: Risultati JPG Soluzioni pdf
Sessione estiva :
appello3: giovedi' 27 giugno 2019, ore 10-12, aula B8
appello4: martedi' 16 luglio 2019, ore 10-12, aula B8
Sessione autunnale :
appello5: sabato 7 settembre 2019, ore 10-12, aula 5
appello6: venerdi' 20 settembre 2019, ore 10-12, aula G2C (SOGENE)
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.
Contare punti su curve ellittiche su campi finiti
Test di primalita' di Atkin.
ESERCIZI
Esercizi 2018-2019
Esercizi 2017-2018
Esercizi1 pdf
Esercizi2 pdf
Esercizi3 pdf
Esercizi4 pdf
Esercizi5 pdf
Esercizi6 pdf
Curve ellittiche in PARI/GP rtf
ECM fase 1: esempi rtf
ECM a carte scoperte rtf
Esercizi7 pdf
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...) pdf
Esercizi5 (curve ellittiche) pdf
Soluzioni pdf
Esercizi6 (logaritmo discreto in Z * p ) pdf
Soluzioni pdf
Esercizi7 (preliminari al crivello quadratico) pdf
Soluzioni pdf
MATERIALE
Software
GMP software for
long integer arithmetic.
PARI/GP
computer algebra system for doing fast computations in number theory.
PARI-DOC User's Guide to PARI/GP
GPTutorial1
GPTutorial2
SAGE software matematico (include PARI/GP)
Alpertron online
Testi
Articoli di carattere espositorio, conferenze
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.
Post-quantum Cryptography Winter School 2016 link
Phong Nguyen, Lattice based Cryptography talk
L'associazione nazionale di crittografia "De Componendis Cifris" link
Materiale per argomenti
RSA
R. Schoof , Fattorizzazione e criptosistemi a chiave pubblica,
Didattica delle Scienze 137 (1988), 48–54.
pdf A. Lenstra, J. Hughes, M. Augier, J. Bos, T. Kleinjung, C. Wachter , Ron was wrong, Whit is right, 2012 pdf
D. Boneh , Twenty Years of Attacks on the RSA Cryptosystem pdf
Fotos R ivest,
S hamir, A dleman
Primalità
Why prime numbers still fascinate mathematicians 2300 years later link 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
(Il test di Miller-Rabin si trova alle pp. 2–4).
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.)
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)
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.
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
(mini calcolo dell'indice) 1 , 2 , 3 , 4 .
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.
Espansioni decimali di 1/n .
Nota sul Teorema dei numeri primi di Chebyshev.
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 sull'algoritmo Baby-Step-Giant-Step per la risoluzione del logaritmo discreto su un gruppo ciclico.
Nota su esempi di applicazioni del logaritmo discreto alla crittografia.
Nota sul Crivello Quadratico.
Nota sulla sommatoria Σ 1/p.
Nota "smooth numbers estimates".
Nota sull'algoritmo di Shanks-Tonelli.
Nota sulle radici quadrate modulo p e modulo pk .
Nota sui test di primalita' di Pocklington and di Goldwasser-Kilian.
Nota sull'algoritmo di Cornacchia.
Nota sull'algoritmo di Cantor-Zassenhaus.
NUMEROLOGIA & VARIE
News
Electronic Frontier Foundation link
Numeri RSA link
21 dicembre 2018 : nuovo primo record
link
3 gennaio 2018 : nuovo primo record
link
link
7 gennaio 2016 :
New
Mersenne prime.
25 gennaio 2013 : Trovato nuovo primo di
Mersenne 257885161 -1 .
15 marzo 2011 : Nuovo
fattore di F17 .
8 marzo 2010 : Trovato fattore record con ECM. Vedi annuncio
3 febbraio 2010 : Fattorizzato F 14. Vedi annuncio
7 gennaio 2010 : Fattorizzato RSA-768. Vedi annuncio e
articolo
29 settembre 2008 :
Scoperto un numero primo con circa 13.000.000 di cifre
pdf .
31 agosto 2007 :
Il numero N = (242737 +1)/3 è
primo .
22 maggio 2007 : È stato fattorizzato il 1039-esimo numero di Mersenne 21039 -1 . Vedi
annuncio
26 settembre 2006 :
M44 2 novembre 2005 : E` stato fattorizzato
RSA640 .
primo records
Records di primalita'
GIMPS
Factoring Records
Fattori record trovati con ECM ECMNETproject
Il corso di Teoria Elementare dei Numeri
Altro
L'associazione BEST 
