Università di Roma “Tor Vergata”

Ingegneria informatica

Corso di Teoria elementare dei numeri

2 ottobre 2006 – 24 novembre 2006

Docente: Prof. René Schoof            Assistente: Burcu Baran

Corso chiuso

Esami precedenti

• Compito del 11 dicembre 2006: Compito corretto.
• Compito del 2 marzo 2007: 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.

News

• 22 maggio 2007: È stato Fattorizzato il 1039-esimo numero di Mersenne 2¹⁰³⁹-1.

Foto

• 9 novembre 2006: Foto1, Foto2, Foto3.

Programma

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

Materiale

• Software
  • GMP software for long integer arithmetic.
  • PARI/GP computer algebra system for doing fast computations in number theory. (version 2.2.11-α)
• 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.
  • Dan Bernstein's AWS 2006 Lecture Notes & Talk 1, Talk 2.
  • A. Zaccagnini e A. Languasco: Introduzione alla crittografia, Hoepli 2004.
• Note
  • Appunti sui numeri interi.
  • Appunti sui gruppi.
  • Nota sulla funzione φ di Eulero (3 pagine).
  • Espansioni decimali di 1/n (1 pagina).
  • Nota sulle radici primitive modulo p (2 pagine).

Esercizi

• 10 ottobre 2006: Foglio 1 (pdf)
• 18 ottobre 2006: Foglio 2 (pdf)
• 25 ottobre 2006: Foglio 3 (pdf)
• 2 novembre 2006: Foglio 4 (pdf)
• 12 novembre 2006: Foglio 5 (pdf)

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.)
• Metodo p – 1 (di Pollard)
  • p – 1 method web pages.
  • p – 1 method in Wikipedia.
• Primalità
  • Miller-Rabin Test in Wikipedia.
  • The Prime pages.
  • Articolo sulle test di primalità (21 pagine).
  • Test di Pocklington.
  • Due esempi del test di Pocklington.
  • 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.
  • Baby-step-Giant-step method.
  • Paper by Chris Studholme.
  • Esempio: calcolo di un logaritmo discreto (usando il metodo del calcolo dell'indice).
  • Record dicembre 2006.
  • Foto di Dan Shanks.
  • Canguri: J. Pollard: Monte Carlo methods for index computation (mod p), Math. Comp. 32 (1978). (7 pagine).
  • Diffie-Hellman key exchange.
• 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.
  • Elliptic curve factoring online
  • R. Brent: Factorization of the tenth Fermat number, Math. Comp. 68 (1999) 429–451. (pdf)
  • Foto di Hendrik Lenstra.
  • Foto di Peter Montgomery.
• Logaritmo discreto ellittico
  • Discrete logarithm on elliptic curves.
  • Elliptic curves and discrete logarithms in Google.
  • Certicom (Elliptic curve cryptography).
  • Certicom challenges.
• Test di primalità di Atkin
  • Elliptic curve primality proving web pages.
  • The Prime Pages.
  • Primo primality proving.
  • Some CM elliptic curves.
  • 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).
  • Foto di Carl Pomerance
  • La favola dei due crivelli.
  • Square roots modulo p. Algoritmo di Tonelli.
• 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.)
  • La fattorizzazione di RSA640.

Numerologia

• Numeri di Mersenne
  • Numeri di mersenne
  • 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.

Anni precedenti

• 2005-2006

Altro

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