POČÍTAČOVÁ ALGEBRA I 2010/11

PŘEDNÁŠKA V posledních letech jsem přednášel já, ale letos přednáší Jan Žemlička, obsah se nemění.

CVIČENÍ mám já. Na cvičeních se budeme věnovat především implementaci probíraných algoritmů. Naučíme se základy práce s Mathematicou a základy programovaní v C++ s použitím matematických knihoven GMP a NTL. Část cvičení bude formou prezentace výsledků studentů.

Zápočet bude možná těžší než zkouška. K zápočtu je třeba odevzdat dva zápočtové programy, jeden v Mathematice a jeden v C++/GMP/NTL, naměřit časovou složitost na náhodných datech, výsledky zpracovat do grafů a alespoň jednu implementaci odprezentovat na cvičeních včetně testu časové složitosti na náhodných datech. Vzorová zápočtová úloha v Mathematice zde a zde.

Zápočtové programy posílejte plně funkční, s okomentovaným zdrojákem a srozumitelným ovládáním (vstupem/výstupem) tak, abych mohl posoudit správnost na vlastnoručně zadaném vstupu. Zápočťáky v C++ posílejte buď včetně binárek (EXE, linux), nebo včetně konfiguračních souborů pro Code::Blocks (tak abych to jednou klávesou přeložil a spustil); jiný překladač nemám. Protože gmail obvykle odmítá exáče, buď ho nějak ošiďte, nebo přes úschovnu, nebo osobně. Díky za pochopení.

Zápočťáky:

algoritmus	student
Čínská věta o zbytcích v Z: Lagrange vs. Garner
Čínská věta o zbytcích v Q[x]: Lagrange vs. Garner
Čínská věta o zbytcích v Z_p[x]: Lagrange vs. Garner
Interpolace nad Z_p ve dvou proměnných
Násobení polynomů v Z[x]: školské vs. pomocí FFT v Z_p[x]
Násobení polynomů v Z[x]: školské vs. pomocí FFT v C[x]
Dělení polynomů v Z[x]: školské vs. rychlé (Newton)
Dělení polynomů v Z_p[x]: školské vs. rychlé (Newton)
Dělení v Z: Newtonova metoda vs. půlení intervalu vs. školské
Odmocnina v Z: Newtonova metoda vs. půlení intervalu
Newtonova metoda tečen vs. její modifikace se sečnami
NSD pomocí PRS v Z[x]
NSD pomocí PRS v Z[x,y]
NSD - modulární algoritmus v Z[x]
Bezčtvercová faktorizace v Z[x]
Bezčtvercová faktorizace v Z_p[x]
Berlekampův algoritmus (faktorizace v Z_p[x])
Stejnostupňová a různostupňová faktorizace (v Z_p[x])
Henselovo liftování + faktorizace v Z[x]
Testování ireducibility v Z[x] a v Z_p[x]
Kroneckerův algoritmus (faktorizace v Z[x,y])

Poznámky: 1) V knihovně NTL není implementována aritmetika v Q[x] - použijte floating point operace (tj. pracujte v "R[x]"); 2) aritmetika v C[x] se rozumí floating point; 3) pro dělení v Z[x] uvažujte pouze monické dělitele; 4) numerické výpočty měřit pod C++/GMP

POČÍTAČOVÁ ALGEBRA II 2009/10

Ve školním roce 2010/11 není tento předmět vyučován. Jde o loňské informace.

Článek o využití Gröbnerových bází v kryptoanalýze (celý text je dostupný z domény mff.cuni.cz)

Zkouška bude udělena za zápočtové programy a domácí cvičení (tj. žádné ústní zkoušení). Na jedničku je potřeba aspoň 28 bodů, na dvojku 24, na trojku 20.

Úlohy (mohou být vypracovány částečně na počítači, viz instrukce u jednotlivých úloh)

1. (2 body) Uvažujme polynomy jedné proměnné nad T. Za jakých podmínek je množina polynomů Gröbnerovou bází? Dokažte, že každý ideál má jednoprvkovou Gröbnerovu bázi. Co je výsledkem přepisu polynomu f pomocí báze {r}?
2. (2 body) Buď I=<R> ideál v oboru T[x1,...,xn]. Dokažte, že R je Gröbnerova báze právě tehdy, když <lt(r):r in R>=<lt(f):f in I>
3. (3 body) Uvažujme pro jednoduchost polynomy dvou proměnných nad T. Odhadněte časovou složitost Algoritmu A (testování g\in<R>) v závislosti na velikosti g, počtu polynomů v R a jejich velikosti. Jak se výsledek liší pro LEX a GLEX?
4. (3 body) Najděte normovanou redukovanou Gröbnerovu bázi ideálu <x^2-2y^2, xy-3> v Q[x,y] vzhledem k nějakému uspořádání (dle vlastního výběru). Je polynom 3-x-2y^3+2y^4 prvkem tohoto ideálu? [Rozepište běh Buchbergerova algoritmu, jednotlivá přepisování podle dosavadní báze můžete provést automaticky na počítači.]
5. (1 bod) Buď I=< x+y, x^2+1> a J=< x-y, x^2-1>. Rozhodněte, zda I průnik J = IJ. Pokud ne, uveďte příklad polynomu, který je průniku, ale není v součinu.
   [Na výpočet Gröbnerových bází můžete použít počítač.]
6. (2 body) Kolik řešení má následující soustava rovnic v Q a kolik v C ?
   a) x^2 - 2xy^2 + 1 = 0, xy - 2y^2 + x = 0.
   b) 1 + 2x^2 + y^2 + 4x^2y^2 + 2x^2y^4 = 0, xy^2 + xy^4 = 0
   [Na výpočet Gröbnerových bází můžete použít počítač.]
7. (2 body) Řešte pomocí metody Gröbnerových bází následující geometrické úlohy:
   a) Simson-Wallaceova věta: Buď ABC trojúhelník a P bod na kružnici opsané. Nechť K,L,M značí paty kolmic z bodu P na přímky AB,AC,BC. Pak body K,L,M leží na přímce.
   b) Menelaova věta: Buď ABC trojúhelník a nechť A' leží na přímce BC, B' leží na přímce AC, C' leží na přímce AB. Pak A',B',C' leží na přímce právě tehdy, když (ABC')(BCA')(CAB')=1. Zde (ABC) značí u takové, že C-A=u(C-B).
   [Na výpočet Gröbnerových bází můžete použít počítač.]
8. (1+2 body) Najděte a) nejkratší bázi mřížky dané vektory (3,8), (5,14), b) LLL-redukovanou bázi mřížky dané vektory (-1,5,0), (2,5,0), (8,6,16).
   [Ručně.]
9. (2 body) Buď b_1,...,b_n LLL-redukovaná báze mříže a v_1,...,v_i nějaké lineárně nezávislé mřížové body. Dokažte, že ||b_i||<2^((n-1)/2)max(||v_1||,...,||v_i||).
10. (2 body) Dokažte, že v dvoudimenzionální verzi algoritmu na hledání nejkratší báze mříže je každý nový vektor alespoň 3^(1/2) -krát menší než ten původní.
11. (2 body) Uvažujte mřížku L v Q^n danou n kanonickými vektory a vektorem (1/2 ... 1/2). Najděte nějakou bázi. Uvažujme dále vektory b_1,...,b_n zkonstruované tak, že b_1 je nejkratší v L a b_(i+1) je nejkratší v L-<b_1,...,b_i>. Dokažte, že pro n>4 toto není báze.
12. (3 body) a) Najděte a,b celá taková, že a^2+b^2=NextPrime[2^1000].
    b) Najděte pomocí LLL minimální polynom čísla 2^(1/2)-2^(1/3)+2^(1/4) nad Q.
    c) Najděte diofantickou aproximaci čísel e a pí, kde epsilon=0.3.
    [Na výpočet redukované báze použijte počítač.]
13. (3-6 bodů podle kvality) Uvažujte Merkle-Hellmanův kryptosystém založený na knapsacku. Proveďte statistiku úspěšnosti tohoto útoku v závislosti na n: pro různá n generujte náhodné klíče dimenze n a náhodné zprávy, počítejte kolika procentech případů LLL najde otevřený text. Závisí úspěšnost útoku na klíči? (Pro daný klíč vygenerujte několik zpráv, zkoumejte podíl prolomených zpráv; liší se to významně pro různé klíče?)

Témata zápočtových programů (programovací jazyk libovolný)

1. (6 bodů) Gröbnerovy báze: Algoritmus A, Algoritmus B, redukce bází.
2. (4-6 bodů) LLL (základní verze 4 body, aspoň trochu optimalizovaná 6).
3. (2 body) Napište funkce pro průnik, součin a součet ideálů a pro náležení radikálu nad algebraicky uzavřeným tělesem.
4. (5 bodů) Napište funkci pro barvení grafů a) pomocí Gröbnerových bází, b) pomocí SAT (viz např. funkce SatisfiableQ v Mathematice). Srovnejte jejich rychlost.
5. (8 bodů) Naprogramujte kryptosystém Goldreich-Goldwasser-Halevi. Způsob vytváření dobré a špatné báze si určete experimentálně sami (nebo si jej někde najděte) tak, aby špatná báze obsahovala n vektorů, každý o zhruba n bitech. Zjistěte, pro jak velké n je vaše implementace odolná vůči útoku pomocí LLL (tj. LLL převede špatnou bázi na něco, co nestačí k dešifrování).