Università di Roma “Tor Vergata”

Dipartimento di Matematica

Crittografia

2 marzo 2010 – 4 giugno 2010

Docente: Prof. René Schoof

Programma

• Presentiamo algoritmi per risolvere problemi computazionali che sono rilevanti per la crittografia odierna.
• Discuteremo: test di primalità, algoritmi di fattorizzazione, curve ellittiche su campi finiti, metodi per calcolare logaritmi discreti.
• Prerequisiti: i corsi di geometria e algebra del primo anno.

Esami

• 28 giugno 2010, primo compito: compito corretto.
• 13 luglio 2010, secondo compito. compito corretto.
• 21 settembre 2010, terzo compito. compito corretto.
• 11 ottobre 2010, quarto compito.

Esercizi

• 10 marzo 2010: Foglio 1.
• 23 marzo 2010: Foglio 2.
• 28 marzo 2010: Foglio 3.
• 26 aprile 2010: Foglio 4.
• 19 maggio 2010: Foglio 5.

Materiale

• Software
  • GMP software for long integer arithmetic.
  • PARI/GP computer algebra system for doing fast computations in number theory.
  • Sage Notebook.
  • Factorizaciòn usando curvas elípticas online
• Testi
  • Richard Crandall and Carl Pomerance: Prime Numbers. A computational perspective, Springer-Verlag 2002.
  • Joe Buhler and Peter Stevenhagen: Algorithmic Number Theory.
  • Daniele Venturi: Lecture Notes on Algorithmic Number Theory, 2009.
  • Donald Knuth: The art of computer programming 2 (Seminumerical Algorithms), Addison-Wesley 1997.
  • Arjen Lenstra : Integer factoring, Designs, Codes and Cryptography, 19 (2000) 101-128.
  • Alessandro Zaccagnini e Alessandro Languasco: Introduzione alla crittografia, Hoepli 2004.
• Crittografia
  • 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)
  • René Schoof, Fattorizzazione e criptosistemi a chiave pubblica, Didattica delle Scienze 137 (1988), 48–54. (pdf)
    
  • Victor Miller: Elliptic curve cryptography. Presentazione, 24 maggio 2007.
  • History of cryptography, course by John Voight, UVM Fall 2009.
  • I servizi segreti USA scelgono curve ellittiche: nsa, gcn.
  • Corso di Giuseppe Italiano (Facoltà di Ingegneria, Tor Vergata).
  • Certicom tutorial.
• Note
  • Proof of the weak prime number theorem.
  • Nota sui campi finiti.
  • Nota sui numeri di Fermat e Mersenne.
  • Nota sulla sommatoria Σ 1/p (2 pagine).
  • Cornachia's algorithm (pdf, 2 pagine).
• Notizie
  • Mersenne forum.
  • RSA768: record 7 gennaio 2010.
  • F₁₄ factored! 3 febbraio 2010.
  • ECM record 8 marzo 2010.

Materiale per argomenti

• Primalità
  • Miller– Rabin Test in Wikipedia.
  • Rabin Miller estimate (pdf, 2 pagine).
  • The Prime pages.
  • Articolo sui test di primalità (21 pagine; contiene Miller-Rabin e AKS).
  • Agrawal-Kayal-Saxena primality test in Wikipedia.
  • Foto Agrawal, Kayal, Saxena (Palo Alto, primavera 2004)
• Pollard ρ
  • John Pollard's home page and computer.
  • Pollard ρ web pages.
  • Pollard ρ in Wikipedia.
  • J. Pollard and R. Brent: Factorization of the eighth Fermat number, Math. Comp. 36 (1980). (pdf, 4 p.)
• Metodi “p – 1 ”
  • p – 1 method web pages.
  • p – 1 method in Wikipedia.
  • Test di primalità di Pocklington.
  • Due esempi del test di Pocklington.
• Curve ellittiche
  • Curve Ellittiche in Wikipedia
  • Corso di Curve Ellittiche di Jim Milne.
  • Counting points with the baby-step-giant-step method.
  • Elliptic curve method web pages.
  • Metodo delle curve ellittiche in Wikipedia.
  • Ecmnet.
  • R. Brent: Factorization of the tenth Fermat number, Math. Comp. 68 (1999) 429–451. (pdf)
  • P. Zimmerman: Miglioramenti del metodo delle curve ellittiche. (April 2003)
  • Foto di Hendrik Lenstra.
  • Elliptic curve primality testing in Wikipedia.
• Logaritmo discreto
  • Discrete logarithm web pages.
  • Il logaritmo discreto in Wikipedia.
  • ElGamal encryption in Wikipedia.
  • Shanks' Baby-step-Giant-step method.
  • Diffie-Hellman key exchange.
  • Paper by Chris Studholme.
  • Esempio: calcolo di un logaritmo discreto (usando il metodo del calcolo dell'indice).
• Test di primalità di Atkin
  • Elliptic curve primality proving web pages.
  • The Prime Pages.
  • Primo primality proving.
  • Some CM elliptic curves. Some more.
  • Esempio di un test di Atkin.
• Numerologia
  • I numeri di Mersenne.
  • Il test di Lucas- Lehmer.
  • I numeri perfetti.
  • Numeri di Mersenne in Time magazine.
  • I numeri di Fermat.
  • Il test di Pépin.
  • Il quinto numero di Fermat non è primo ( Euler 1732).
  • Poligoni regolari costruibili.