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

1^o semestre: 29 settembre 2014 - 30 gennaio 2015.

• 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
  
  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) AL2011 )
  Il corso dell'anno scorso TEN 2013-14
  Foto 2015   

ESAMI

L'esame consiste in un compito scritto e in un progetto.
Per presentare il progetto è necessario aver fatto un compito scritto sufficiente (con voto almeno 18). Il voto del compito vale fino al 30 settembre 2015.

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.

• Appello 1: risultati html soluzioni pdf
• Appello 2: risultati html soluzioni pdf
  
  
• Attenzione: e' possibile usufruire di una sola delle due date di luglio 2015:
  
• Appello 3: risultati html soluzioni pdf
• Appello 3bis: martedi' 14 luglio 2015, ore 15-17, Aula C4
  
  
• Appello 4: mercoledi' 16 settembre 2015, ore 15-17, Aula T5 (edificio SOGENE)
• Appello 5: mercoledi' 30 settembre 2015, ore 17-19, Aula da determinare.

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

• Esercizi1 pdf
• Esercizi2 pdf
• Esercizi3 pdf
• Esercizi4 pdf
• Esercizi5 txt
• Curve ellittiche in pari/gp rtf
• Curve ellittiche in pari/gp2 rtf
• Curve ellittiche in pari/gp3 rtf
• Esercizi6 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...) rtf
• Esercizi5 (curve ellittiche) pdf   Soluzioni pdf
• 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
• 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 Factorizaciòn usando curvas elípticas online
• Tuts4you msieve

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) & Talk 1, Talk 2.
• D. Knuth: The art of computer programming 2 (Seminumerical Algorithms), Addison-Wesley 1997.

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
    
  • A. Lenstra, J. Hughes, M. Augier, J. Bos, T. Kleinjung, C. Wachter, Ron was wrong, Whit is right 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.)
    • BirthdayGrapher (solo per Mac) link
  • 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)
    • 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 p^k.
• Nota "smooth numbers estimates".

NUMEROLOGIA & VARIE

• News
  • Electronic Frontier Foundation link
  • 7 gennaio 2016: New Mersenne prime.
  • 25 gennaio 2013: Trovato nuovo primo di Mersenne 2^57885161-1.
  • 15 marzo 2011: Nuovo fattore di F₁₇.
  • 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 = (2⁴²⁷³⁷+1)/3 è primo.
  • 22 maggio 2007: È stato fattorizzato il 1039-esimo numero di Mersenne 2¹⁰³⁹-1. Vedi annuncio
  • 26 settembre 2006: M₄₄ e' primo.
  • 2 novembre 2005: E` stato fattorizzato RSA640. Comunicato stampa RSA.
  • primo records
  • Records di primalita'
  • Records di fattorizzazione.
  • GIMPS
• The Prime pages.
• Numeri di Carmichael
• Numeri di Mersenne
• Numeri perfetti
• Sito ufficiale RSA
• Sito Ufficiale certicom (ECC elliptic curve criptography)
• National Security Agency: The case for elliptic curve criptography link1 link2
• Government Computer News: giugno 2007

Il corso di Teoria Elementare dei Numeri

• TEN 2005-2006    2006-2007    2007-2008
• TEN 2008-2009    2009-2010    2010-2011    2011-2012    2012-2013    2013-2014
• Criptography - University of California - Berkeley spring 2009    spring 2010    spring 2012
• Cryptography, Dan Boneh, Stanford University: crypto I    crypto II






Altro

• L'associazione BEST per la promozione della mobilità degli studenti di Ingegneria in Europa.