Laurea Specialistica in Ingegneria Informatica
Anno Accademico 2017-2018

T e o r i a E l e m e nt are d e i N u m e r i

Laurea Specialistica, anno 1, crediti 6.

Appelli autunnali:

appello 1: 6 settembre 2018, ore 9:30-11:30, Aula T6 ( Ed. SOGENE qui )
appello 2: 20 settembre 2018, ore 10-12, Aula C4
Chi fa lo scritto in settembre, si porti avanti col progetto per tempo.

ORARIO

1^o semestre: 25 settembre 2017 - 22 dicembre 2017.

	LUNEDI	MARTEDI	MERCOLEDI	GIOVEDI	VENERDI
ore 9:30 - 11:15		Lezione Aula C5
ore 14-16					Lezione Aula C4

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
Foto 22/12/2017 1 2

Testo di riferimento principale: R. Crandall and C. Pomerance: Prime Numbers. A computational perspective, Springer-Verlag 2002.
Prerequisiti: Calcolo modulo n. Vedi: Corso di Algebra e Logica (Laurea Triennale in Ing. Informatica) AL2015 )

ESAMI

Il voto del compito vale fino al 10 ottobre 2018. 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.
Non sono consentiti libri, appunti ne' palmari.
Non è consentito uscire durante il compito.

Sessione invernale
appello1: Soluzioni pdf
appello2: Soluzioni pdf

Sessione estiva :
appello3: 19 giugno 2018, ore 10 - 12, aula B7
appello4: Soluzioni pdf

Sessione autunnale:

appello5: 6 settembre 2018, ore 9:30-12:30, Aula T6 ( Ed. SOGENE qui )

appello6: 20 settembre 2018, ore 10:00-12:00, Aula C4.

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 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

Alpertron Factorizaciòn usando curvas elípticas online

Testi

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.
A.K. Lenstra : Integer factoring, Designs, Codes and Cryptography, 19 (2000) 101-128.
Dan Bernstein's Integer factorization. Lecture Notes AWS 2006 pdf (57 pagine)
D. Knuth: The art of computer programming 2 (Seminumerical Algorithms), Addison-Wesley 1997.

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

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 Rivest, Shamir, Adleman
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 (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 Agrawal, Kayal, Saxena (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 “p – 1 ”

p – 1 method in Wikipedia.
p – 1 method web pages.

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.
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 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 p^k.
Nota "smooth numbers estimates".