Matematické Fórum

Jirda · 10. 06. 2012 14:24

Zdravim,

chtel bych poprosit o radu pri reseni prikladu na roklad polynomu na ireducibilni faktory, pricemz polynomy jsou nad nejakym Zp (zbytkove tridy).

Mam tu jeden lehci priklad, na kterem bych chtel pochopit strategii reseni.

Mam polynom x^4 + x^3 + x + 1 lezicim v Z2[x]

Osobne bych to resil tak, ze budu postupne testovat mozne koreny a i ty s ohledem na to, ze se pohybujeme v Z2, muzou byt snad jen 0 a 1.

Proto pouziju Hornerovo schema.

1 1 0 1 1
0 1 1 0 1 1 0 neni koren

1 1 0 0 1 0 1 je koren
1 1 1 1 0 1 je koren
1 1 0 1 1 neni koren

zjistili jsme, ze 1 je dvojnasobnym korenem...pak by tedy rozklad mel byt takto:

(x-1)(x-1)(x^2 + 1)

Vidime, ze uz to nijak dal nerozlozime. Ale co kdyz si chci udelat zkousku?
Roznasobim a uvidim, zda mi vyjde polynom, ktery jsem rozkladal:

(x-1)(x-1) = x^2 -x -x +1 = x^2 +1 (protoze -2x mod 2 je 0)
no a (x^2 + 1) * (x^2+1) = x^4 + x^2 + x^2 + 1 = x^4 + 1, coz zrejme neodpovida rozkladanemu polynomu

Neco delam ocividne spatne. Mohl by mi nekdo rici, jak spravne u techto prikladu postupovat a kde jsem spadl do pasti?

Dekuji.

vanok · 10. 06. 2012 14:59

Ahoj ↑ Jirda:,
To je dosledok, ze si v $Z_2[X]$ a tak nemozes stotoznit funkciu asociovany polynom a polynom,
Funkcia polynom $f(x)=x^3 + x$ je nulova v $Z_2$
ale polynom $P= X^3 +X$ nie je nulovy v $Z_2[X]$ ;

Poznamka; v pedandnej notacii, polynomy sa znacia z X, a asociovane funkcie z x.
Tak si zapametajn, ze:
V konecnych telesach nie vsetko take iste ako ti hovori intuicia z $R$ alebo z $C$ .

Jirda · 10. 06. 2012 15:32

↑ vanok:

Takze me reseni je spravne, ale zpusob, jakym se snazim provest zkousku, je spatny? Existuje nejaka moznost, jak si overit korektnost sveho reseni?

vanok · 10. 06. 2012 17:21

↑ Jirda:,
Overit korene staci dosadit do daneho polynomu ich hodnoty.

Jirda · 10. 06. 2012 23:49 — Editoval Jirda (10. 06. 2012 23:52)

↑ vanok:

Predpokladam ale, ze kdybych narazil na priklad, kde i po dosazeni potencionalnich korenu by zadny nevysel "pozitivne", tak to porad neznamena, ze by byl polynom ireducibilni?

Treba tento polynom X^4 + X^3 + X + 2 v Z3 po dosazeni 0,1,2 nema koreny. Ale presto je rozlozitelny na (X^2+1)(x^2+x+2)

Vyresi se to soustavou rovnic, ze uvazujeme, ze polynom stupne 4 muze byt slozen pouze z 2 polynomu stupne 2.

Co kdybych ale dostal polynom stupne 5? Muzu pak uvazovat, ze je teoreticky rozlozitelny na dva polynomy stupne 3 a 2 a nebo existuje jeste jina kombinace?

A jeste jedna vec by me zajimala. Kdybych mel treba Z2, kolik zde existtuje normovanych polynomu?
Pro tyto stupne to je?
1 - 2 polynomy
2 4 polynomy
3 - 8 polynomu a takto umerne to roste

a jak je to s poctem ireducibilnich polynomu v danem stupni, da se vyjadrit taky vztahem?

Diky za odpoved.

vanok · 11. 06. 2012 00:06 — Editoval vanok (11. 06. 2012 00:31)

Asi som bol trocha nepresny
Da sa dokazat ze v $Z_2[X]$ polynomy stupna 2 ako aj 3 su ireduktibilne ak nemaju korene
( to sa da lahko ukazat, lebo ak by mali nejaky koren, tak vieme najst nejaku faktorizaciu)
Pochopitelne pre stupen 4 viac to nefunguje.

pre polynomy stupna $3$ ireduktibilne su $X^3+X+1$ a $X^3+X^2+1$
a jediny stupna 2 je $X^2+X+1$ .

Staci ?

Edit: nejake citanie
http://en.wikipedia.org/wiki/Irreducible_polynomial
http://www.science.unitn.it/~degraaf/co … olfact.pdf

Jirda · 11. 06. 2012 00:12

↑ vanok:

Jetse by me zajimalo, jak se ptam:

""Co kdybych ale dostal polynom stupne 5? Muzu pak uvazovat, ze je teoreticky rozlozitelny na dva polynomy stupne 3 a 2 a nebo existuje jeste jina kombinace?"

Diky

vanok · 11. 06. 2012 00:20

↑ Jirda:
Ano mozes mat taky sucin...
cize ireduktibilne stupna 5 (na priklad)... najdes tak ze medzi tymy co nemaju korene vylucis, tie co su taketo suciny.
Co vlastne studujes? precitaj si co som editoval do predosleho odkazu.

vanok · 11. 06. 2012 00:27 — Editoval vanok (11. 06. 2012 00:27)

$X^5+X^2+1 ;X^5+X^3+1;X^5+X^4+X^3+X^2+1; X^5+X^4+X^3+X +1; X^5+X^4+X^2+X +1; X^5+X^3+X^2+X +1$
Zabavil som sa trosku a tu mas ( aspon dufam) dokonaly zoznam ireduktiblych d° 5.

Bonus:
$X^4+X^3+1; X^4+X +1; X^4+X^3+X^2+X +1$

OiBobik

↑ Jirda:

Jenom doplním:

Nad konečnými tělesy existují přímo algoritmy na faktorizaci polynomů na ireducibilní činitele (viz

http://en.wikipedia.org/wiki/Berlekamp's_algorithm

) - ale ty používat bývá dost často zbytečné pro "ruční" výpočty.

Jinak nad konečným tělesem se dá spočítat nejen počet ireducibilních polynomů zadaného stupně, ale dokonce součin všech těchto (monicky vzatých) ireducibilních polynomů (přičemž s algoritmem na faktorizaci dostanu tím pádem rovnou i seznam těch ireducibilních polynomů). K těmto a příbuzným tématům můžu doporučit skripta Libora Barta a Jiřího Tůmy (obdržení součinu ireducibilních polynomů daného stupně, respektive počtu ireducibilních polynomů daného stupně, je popsán v kap. 5; faktorizace polynomů v kap. 6).

vanok · 11. 06. 2012 00:32

↑ OiBobik:
Ahoj, ano zaujimava a velmi uzitocna poznamka.

Jirda · 11. 06. 2012 00:35

↑ vanok:

Diky.

Co vkastne studuju? Pokud je to myslena otazka, co hledam za odpovedi a ne co studuji za obor, tak se pripravuju na zkousku z algebry a snazim si ujasnit tuhle kapitolu polynomu se zbytkovyma tridama. Je tu cela rada ruznych typu prikladu a tak jsem si chtel obecne ujasnit principy kolem toho.

Matematické Fórum

#1 10. 06. 2012 14:24

Rozložení polynomu na ireducibilní faktory

#2 10. 06. 2012 14:59

Re: Rozložení polynomu na ireducibilní faktory

#3 10. 06. 2012 15:32

Re: Rozložení polynomu na ireducibilní faktory

#4 10. 06. 2012 17:21

Re: Rozložení polynomu na ireducibilní faktory

#5 10. 06. 2012 23:49 — Editoval Jirda (10. 06. 2012 23:52)

Re: Rozložení polynomu na ireducibilní faktory

#6 11. 06. 2012 00:06 — Editoval vanok (11. 06. 2012 00:31)

Re: Rozložení polynomu na ireducibilní faktory

#7 11. 06. 2012 00:12

Re: Rozložení polynomu na ireducibilní faktory

#8 11. 06. 2012 00:20

Re: Rozložení polynomu na ireducibilní faktory

#9 11. 06. 2012 00:27 — Editoval vanok (11. 06. 2012 00:27)

Re: Rozložení polynomu na ireducibilní faktory

#10 11. 06. 2012 00:27 — Editoval OiBobik (11. 06. 2012 00:36)

Re: Rozložení polynomu na ireducibilní faktory

#11 11. 06. 2012 00:32

Re: Rozložení polynomu na ireducibilní faktory

#12 11. 06. 2012 00:35

Re: Rozložení polynomu na ireducibilní faktory

Zápatí