Matematika IV - 5. přednáška Polynomy
Michal Bulant
Masarykova univerzita Fakulta informatiky
17. 3. 2008
Q Dělitelnost a nerozložitelnost Q Kořeny a rozklady polynomů Q Polynomy více proměnných Q Pár slov o šifrách
•  Martin Panák, Jan Slovák, Drsná matematika, e-text.
•  R. B. Ash, Abstract algebra,
http://www.math.uiuc.edu/~r-ash/Algebra.html.
•  Jiří Rosický, Algebra, PřF MU, 2002.
•  dále Předmětové záložky v IS MU
Směřujeme nyní ke zobecnění rozkladů polynomů nad číselnými obory a k tomu nejprve potřebujeme ujasnit, co je dělitelnost v základním okruhu R samotném. Uvažujme proto nějaký pevně zvolený obor integrity Z?1, třeba celá čísla Z nebo okruh Zp s prvočíselným p. V R definujeme dělitelnost analogicky jako to známe ze Z: b\a  <š=>  3c G R : a = b ■ c .
Pak platí:
•  je-li a\b a zároveň b\c pak také a|c;
•  a\b a zároveň a\c pak také a\(ceb + ßc) pro všechny ct,ß<ER;
•  a|0 pro všechny a G /? (je totiž a • 0 = 0);
•  každý prvek a G /? je dělitelný všemi jednotkami e G /? a jejich násobky a • e (jak přímo plyne z existence e_1)
^bor integrity proto, aby bylo jednoznačné dělení!
Řekneme, že prvek a G R je nerozložitelný (ireducibilní), jestliže
•  je nenulový a není jednotkou (tj. a\ 1),
•  je dělitelný pouze jednotkami e G R a čísly a • e (tzv. čísla asociovaná s a - tj. taková b <E R, že a\b a b\a).
Řekneme, že okruh R je obor integrity s jednoznačným rozkladem, jestliže platí:
•  pro každý nenulový prvek a G R, který není jednotkou, existují nerozložitelné a\1..., ar G R takové, že a = a\ ■ a-i... ar
•  jsou-li prvky a\,..., ar a b\,..., bs nerozložitelné, nejsou mezi nimi žádné jednotky a ai32 ... ar = b\b% ... bs, pak je r = s a ve vhodném přeuspořádání platí aj = ejbj pro vhodné jednotky ej.
Příklad
O Z, R[x] jsou obory integrity s jednoznačným rozkladem (ireducibilní prvky v Z jsou prvočísla a čísla k nim opačná).
O Každé těleso je obor integrity s jednoznačným rozkladem (kde každý nenulový prvek je jednotka).
Q Např. v okruhu Z[\/—5] = {a + byf—b; a, b e Z} existují dva různé rozklady čísla 6 na nerozložitelné prvky:
2-3 = (l-\/=5)(l + \/=5).
Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Zje procedura dělení se zbytkem a Euklidův algoritmus pro hledání největších společných dělitelů. Tyto postupy nyní zobecníme.
Lemma (Věta o dělení se zbytkem)
Nechi R je komutativní okruh bez dělitelů nuly a f,g e R[x] polynomy g ^ 0. Pak existuje a G R, a 7^ 0, a polynomy q a r splňující af = qg + r, kde r = 0 nebo str < st g. Je-Ii navíc R těleso neboje aspoň vedoucí koeficient polynomu g roven jedné, potom lze volit a = 1 a polynomy q a r jsou v tomto případě určeny jednoznačně.
Poznámka
Toto tvrzení je možné aplikovat i obecněji (viz Euklidovské okruhy), je ale třeba správně definovat, jak budeme porovnávat prvky.
Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi
kořenů polynomů.
Uvažme polynom f(x) G R[x], st f > 0, a dělme jej polynomem
x - b, b G R.
Protože je vedoucí koeficient jednička, algoritmus pro dělení dává
jednoznačný výsledek. Dostáváme tedy jednoznačně zadané
polynomy q a r splňující f = q{x — b) + r, kde r = 0 nebo
st r = 0, tj. r G R. Tzn., že hodnota polynomu f v b G /? je rovna
právě f(Ď) = r.
Proto je prvek b G /? kořen polynomu f právě, když (x — b)\f.
Protože po vydělení polynomem stupně jedna vždy klesne stupeň
výsledku alespoň o jedničku, dokázali jsme následující tvrzení:
Důsledek
Každý nenulový polynom f nad tělesem R má nejvýše st f kořenů.
Příklad
Polynom x3 má nad Zs 4 kořeny ([0]s, [2]s, [4]s, [6]s,)-
Je to tím, že tento okruh není oborem integrity (a tedy ani
tělesem).
Důsledkem předchozího tvrzení je následující velmi důležitý fakt.
Důsledek
Libovolná konečná podgrupa multiplikativní grupy (Kx, •) tělesa (K, +, •) je cyklická. Speciálně existuje prvek g G Z* tak, že jeho mocniny generují celou grupu Z*.
Platí-li pro k > 1, že dokonce (x — b)k\f, kde k je největší možné, říkáme, že kořen b je násobnosti k.
Dva polynomy nad nekonečným komutativním okruhem, které zadávají stejné zobrazení R —> R, mají rozdíl, jehož kořenem je každý prvek v R. Protože rozdíl polynomů má jen konečný stupeň, pokud není nulový, dokázali jsme tak již dříve uvedené tvrzení:
Jestliže je R nekonečný okruh, pak dva polynomy f(x) a g{x) , R jsou stejné právě, když jsou stejná příslušná zobrazení f a g.
Polynom h je největší společný dělitel dvou polynomů a f a g G R[x] jestliže:
•  h\f a zároveň h\g
•  jestliže k\fa zároveň k\g pak také k\h.
Věta (Bezoutova rovnost)
Necht R je těleso a necht f,g<E R[x]. Pak existuje největší společný dělitel h polynomů f a g. Polynom h je určený jednoznačně, až na násobek nenulovým skalárem. Přitom existují polynomy A, B G R[x] takové, že h = Af + Bg.
Euklidův algoritmus.
D
Důkaz následujícího tvrzení je poměrně technický a nebudeme jej prezentovat v detailech (i když jsme si vše potřebné pro něj již v podstatě připravili).
Je-li R obor integrity s jednoznačným rozkladem, pak také okruh polynomů R[x] je obor integrity s jednoznačným rozkladem.
Příklad
Z[x],Zs[x] jsou okruhy s jednoznačným rozkladem.
Důsledkem této věty je skutečnost, že každý polynom nad komutativním okruhem s jednoznačným rozkladem můžeme rozložit tak, jak to známe s polynomy s reálnými nebo komplexními koeficienty. Pokud má polynom tolik kořenů, včetně násobnosti, jako je jeho stupeň st f = k, je odpovídající rozklad tvaru
f(x) = b ■ (x - 3i) • (x - a2)... (x - ak).
Zatímco reálné polynomy mohou být i úplně bez kořenů, každý komplexní polynom naopak takovýto rozklad připouští. To je obsahem tzv. základní věty algebry:
Věta (Základní věta algebry)
Pole C je algebraicky uzavřené, tj. každý polynom stupně alespoň 1 má kořen.
J
ist                  Kořeny a rozklady pc
Polynomy vice pr
Hledání kon
i red uci bi I it.
Věta (Gaussovo lemma)
Je-li polynom f G Z[x] ireducibilní nad Z, pak je rovněž ireducibilní jakožto polynom nad Q.
Důsledek
\/2 není racionální číslo.
Má-li polynom f(x) = anxn + • • • + ao G Z[x] racionální kořen r/s G Q v základním tvaru, pak r\ao a s\an.
Příklad
•  Dokažte, že x3 — 3x — 1 G Q [x] je ireducibilní.
•  Dokažte, že x3 — 3x — 1 G 2^[x] je ireducibilní.
ist                  Kořeny a rozklady pc
Polynomy vice pr
Hledání kon
i red uci bi I it.
Věta (Eisensteinovo kritérium ireducibility)
Je-li f{x) = anx" + • • • + a\x + 3o G Z [x], přičemž:
9  p j a0,...,Pn-l,P\3n •   P2 f 30-
Pak je f ireducibilní nad Z (a tedy i nad Q).
Důsledek
Nad okruhem Z existují ireducibilní polynomy libovolného stupně.
Stačí uvážit fn = x" + 2, který je podle Eisensteinova kritéria (s p = 2) ireducibilní stupně n.                                                             D
Poznámka
Užitečná je často také tzv. lokalizace, tj. redukce koeficientů modulo zvolené prvočíslo p, příp. posunutí proměnné o konstantu. Např., že polynom x3 + 27x2 + 5x + 97 je ireducibilní, zjistíme díky redukci, ireducibilitu tzv. kruhového polynomu
,p-i
x-1 díky substituci x = y + 1.
+ ---+X+1
J e-1 i a kořenem polynomu f nad tělesem násobnosti k > 1, je a kořenem f násobnosti k — 1.
Důsledek
Násobné kořeny polynomu f jsou právě kořeny (f, f). Všechny kořeny polynomu f obdržíme jako (jednoduché) kořeny polynomu
f/(f, n
Okruhy polynomů v proměnných x\,... ,xr definujeme induktivně vztahem
/?[*!, ...,xr]:= R[xi,... ,xr_i][xr].
Např. R[x, y] = R[x][y], tzn. že uvažujeme polynomy v proměnné y nad okruhem R[x]. Snadno se ověří, že polynomy v proměnných x\,... ,xr lze chápat jako výrazy vzniklé z písmen x\,... ,xn a prvků okruhu R konečným počtem (formálního) sčítání a násobení v komutativním okruhu. Například prvky v /?[x,y] jsou tvaru
f = an(x)yn + an_i(x)y"-1 + • • • + a0(x) = (amnxm + ■■■ + a0n)yn + ■■■ + (r>p0xp + • • • + b00) = coo + ciox + coiy + C20X2 + cnxy + c02y2 + ■■■
Jako důsledek naší definice a předchozích výsledků pro polynomy nad obecnými komutativními okruhy dostáváme:
Důsledek
O Jestliže v okruhu R nejsou dělitelé nuly pak také v okruhu polynomů R[x\,... ,xr] nejsou dělitelé nuly.
Je-li R obor integrity s jednoznačným rozkladem, pak také okruh polynomů R[x\,..., xr] je obor integrity s jednoznačným rozkladem.
Příklad
Z[x,y] je okruh s jednoznačným rozkladem.
				
Polynom f	e/?[xi,..	.,*„],	který se nezmění	při libovolné
permutaci	proměn nýc	h xi,	... ,xn, se nazývá	symetrický polynom.
Elementárními symetrickými polynomy rozumíme polynomy				
	Sl =	*i +x2H--------hxn,		
	S2 =	XiX2	+ ^1^3 H--------hx„	-ixn,
	S„ =	Xl ••	■Xn	
RSA
Ron Rivest, Adi Shamir, Leonard Adieman (1977; C. Cocks,GCHQ - 1973)
•  každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a
•  generování klíčů: zvolí dvě velká prvočísla p, q, vypočte
n = pq, Lp{n) = (p — l)(q — 1) [n je veřejné, ale <p(n) nelze snadno spočítat ]
•  zvolí veřejný klíč e a ověří, že (e, tp{n)) = 1
•  např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e ■ d = 1 (mod </?(n))
•  zašifrování numerického kódu zprávy M: C = Ce{M) = Me (mod n)
•  dešifrování šifry C: OT = Dd(C) = Cd (mod n)
Fermatova, resp. Eulerova věta.
D
Poznámka
•  Korektní naprogramování bez postranních kanálů není triviální (viz např. PKCS#1, RFC 3447).
•  Analogicky podepisování (hashů) zpráv (viz např. DSA)
•  Viz RSA factoring challenge (např. rozklad 212 ciferného čísla RSA-704 vynese 30 000 USD).
Diffie-Hellm
Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ
1974)
Výmena klíčů pro symetrickou kryptografii bez předchozího
kontaktu (tj. náhrada jednorázových klíčů, kurýru s kufříky, . ..
•   Dohoda stran na cyklické grupě G a jejím generátoru g (veřejné)
•  Alice vybere náhodné a a pošle ga a Bob vybere náhodné b a pošle gb
» Společným klíčem pro komunikaci je gab.
)■
Poznámka
•   Problém diskrétního logaritmu (DLP)
•   Nezbytná autentizace (man in the middle attack)
Z protokolu DH na výměnu klíčů odvozen šifrovací algoritmus EIGamal:
•  Alice zvolí cyklickou grupu G spolu s generátorem g
9 Alice zvolí tajný klíč x, spočítá h = gx a zveřejní veřejný klíč (G,g,h)
•  šifrování zprávy M: Bob zvolí náhodné y a vypočte C\ = gy a C2 = M ■ hy a pošle (Q, C2)
•  dešifrování zprávy: OT = C2/C1
Poznámka
Opět lze odvodit podepisování.
Eliptické kři
Eliptické křivky jsou rovinné křivky o rovnici tvaru y2 = x3 + ax + b a zajímavé jsou tím, že jejich bodech lze definovat operace tak, že výslednou strukturou bude komutativní grupa. Přitom uvedené operace lze efektivně provádět a navíc se ukazuje, že mají (nejen) pro kryprografii zajímavé vlastnosti - srovnatelné bezpečnosti jako RSA lze dosáhnout již s podstatně kratšími klíči. Výhodou je rovněž velké množství použitelných eliptických křivek (a tedy grup různé struktury) podle volby parametru a, b . Protokoly:
•   ECDH - přímá varianta DH na eliptické křivce (jen místo generátoru se vybere vhodný bod na křivce)
•   ECDSA - digitální podpis pomocí eliptických křivek.
Poznámka
Problém diskrétního logaritmu (ECDLP).
Navíc se ukazuje, že eliptické křivky jsou velmi dobře použitelné při
faktorizaci prvočísel.