Algebrai geometriai számítások előadás


Az előadás helye és ideje: DT 0-411, hétfő 14.00-15.30

Számonkérés: a tárgyat szóbeli vizsga zárja. A vizsga helye DT 2.206, a vizsga ideje a Neptumban meghirdetett időpontokban, illetve egyéni megbeszélés szerint. A vizsgán szereplő tételek

Ajánlott irodalom:

  1. R. L. C. Washington: Elliptic Curves: Number Theory and Cryptography

  2. Farkas Gábor, Kátai Imre: Algebrai geometriai számítások

  3. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone : Handbook of applied cryptography


Egyes előadások tartalma

1. előadás, 2013. 02. 17:
Prímszámok eloszlása. Prímtesztek. Fermat-teszt, pszeudoprímek. Soloway-Strassen teszt, kvadratikus maradékok, Legendre szimbólum, Euler tétele.

2. előadás, 2013. 02. 24:
Legendre szimbólum tulajdonságai. Jacobi szimbólum és tulajdonságai. Legendre szimbólum kiszámítása Jacobi szimbólummal. Soloway-Strassen teszt és tulajdonságai. Miller-Rabin teszt, erős pszeudoprímek.

Determinisztikus prímtesztek. Lucas teszt.

3. előadás, 2013. 03. 03:
Determinisztikus prímtesztek (folyt.). Pocklington-Lehmer teszt, Proth teszt.

Faktorizáció. Próbaosztás, Pollard ró, Pollard p-1, Fermat faktorizációk.

4. előadás, 2013. 03. 10:
Faktorizáció (folyt.). Kvadratikus szita, szubexponenciális algoritmusok.

Diszkrét logaritmus probléma. A DDHP, CDHP és DLP problémák. Generátor keresése. Generikus algoritmusok, brute-force, Baby-step, giant-step algoritmus.

5. előadás, 2013. 03. 17:
Diszkrét logaritmus probléma (folyt.). Pollard ró, Pohling-Hellman. Indexkalkulus. Schnorr csoport.

Elliptikus görbék. A görbék fogalma, rövid Weierstrasse egyenlet. Szinguláris görbék. Általános Weierstrasse egyenlet, és kapcsolata a rövid Weierstrasse egyenlettel.

6. előadás, 2013. 03. 24:
Csoportművelet a görbén. Projektív koordináták. Görbék véges testek fölött. Hasse-Weil tétel.

7. előadás, 2013. 03. 31:
Görbék elemszáma. Frobenius leképzés a görbén. Torziópontok. Szuperszinguláris görbék. Bilineáris leképzések a torziócsoportból.

8. előadás, 2013. 04. 07:
Diszkrét logaritmus probléma görbéken. MOV támadás.
Kriptográdiai alkalmazások: Diffie-Hellman kulcscsere. Példa, mikor a DDHP könnyű. 3 személyes kulcscsere protokoll. ElGamal titkosítás.

9. előadás, 2013. 04. 14:
Kriptográdiai alkalmazások (folyt.): ElGamal és ECDSA aláírás. ID alapú titkosítás.
Görbék mod n.

10. előadás, 2013. 04. 28:
Görbék mod n (folyt.). Faktórizáció és determinisztikus prímteszt elliptikus görblkkel.