Vybrané kapitoly z geometrie pre grafikov

Literatúra

• Miles Reid: Undergraduate algebraic geometry, Cambridge University Press, 1989
• Robert J. Walker: Algebraic curves, Princeton University Press, 1950
• William Fulton: Algebraic Curves, Addison-Wesley Publishing Co, 1989
• Igor R. Shafarevich: Basic Algebraic Geometry 1, Springer Verlag, 1994

Hodnotenie

min 0,5 úlohy: E
min 1 úloha: D
min 1,5 úlohy: C
min 2 úlohy: B
min 2,5 úlohy: A

1. úloha

Navrhnite a implementujte algoritmus, ktorý nájde obidve asymptoty zadanej hyperboly. Asymptotu sme definovali ako priamku, ktorá má asymptotický smer (bolo vysvetlené na prednáške) a hyperbolu nepretína. Vypracovanie úlohy by malo pozostávať z dvoch častí:

• teoretické riešenie (na papieri): analýza problému, odvodenie vzorcov a postupov, ...
• samotná implementácia: program, ktorý dostane na vstupe hyperbolu (napríklad ako zoznam koeficientov kvadratickej rovnice) a vypíše obe jej asymptoty (ich všeobecné rovnice).

2. úloha

Hodnotenie

3. úloha

Podrobnejší popis protokolu:
- Zvoľte si vhodné konečné pole F, t.j. zvoľte si prvočíslo dostatočne veľké na to, aby ste do prvkov poľa vedeli zakódovať (textovú) správu.
- Zvoľte si eliptickú krivku E nad poľom F (t.j. parametre p,q v rovnici y^2 = x^3 + px + q, aby diskriminant krivky bol nenulový v poli F).
- Nájdite na krivke E bod g, nech podľa možnosti jeho rád v grupe E je čo najväčší.
(F,E,g a rád g v grupe E sú súčasťou verejného kľúča.)
- Každý účastník komunikácie (A,B,...) si volí prirodzené číslo (a,b,...) (menšie ako rád g v grupe E) = súkromný kľúč, a zverejní bod a.g, b.g,... = verejný kľúč (označme ich ako va, vb,...).
- účastník A pre komunikáciu s B použije ako kľúč x-súradnicu bodu a.vb
šifrujte jednoducho násobením v poli F: ak m je kód časti správy, teda prvok poľa F, a k je kľúč, tak m.k je zašifrovaná časť správy, kde "." je násobenie v poli F.

Poznámky:
1. Hľadanie bodu na krivke a hľadanie rádu prvku grupy E sú vo všeobecnosti veľmi ťažké problémy. Vy však použite obyčajné prehľadávanie. Vami zvolené prvočíslo vôbec nemusí byť príliš veľké.
2. Odvodili sme si (čiastočne) vzorce pre výpočty na eliptickej krivke y^2 = x^3 + p*x + q:
- ak x1 = x2 a y1 = -y2, tak (x1,y1)+(x2,y2)=o, bod v nekonečne, neutrálny bod grupy E
- ak x1 a x2 sú rôzne, tak (x1,y1) + (x2,y2) = (x3,y3) také že:
x3 = L^2 - x1 - x2,
y3 = L*(x1-x3) - y1,
kde L = (y2-y1)/(x2-x1)
- ak (x1,y1)=(x2,y2), tak 2*(x1,y1) = (x3,y3) také že:
x3 = L^2 - 2*x1,
y3 = L*(x1-x3) - y1,
kde L = (3*x1^2 + p)/(2*y1).
3. Pokiaľ nebudete používať knižnicu, ktorá poskytuje modulárnu aritmetiku, budete stáť pred problémom, ako pre dané n nájsť m, že nm = 1 (mod prvočíslo). Na toto existujú efektívne algoritmy, nemusíte ich však implementovať, stačí ak si na začiatku (po voľbe poľa) vyrobíte tabuľku, ktorá bude pre každé číslo obsahovať k nemu inverzné.

Hodnotenie