English

Andrej Dujella:

Algoritmi za eliptičke krivulje

Od 17.3.2009. ovdje možete predići drugu zadaću.
Rok za predaju rješenja druge zadaće bio je 8.4.2009.

Od 26.5.2009. ovdje možete predići treću zadaću.
Rok za predaju rješenja treće zadaće bio je 10.6.2009.

Opis kolegija

U ovom kolegiju obradit će se neki važni algoritmi za eliptičke krivulje nad poljem racionalnih brojeva, te nad konačnim poljima.

Detaljno će se opisati algoritmi za dobivanje informacija o Mordell-Weilovoj grupi eliptičke krivulje nad poljem racionalnih brojeva (torzijska grupa, gornje i donje ocjene za rang, generatori grupe u slučaju kad je moguće egzaktno izračunati rang). Prikazat će se neke metode za konstrukciju eliptičkih krivulja relativno velikog ranga, a također i metode za nalaženje svih cjelobrojnih točaka na eliptičkoj krivulji, koje koriste poznavanje pripadne Mordell-Weilove grupe.

Kod eliptičkih krivulja nad konačnim poljima, bit će riječi o efikasnoj implementaciji zbrajanja i multipliciranja točaka, s posebnim naglaskom na polja karakteristike 2, koja su važna za primjene u kriptografiji. Prikazat će se algoritmi za efikasno brojenje točaka, te algoritmi za problem diskretnog logaritma na eliptičkoj krivulji.

Tijekom kolegija studenti bi trebali ovladati programima i programskim paketima za rad s eliptičkim krivuljama (PARI/GP, MWRANK, MAGMA), te pomoću njih rješavati programske zadatke.

Od studenata se očekuje poznavanje osnovnih pojmova i činjenica o eliptičkim krivuljama, na razini poslijediplomskog kolegija Ivice Gusića Uvod u aritmetiku eliptičkih krivulja (predavanja se mogu naći na http://www.math.hr/~duje/seminar.html) ili standardnog udžbenika Silverman-Tate Rational Points on Elliptic Curves.

Literatura

1. I. Blake, G. Seroussi, N. Smart: Elliptic Curves in Cryptography, Cambridge University Press, Cambridge, 1999.

2. H. Cohen: A Course in Computational Algebraic Number Theory, Springer-Verlag, New York, 1993.

3. H. Cohen: Number Theory. Volume I: Tools and Diophantine Equations, Springer Verlag, Berlin, 2007.

4. I. Connell: Elliptic Curve Handbook, McGill University, 1999.

5. J. E. Cremona: Algorithms for Modular Elliptic Curves, Cambridge University Press, Cambridge, 1997.

6. A. Dujella, M. Maretić: Kriptografija, Element, Zagreb, 2007.

7. D. Hankerson, A. Menezes, S. Vanstone: Guide to Elliptic Curve Cryptography, Springer-Verlag, New York, 2004.

8. S. Schmitt, H.G. Zimmer: Elliptic Curves. A Computational Approach, de Gruyter, Berlin, 2003.

9. J. H. Silverman: Elliptic curves and cryptography, in: P. Garrett, D. Lieman (Eds.): Public-Key Cryptography, American Mathematical Society, Providence, 2005, pp. 91-112.

10. J.H. Silverman: The Arithmetic of Elliptic Curves, Springer-Verlag, 1996, 2009.

11. J. H. Silverman, J. Tate: Rational Points on Elliptic Curves, Springer-Verlag, Berlin, 1992.

12. N. P. Smart: The Algorithmic Resolution of Diophantine Equations, Cambridge University Press, Cambridge, 1998.

13. L. C. Washington: Elliptic Curves: Number Theory and Cryptography, CRC Press, Boca Raton, 2003, 2008.

Bilješke s predavanja
(u pdf formatu)

Seminarske teme

Neki (korisni) linkovi

Seminar za teoriju brojeva i algebru
Teorija brojeva - dodiplomski izborni kolegij
Kriptografija - dodiplomski izborni kolegij
Eliptičke krivulje i njihova primjena u kriptografiji - studentski seminar (2002/2003)
Teorija brojeva u kriptografiji - poslijediplomski kolegij (Andrej Dujella, 2003/2004)
Diofantske jednadžbe - poslijediplomski kolegij (Andrej Dujella, 2006/2007)
Algorithms from A Course in Computational Algebraic Number Theory (James Pate Williams)
Software packages of interest to number theory
PARI/GP home page
SAGE home page
Cremona's MWRANK (verzija za windowse)
Algorithmic Number Theory: Tables and Links (Noam Elkies)
High rank elliptic curves with prescribed torsion (Andrej Dujella)
Number Theory Web (održava Keith Matthews)
Popis dostupne literature iz teorije brojeva

Web stranice nekih kolegija o eliptičkim krivuljama:

Algorithmic Aspects of Elliptic Curves (Andrej Dujella)
Arithmetic of Elliptic Curves and Modular Forms (Hossein Movasati)
Elliptic Curves (Edray Goins)
Elliptic Curves (Jim Milne)
Elliptic Curves (Miles Reid)
Elliptic Curves (Helena Verrill)
Elliptic Curves and Applications (Andrej Dujella)
Elliptic Curves and Cryptography (Alan Silvester)
Elliptische Kurven (Franz Lemmermeyer)
Introduction to elliptic curves (Ian Kiming)
Number Theory of Cubic Curves (Jaap Top)
Rational Points on Elliptic Curves (Daniel Rogalski)
Selected Topics in Number Theory (Jerrold Tunnell)
Vorlesung uber Elliptische Kurven und Kryptographie (Wolfgang Ruppert)