Docente: Prof. René Schoof            Assistente: Antonella Perucca

Esami

• Prima di presentare un progetto è necessario fare un compito scritto sufficiente (sufficiente: voto ≥ 18).
  Il voto del compito vale per l'intero anno e non influenzerà il voto finale.
• Compito del 3 dicembre 2007: compito corretto.
• Compito del 18 febbraio 2008 : compito corretto.
• Compito del 11 giugno 2008 : compito corretto.
• Compito del 12 settembre 2008: compito corretto.

Progetti (più stelle = più difficile)

• Metodo delle curve ellittiche (prima fase, seconda fase).
• Logaritmo discreto (calcolo dell'indice).
• Crivello quadratico.
• Test di primalità di Atkin.
• Test di primalità ciclotomico (pdf).
• Crivello dei campi di numeri.

Programma

• Algoritmi per fattorizzare numeri ( Metodo ρ di Pollard, metodo p–1, crivello quadratico, metodo delle curve ellittiche)

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)
• Testi
  • R. Crandall and C. Pomerance: Prime Numbers (a computational perspective), Springer-Verlag 2002.
  • D. Knuth: The art of computer programming 2 (Seminumerical Algorithms), Addison-Wesley 1997.
  • A.K. Lenstra : Integer factoring.
  • Dan Bernstein's AWS 2006 Lecture Notes & Talk 1, Talk 2.
  • A. Zaccagnini e A. Languasco: Introduzione alla crittografia, Hoepli 2004.
• Applicazioni crittografiche
  • Joe Malkevitch: Mathematics and internet security.
  • Ronald van Luijk: Presentazione a Bogota.
• Note
  • Appunti sui numeri interi.
  • Nota sulla funzione φ di Eulero (3 pagine).
  • Appunti sui gruppi.
  • Espansioni decimali di 1/n (1 pagina).
  • Nota sulle radici primitive modulo p (2 pagine)
  • Nota sulla sommatoria Σ 1/p

Esercizi

• 4 ottobre 2007: Foglio 1 (pdf) (commenti pdf)
• 11 ottobre 2007: Foglio 2 (pdf) (commenti pdf)
• 20 ottobre 2007: Foglio 3 (pdf) (commenti pdf e pdf)
• 27 ottobre 2007: Foglio 4 (pdf) (commenti pdf)
• 16 novembre 2007: Foglio 5 (pdf) (commenti pdf)

Photos

• Foto 1, Foto 2.

Varie

• 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.)
• 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)
• 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).
• 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.
  • Factorizaciòn usando curvas elípticas online
  • Ecmnet.
  • Elliptic curve cryptography by Victor Miller, May 24, 2007.
  • 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.
  • Foto di Peter Montgomery.
• 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.
• 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.)

Numerologia

• I record
  • Factorization records.
• Numeri di Mersenne
  • Numeri di Mersenne
  • Numeri perfetti.
  • Più grande numero primo
  • Record 26 settembre 2006: M₄₄
  • GIMPS
• RSA
  • RSA
  • RSA demo
  • Sfide RSA
  • Fotos Rivest, Shamir, Adleman
  • È stato fattorizzato RSA640. Comunicato stampa RSA.
• News
  • 22 maggio 2007: È stato Fattorizzato il 1039-esimo numero di Mersenne 2¹⁰³⁹-1.
  • 31 agosto 2007: Il numero N = (2⁴²⁷³⁷+1)/3 è primo.

Anni precedenti e futuri

• 2005-2006
• 2006-2007
• 2008-2009

Altro

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