Università di Roma “Tor Vergata”

Ingegneria informatica

Corso di Teoria elementare dei numeri

3 ottobre 2005 – 25 novembre 2005

Docente: Prof. René Schoof

Corso chiuso

Programma

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

Esami

• 29 settembre 2006 (Ultimo appello!): Prenotazione chiusa.

  Div

  • Foto 17-11-2005.
  • Foto1, Foto2, Foto3 18-11-2005.
  • Numeri da fattorizzare.
  • Numeri di Bernoulli.
  • Conclave Obscurum.

  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.
    • J. von zur Gathen and J. Gerhard: Modern computer algebra, Cambridge University Press 2000.
    • A. Zaccagnini e A. Languasco: Introduzione alla crittografia, Hoepli 2004.
  • Note
    • Nota sulla funzione φ di Eulero (3 pagine).
    • L'espansione decimale di 1/n (1 pagina).
    • Nota sulle radici primitive modulo p (2 pagine).
    • Nota sulla sommatoria di 1/p (3 pagine).

  Varie

  • Ultim'ora!! (Settembre 2006) Il più grande numero primo noto.
  • 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.
  • Numeri di Mersenne
    • Numeri di mersenne
    • Più grande numero primo
    • GIMPS
  • RSA
    • Fattorizzazione di RSA640. Comunicato stampa RSA.
    • RSA
    • RSA demo
    • Sfide RSA
    • Foto Rivest, Shamir, Adleman
  • Primalità
    • The Prime pages.
    • Articolo sulle test di primalità (21 pagine).
    • Test di Pocklington.
    • Due esempi del test di Pocklington.
    • Foto Agrawal, Kayal, Saxena (Palo Alto, primavera 2004)
  • Il crivello quadratico
    • Quadratic Sieve web pages.
    • Il crivello quadratico in Wikipedia.
    • Esempio di fattorizzazione usando il crivello quadratico.
    • La fattorizzazione di RSA129 (1994).
    • Foto di Carl Pomerance
    • Square roots modulo p. Algoritmo di Tonelli.
  • Logaritmo discreto
    • Discrete logarithm web pages.
    • Il logaritmo discreto in Wikipedia.
    • Calcolo di un logaritmo discreto usando index calculus.
    • Baby-step-Giant-step method.
    • Foto di Dan Shanks.
    • Index calculus by Lamacchia and Odlyzko
    • Canguri (18 pagine).
  • 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.
    • Esempio di una fattorizzazione usando ecm.
    • Distribuzione delle curve ellittiche per p = 1000003.
    • Elliptic curve factoring online
    • Foto di Hendrik Lenstra.
  • Test de 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.
  • Crivello dei campi di numeri
    • Number field sieve web pages.
    • Number field sieve in Wikipedia.
    • NFSNET
    • 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.)

  Esercizi

  • 9 ottobre 2005: 1^o Foglio. (pdf)
  • 16 ottobre 2005: 2^o Foglio. (pdf)
  • 24 ottobre 2005: 3^o Foglio. (pdf)
  • 10 novembre 2005: 4^o Foglio. (pdf)
  • 14 novembre 2005: 5^o Foglio. (pdf)

  Altro

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