Esami

Programma

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

Esercizi

• 30 ottobre 2008: Foglio 1.
•  6 novembre 2008: Foglio 2.
• 20 novembre 2008: Foglio 3.
• Pagina web Filippo Nuccio.

Materiale

• Software
  • GMP software for long integer arithmetic.
  • PARI/GP computer algebra system for doing fast computations in number theory. (version 2.2.11-α) or (version 2.03.01-β for Windows)
  • Factorizaciòn usando curvas elípticas online
• Testi
  • Richard Crandall and Carl Pomerance: Prime Numbers. A computational perspective, Springer-Verlag 2002.
  • 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.
  • Dan Bernstein's Integer factorization. Lecture Notes AWS 2006 pdf (57 pagine) & Talk 1, Talk 2.
  • Alessandro Zaccagnini e Alessandro Languasco: Introduzione alla crittografia, Hoepli 2004.
  • Joe Buhler and Peter Stevenhagen: Algorithmic Number Theory. Here is the book.
• 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.
  • I servizi segreti USA scelgono curve ellittiche: nsa, gcn.
  • Certicom tutorial.
• Note
  • Rabin Miller estimate (pdf, 2 pagine).
  • Nota sulla funzione φ di Eulero (3 pagine).
  • Espansioni decimali di 1/n (1 pagina).
  • Shanks-Tonelli (pdf, 1 pagina).
  • Cornachia's algorithm (pdf, 2 pagine).
  • Nota sulle radici primitive modulo p (2 pagine)
  • Nota sulla sommatoria Σ 1/p (2 pagine).

Materiale per argomenti

• Primalità
  • Miller– Rabin Test in Wikipedia.
  • The Prime pages.
  • Articolo sui test di primalità (21 pagine; Miller-Rabin sta sulle pp. 2–4).
  • Agrawal-Kayal-Saxena primality test in Wikipedia.
  • Foto Agrawal, Kayal, Saxena (Palo Alto, primavera 2004)
• Pollard ρ
  • John Pollard's home page.
  • 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.
• Metodo delle curve ellittiche
  • Curve Ellittiche in Wikipedia
  • Corso di Curve Ellittiche di Jim Milne.
  • 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.
• 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.
  • Foto di Oliver Atkin.
• Logaritmo discreto
  • Discrete logarithm web pages.
  • Il logaritmo discreto in Wikipedia.
  • ElGamal encryption in Wikipedia.
  • Baby-step-Giant-step method.
  • Foto di Dan Shanks.
  • J. Pollard: Monte Carlo methods for index computation (mod p), Math. Comp. 32 (1978). (Canguri, pdf, 7 p.).
  • Diffie-Hellman key exchange.
  • Paper by Chris Studholme.
  • Esempio: calcolo di un logaritmo discreto (usando il metodo del calcolo dell'indice).
• Il crivello quadratico
  • Quadratic Sieve web pages.
  • Il crivello quadratico in Wikipedia.
  • Esempio di fattorizzazione usando il crivello quadratico.
  • Another example
  • La fattorizzazione di RSA129 (1994).
  • Il crivello quadratico di Carl Pomerance.
  • La favola dei due crivelli di Carl Pomerance.
  • Foto di Carl Pomerance
  • Square roots modulo p. Algoritmo di Tonelli.
  • Da evitare: l'articolo di Landquist.
• Il crivello dei campi di numeri
  • Article by Peter Stevenhagen.
  • Number field sieve web pages.
  • Number field sieve in Wikipedia.
  • Esempio di una fattorizzazione usando NSF.
  • NFSNET
  • The development of the Number Field Sieve by A.K. Lenstra & H. W. Lenstra.
  • A.K. Lenstra, H.W. Lenstra, M.S. Manasse, J.M. Pollard: The factorization of the ninth Fermat number, Math. Comp. 61 (1993). (pdf, 32 p.)