Università di Roma “Tor Vergata”

Dipartimento di Matematica

Teoria elementare dei numeri

28 settembre 2015 - 23 gennaio 2016

Docente: Prof. René Schoof

Corso chiuso

Programma

• Obiettivi formativi: analizzare il funzionamento e la complessità 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:
  • Primalità e fattorizzazione: complessità a confronto, criptosistema RSA, test di primalità di Miller-Rabin;
  • Algoritmi per fattorizzare numeri: Metodo ρ di Pollard, metodo p–1, metodo delle curve ellittiche, crivello quadratico;
  • Logaritmo discreto: Diffie-Hellman key exchange, Baby-step-Giant-Step, calcolo dell'indice.
  • Certificati di primalità: criterio di Pocklington, algoritmo di Goldwasser-Kilian.

Esami

• Mercoledì 14 settembre 2016: compito scritto, 10:00 Aula L3, Sogene.
• L'esame consiste in un compito scritto e 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 2017.
• Portare un documento di riconoscimento.
  Non sono consentiti libri, appunti o palmari.
  Non è consentito uscire durante il compito.

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.
• Logaritmo discreto per campi finiti di piccola caratteristica.
• Contare punti su curve ellittiche su campi finiti.
• Test di primalita' di Atkin.

Esercizi vari

• Esercizi1 pdf
• Esercizi2 pdf
• Esercizi3 pdf
• Esercizi4 pdf
• Esercizi5 txt
• Esercizi6 pdf
• Esercizi1 (complessita') pdf
• Esercizi2 (numeri primi, numeri B-smooth) pdf
• Esercizi3 (gruppi, anelli, campi) pdf (vedi anche pdf
• Esercizi4 (esercizi con PARI/GP, in aggiornamento...) rtf
• Esercizi5 (curve ellittiche) pdf
• Esercizi6 (logaritmo discreto in Z^*_p) pdf
• Esercizi7 (crivello quadratico) pdf
• Esercizi8 (criterio di Pocklington) 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.)
  • 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.
    • 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".