Matematické Fórum

Honza90

Dobrý den. Už podruhé se vracím k tomuto tématu a to z toho důvodu, že mi stále nejsou jasné následující věci. V konečných polích se sčítá a násobí modulárně. V poli o p prvcích, kde p je prvočíslo, počítám mod p. Když má pole p^n prvků zvolím si polynomiální reprezentaci prvků, počítám potom mod "polynom". Nějak se z toho vytratí ta modulární artimetika, když v poli o 4 prvích počítám mod x^2 + x + 1, to už se ale ani trochu nepodobá mod 4. To je jedna věc. druhá věc nalezení redukčního polynomu pro dané neprvočíselné pole. Mám-li třeba pole GF(25) nezbývá mi nic jiného než mezi sebou vynásobit 20 různých polynomů a pak určit, jak by měl vypadat nerozložitelný polynom. Co se vlastně myslí tím nerozložitelný? Znamená to, že nelze napsat jako součin dvou prvku toho pole? Jak to pak ale rozhodneme, když pro výpočet součinu dvou prvků prvně potřebujeme znát ten redukční polynom? Ještě by mě zajímalo, jestli existuje nějaká rychlejší cesta k nalezení redukčního polynomu(např. pomocí ideálů). Díky za odpověď třeba jen na některou z otázek.

kompik · 24. 10. 2012 12:46

Když má pole p^n prvků zvolím si polynomiální reprezentaci prvků, počítám potom mod "polynom". Nějak se z toho vytratí ta modulární artimetika, když v poli o 4 prvích počítám mod x^2 + x + 1, to už se ale ani trochu nepodobá mod 4.

To nie je celkom pravda.
Pole s $p^n$ prvkami mozeme dostat ako $\mathbb Z_p[x]/(p(x))$ , kde $p(x)$ je lubovolny ireducibilny polynom $p(x)\in \mathbb Z_p[x]$ stupna $n$ .
Cize naozaj pocitame modulo polynom, ale vsetky operacie s polynomami robime v $\mathbb Z_p$ , teda ked pocitas s koeficientami, pouzivas tam modulo p.

To je jedna věc. druhá věc nalezení redukčního polynomu pro dané neprvočíselné pole. Mám-li třeba pole GF(25) nezbývá mi nic jiného než mezi sebou vynásobit 20 různých polynomů a pak určit, jak by měl vypadat nerozložitelný polynom. Co se vlastně myslí tím nerozložitelný? Znamená to, že nelze napsat jako součin dvou prvku toho pole?

Pracujme nad polom $F$ . Polynom $p(x)\in F[x]$ je ireducibilny, ak sa neda zapisat ako sucin $p(x)=f(x)g(x)$ netrivialnym sposobom. T.j. ak ho rozlozim na sucin, jeden z tych polynomov musi byt konstantny.

Ked uz si navrhol GF(25), skusme sa pozriet na tento pripad. Radi by sme zostrojili pole, ktore ma $5^2$ prvkov. To dostaneme ako $\mathbb Z_5[x]/(p(x))$ , ak vieme najst nejaky polynom $p(x)\in\mathbb Z_5[x]$ , ktory je ireducibilny.

Pre polynomy stupna 2 a 3 na to, aby sme ukazali ireducibilitu, staci skontrolovat, ze nemaju korene. (Pre vyssie stupne to uz nie je taketo jednoduche.) Cize chceme najst polynom stupna 2, ktory nema v $\mathbb Z_5$ koren.

Staci sa nam obmedzit na monicke (normovane) polynomy $x^2+ax+b$ . To je 25 moznosti. Moznosti, kde $b=0$ nemusime skusat, lebo pre tie je ocividne $x=0$ korenom. Uz mame len 20 moznosti. Skusme zacat po rade: $p(x)=x^2+x+1$ . Ak don dosadim 0,1,2,3,4 (a pocitam modulo 5), tak postupne dostaneme 1,3,2,3,1. Cize tento polynom naozaj nema koren.

Takze $\mathbb Z_5[x]/(x^2+x+1)$ je pole, ktore ma 25 prvkov. Tie mozeme reprezentovat 25 polynomami stupna mensieho ako 2.

Samozrejme 25 prvkove pole by sme zostrojit aj pomocou ineho ireducibilneho polynomu stupna 2. Podla vety z prednasky ale vieme, ze aspon jedno 25 prvkove pole existuje a ze lubovolne dve take polia su izomorfne - cize v istom zmysle dostaneme "to iste pole" aj pre inu volbu polynomu.

Honza90 · 24. 10. 2012 16:47

↑ kompik:
Díky za vyčerpávající a zároveň srozumitelnou odpověď.

Nás na přednášce nechali násobit ty členy mezi sebou a eliminací nevhodných součinů se postupně dobrat redukčního polynomu. Nevíš, jestli pro každé konečné pole bude ten polynom normovaný, nebo se to vztahuje třeba jen na určitou charakteristiku a řád pole?

kompik · 24. 10. 2012 17:13

↑ Honza90:
Priznam sa, ze celkom nerozumiem otazke.

Myslis tym nieco taketo?

Hladame ireducibilne polynomy stupna 4 nad Z2.

Obmedzime sa na monicke (ale tu ine ani nie su), takze mame 16 moznosti:
$x^4$ , $x^4+1$ , $x^4+x$ , $x^4+x+1$ , $x^4+x^2$ , $x^4+x^2+1$ , $x^4+x^2+x$ , $x^4+x^2+x+1$ , $x^4+x^3$ , $x^4+x^3+1$ , $x^4+x^3+x$ , $x^4+x^3+x+1$ , $x^4+x^3+x^2$ , $x^4+x^3+x^2+1$ , $x^4+x^3+x^2+x$ , $x^4+x^3+x^2+x+1$ .

Vylucime vsetky, kde je nula je koren, zostalo nam ich 8:
$x^4+1$ , $x^4+x+1$ , $x^4+x^2+1$ , $x^4+x^2+x+1$ , $x^4+x^3+1$ , $x^4+x^3+x+1$ , $x^4+x^3+x^2+1$ , $x^4+x^3+x^2+x+1$ .

Dalej vylucime tie, kde 1 je koren, co su v tomto pripade presne tie, ktore maju parny pocet clenov.
$x^4+x+1$ , $x^4+x+1$ , $x^4+x^2+1$ , $x^4+x^3+1$ , $x^4+x^3+x^2+x+1$ .

Tychto 5 polynomov su presne polynomy stupna 4, ktore nemaju v Z2 korene. Ale este stale nemusia byt ireducibilne - to sa stane v pripade, ze su sucinom dvoch ireducibilnych polynomov stupna dva. Povedzme, ze vieme (uz sme predtym zratali), ze jediny ireducibilny polynom stupna dva je $x^2+x+1$ .
Takze este treba vylucit $(x^2+x+1)^2=x^4+x^2+1$ .

Zostali nam 4 polynomy:
$x^4+x+1$ , $x^4+x+1$ , $x^4+x^3+1$ , $x^4+x^3+x^2+x+1$ .
Tieto 4 polynomy su presne ireduciblne polynmy stupna 4 nad Z2. Cize ak chceme dostat pole, ktore ma $2^4$ prvkov, pouzijeme niektory z nich.

kompik · 24. 10. 2012 17:14

Honza90 napsal(a):
Nevíš, jestli pro každé konečné pole bude ten polynom normovaný, nebo se to vztahuje třeba jen na určitou charakteristiku a řád pole?

Vynasobenie polynomu konstantou neovplyvni, ci je ten polynom ireducibilny - takze si mozes vybrat, ze budes mat normovany polynom.

Honza90 · 24. 10. 2012 17:37

↑ kompik:
teď už je mi to jasný, díky za pomoc ;)

Matematické Fórum

#1 21. 10. 2012 15:46 — Editoval Honza90 (21. 10. 2012 15:57)

redukční polynom v neprvočíelném poli

#2 24. 10. 2012 12:46

Re: redukční polynom v neprvočíelném poli

#3 24. 10. 2012 16:47

Re: redukční polynom v neprvočíelném poli

#4 24. 10. 2012 17:13

Re: redukční polynom v neprvočíelném poli

#5 24. 10. 2012 17:14

Re: redukční polynom v neprvočíelném poli

Honza90 napsal(a):

#6 24. 10. 2012 17:37

Re: redukční polynom v neprvočíelném poli

Zápatí