Laurea Specialistica in Ingegneria Informatica
Anno Accademico 2012-2013

T e o r i a   E l e m e nt are   d e i  N u m e r i

Docente: Laura Geatti

CORSO CHIUSO

ORARIO

Laurea Specialistica, anno 1, crediti 6.
1 ^o semestre : 1 ottobre 2012 - 2 febbraio 2013.
 

	LUNEDI	MARTEDI	MERCOLEDI	GIOVEDI	VENERDI
16 - 17,45	Lezione   Aula B12 Ed. Did.	Lezione   Aula B12 Ed. Did.

Ricevimento: dopo la lezione in aula, durante il corso.
Per e-mail oppure su appuntamento, dopo la fine del corso.
(Ufficio Geatti: Dipartimento di Matematica - Studio 0122, telefono: 72594628 -Edificio Sogene, Piano terra, dente 1: qui )

PROGRAMMA

Primalita' e fattorizzazione: complessita' a confronto, criptosistema RSA, test di primalita' di Miller-Rabin;
Algoritmi per fattorizzare numeri: Metodo ρ di Pollard, metodo p–1, metodo delle curve ellittiche, crivello quadratico;
Logaritmo discreto: Baby-step-Giant-Step, calcolo dell'indice.
Certificati di primalita': criterio di Pocklington, algoritmo di Goldwasser-Kilian.
Programma dettagliato     Diario delle lezioni

Testo di riferimento principale: R. Crandall and C. Pomerance: Prime Numbers. A computational perspective, Springer-Verlag 2002.

Prerequisiti: Corso di Algebra e Logica (Laurea Triennale in Ing. Informatica) AL2011

ESAMI

L'esame consiste in un compito scritto e in un progetto.
Per presentare il progetto è necessario aver fatto un compito scritto sufficiente (con voto almeno 18).
Il voto del compito vale fino alla sessione di febbraio 2014.

Per partecipare agli scritti, è necessario iscriversi mediante il sito Delphi.
Portare un documento di riconoscimento.
Non sono consentiti libri o appunti.
Non è consentito uscire durante il compito.

• Appello 1: Soluzioni pdf
• Appello 2: Testo pdf

Progetti (gruppi di due persone al massimo) (più stelle = più difficile)

• Metodo delle curve ellittiche (prima fase, seconda fase).
• Logaritmo discreto (calcolo dell'indice).
• Crivello quadratico.
• Test di primalita' di Atkin.

ESERCIZI

Esercizi 2012-2013

• Esercizi1 (argomenti delle prime tre settimane) pdf
• Esercizi2 (argomenti della quarta e quinta settimana) pdf
• Esercizi3 (argomenti della sesta settimana) pdf
• EserciziGP (esercizi con PARI/GP) rtf Esempio1-Pollard txt Esempio2-FakePollard txt
• Esercizi4 (gruppi) pdf
• Esercizi5 (curve ellittiche) pdf

Esercizi svolti

• Esercizi1 (complessita') pdf   Soluzioni pdf
• Esercizi2 (numeri primi, numeri B-smooth) pdf   Soluzioni pdf
• Esercizi3 (gruppi, anelli, campi) pdf (vedi anche pdf e soluzioni pdf )
• Esercizi4 (esercizi con PARI/GP, in aggiornamento...) rtf
• Esercizi5 (curve ellittiche) pdf   Soluzioni pdf    Curve ellittiche in pari/gp rtf
• Esercizi6 (logaritmo discreto in Z^*_p) pdf   Soluzioni pdf
• Esercizi7 (crivello quadratico) pdf   Soluzioni pdf
• Esercizi8 (criterio di Pocklington) pdf   Soluzioni pdf    Esempio pdf

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)
• PARI-DOC User's Guide to PARI/GP   GPTutorial1    GPTutorial2
SAGE software matematico (include PARI/GP)
• Alpertron Factorizaciòn usando curvas elípticas online
• Tuts4you msieve
Testi
• R. Crandall and C. Pomerance: Prime Numbers. A computational perspective, Springer-Verlag 2002.
• L. Washington: Elliptic Curves: Number Theory and and Cryptography, , Chapman and Hall /CRC 2003.
• A.K. 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.
• A. Zaccagnini e A. Languasco: Introduzione alla crittografia, Hoepli 2004.
• D. Knuth: The art of computer programming 2 (Seminumerical Algorithms), Addison-Wesley 1997.
Articoli di carattere espositorio, conferenze
• 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
• L. Adleman : conferenza all'ACM per il premio Turing 2002.
• Victor Miller : Elliptic curve cryptography. Presentazione, 24 maggio 2007.
• Carl Pomerance : Elliptic curves: applications and problems; conferenza First Abel Conference, Univ. of Minnesota , January, 3-5 2011.
Note
• nota1 Aritmetica sui numeri interi.
• nota2 Gruppi, anelli, campi e applicazioni.
• Nota sulla funzione φ di Eulero.
• Espansioni decimali di 1/n.
• Nota sulle radici primitive modulo p.
• Nota sui gruppi abeliani finiti.
• Nota sul metodo ρ di Pollard.
• Nota sul metodo p-1 di Pollard.
• Nota sul metodo delle curve ellittiche.
• Nota sul "calcolo dell'indice" per la risoluzione del logaritmo discreto in Z _p^*.
• Nota su esempi di applicazioni del logaritmo discreto alla crittografia.
• Nota sulla sommatoria Σ 1/p.
• Nota sul Crivello Quadratico.
• Nota sull'algoritmo di Shanks-Tonelli.
• Nota sulle radici quadrate modulo p e modulo p^k.
• Nota "smooth numbers estimates".

Materiale per argomenti

• RSA
  • R. Schoof, Fattorizzazione e criptosistemi a chiave pubblica, Didattica delle Scienze 137 (1988), 48–54. pdf
    
  • S. Robles, The RSA cryptosystem, pdf
    
  • Fotos Rivest, Shamir, Adleman
• Primalità
  • Stime sulla distribuzione dei numeri primi link
  • Il test di primalita' di Miller– Rabin su Wikipedia.
  • Il test di primalita' di Agrawal-Kayal-Saxena in Wikipedia.
  • R. Schoof, Four primality testing algorithms, “Algorithmic number theory” MSRI Publications 44, Cambridge University Press 2008, 101–126. pdf
    (Il test di Miller-Rabin si trova alle pp. 2–4).
  • Criterio di Pocklington in Wikipedia.
  • Algoritmo di Goldwasser-Kilian in Wikipedia.
  • S.Goldwasser, J. Kilian, Primality Testing Using Elliptic Curves, Journal of the ACM, Vol.46, N.4, July 1999, pp.450-472 pdf
  • ECPP records PRIMO
  • Foto Agrawal, Kayal, Saxena (Palo Alto, primavera 2004)
• Fattorizzazione
  • Pollard ρ
    • Pollard ρ in Wikipedia.
    • Pollard ρ web pages.
    • J. Pollard and R. Brent: Factorization of the eighth Fermat number, Math. Comp. 36 (1980). (pdf, 4 p.)
    • BirthdayGrapher (solo per Mac) link
    • John Pollard's home page.
  • Metodo “p – 1 ”
    • p – 1 method in Wikipedia.
    • p – 1 method web pages.
  • Metodo delle curve ellittiche
    • Curve Ellittiche in Wikipedia
    • Metodo delle curve ellittiche in Wikipedia.
    • Elliptic curve method web pages.
    • Elliptic Curve Tutorial di certicom link
    • Ecmnet.
    • B. Poonen: Elliptic curves, “Algorithmic number theory” MSRI Publications 44, Cambridge University Press 2008, pdf
    • R. Brent: Factorization of the tenth Fermat number, Math. Comp. 68 (1999) 429–451. (pdf)
    • H. Lenstra: Factoring integers with elliptic curves, Annals of Math. 126, (1987) 649-673 pdf (l'introduzione e' chiara e accessibile)
    • P. Zimmerman: Miglioramenti del metodo delle curve ellittiche. (April 2003)pdf
    • Foto di Hendrik Lenstra.
    • Foto di Peter Montgomery.
  • Il crivello quadratico
    • Il crivello quadratico in Wikipedia.
    • Esempio di fattorizzazione usando il crivello quadratico txt Spiegazione pdf
    • Un altro esempio pdf Spiegazione pdf
    • La fattorizzazione di RSA129 (1994) txt.
    • Carl Pomerance, Smooth numbers and the quadratic sieve, pdf.
    • Carl Pomerance, A tale of two sieves, pdf (La favola dei due crivelli).
    • Radici quadrate modulo p. Algoritmo di Tonelli txt.
    • L'algoritmo di Shanks-Tonelli in Wikipedia.
    • Il Lemma di Hensel in Wikipedia.
    • Foto di Carl Pomerance
• Logaritmo discreto
  • Il logaritmo discreto in Wikipedia.
  • Discrete logarithm web pages.
  • Baby-step-Giant-step method in Wikipedia.
  • Diffie-Hellman-Merkle key exchange in Wikipedia.
  • El Gamal encryption in Wikipedia.
  • J. Pollard: Monte Carlo methods for index computation (mod p), Math. Comp. 32 (1978). (Canguri, pdf, 7 p.).
  • C. Pomerance: Elementary thoughts on discrete logarithms, “Algorithmic number theory” MSRI Publications 44, Cambridge University Press 2008, pdf.
  • Chris Studholme, The discrete log problem, june 2002, pdf
  • Esempio di calcolo di un logaritmo discreto (usando il metodo del calcolo dell'indice)txt.
  • Il logaritmo discreto sulle curve ellittiche CerticomTutorial
  • Foto di Dan Shanks jpg
  • Foto di Taher ElGamal jpg
  • Foto di Ralph Merkle, Martin Hellman, Whit Diffie jpg

  NUMEROLOGIA & VARIE

  • News
    • Ron was wrong, Whit is right pdf
    • Electronic Frontier Foundation link
    • 8 marzo 2010: Trovato fattore record con ECM. Vedi annuncio
    • 3 febbraio 2010: Fattorizzato F_14. Vedi annuncio
    • 7 gennaio 2010: Fattorizzato RSA-768. Vedi annuncio e articolo
    • 29 settembre 2008: Scoperto un numero primo con circa 13.000.000 di cifre pdf.
    • 31 agosto 2007: Il numero N = (2⁴²⁷³⁷+1)/3 è primo.
    • 22 maggio 2007: È stato fattorizzato il 1039-esimo numero di Mersenne 2¹⁰³⁹-1. Vedi annuncio
    • 26 settembre 2006: M₄₄ e' primo.
    • 2 novembre 2005: E` stato fattorizzato RSA640. Comunicato stampa RSA.
    • primo records
    • Records di primalita'
    • Records di fattorizzazione.
    • GIMPS
  • The Prime pages.
  • Numeri di Carmichael
  • Numeri di Mersenne
  • Numeri perfetti
  • Sito ufficiale RSA
  • Sito Ufficiale certicom (ECC elliptic curve criptography)
  • National Security Agency: The case for elliptic curve criptography link1 link2
  • Government Computer News: giugno 2007

  Il corso di Teoria Elementare dei Numeri

  • 2005-2006
  • 2006-2007
  • 2007-2008
  • 2008-2009
  • 2009-2010
  • 2010-2011
  • 2011-2012
  • Criptography - University of California - Berkeley spring 2009
  
  
  
  
  

  Altro

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