Faktorisierung in F2

19.01.2011, 18:17

Riemannson

Faktorisierung in F2

Hallo,

ich soll $\begin{eqnarray*} X^{16}-X \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb F_2[X] \end{eqnarray*}$ faktorisieren.

in $\begin{eqnarray*} \mathbb F_2[X] \end{eqnarray*}$ sind ja 2 elemente 0 und die 1! oben wird aber -1 benutzt kann ich mit 1 rechnen da in $\begin{eqnarray*} \mathbb F_2[X] \end{eqnarray*}$ ja 1-1=1+1 sein sollte?

und ist $\begin{eqnarray*} (X^{15}+1)X \end{eqnarray*}$ nicht schon eine faktorisierung verwirrt

was muss ich dann beachten?

die polynome müssen irred. sein oder?

19.01.2011, 19:00

tmo

Auf diesen Beitrag antworten »

Ja, das ist schon eine Faktorisierung. Aber man kann natürlich noch weiter faktorisieren. Durch welche Polynome kannst du denn $\begin{eqnarray*} X^{15}-1 \end{eqnarray*}$ (Hier macht es Sinn das Minus zu behalten, weil man sich dann vielleicht an eine Identität aus der Analysis erinnert, die in $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ gilt und entsprechend in jedem Körper) noch ohne Rest teilen?

19.01.2011, 20:02

Riemannson

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
(Hier macht es Sinn das Minus zu behalten, weil man sich dann vielleicht an eine Identität aus der Analysis erinnert, die in $\begin{eqnarray*} \mathbb R \end{eqnarray*}$ gilt und entsprechend in jedem Körper)

klingt interessant aber mir kommt nichts bekannt vor verwirrt

aber ich hab noch ein polynom gefunden: $\begin{eqnarray*} (X^{15}-1)=(X-1)(X^{14}+X^{13}+X^{12}+X^{11}+X^{10}+X^{9}+X^{8}+X^{7}+X^{6}+X^{5}+X^{4}+X^{3}+X^{2}+X+1) \end{eqnarray*}$

19.01.2011, 22:13

tmo

Auf diesen Beitrag antworten »

Genau diese Identität sollte dir eigentlich bekannt vorkommen. Vor allem, wenn du die letzte (lange) Klammer mal mit dem Summenzeichen schreibst.

Und wenn du dann noch $\begin{eqnarray*} 15=3 \cdot 5 \end{eqnarray*}$ beachtest, so findest du damit sogar noch mehr Faktoren in deinem Polynom

20.01.2011, 13:25

Riemannson

Auf diesen Beitrag antworten »

also die letzte (lange) klammer: $\begin{eqnarray*} \sum_{k=0}^{14} X^k \end{eqnarray*}$ ist doch die n-te partialsumme der geometrischen reihe.?

meinst du mit 15=3*5 -> $\begin{eqnarray*} X^{15}=X^3\cdot X^5 \end{eqnarray*}$

verwirrt

20.01.2011, 13:49

Riemannson

Auf diesen Beitrag antworten »

durch etwas probieren hab auch das hier gefunden:

$\begin{eqnarray*} (X^{14}+X^{13}+X^{12}+X^{11}+X^{10}+X^{9}+X^{8}+X^{7}+X^{6}+X^{5}+X^{4}+X^{3}+X^{2}+X+1)=(X^2+X+1)(X^{12}+X^9+X^6+X^3+1) \end{eqnarray*}$

also muss man ja nur noch das weiter faktorisieren: $\begin{eqnarray*} (X^{12}+X^9+X^6+X^3+1) \end{eqnarray*}$

21.01.2011, 19:58

Harty

Auf diesen Beitrag antworten »

Können wir nicht allgemein sagen, dass $\begin{eqnarray*} (X^{15}-1) =\prod_{d|15}\Phi_d(X) \end{eqnarray*}$ , wobei $\begin{eqnarray*} \Phi_d \end{eqnarray*}$ das d-te Kreisteilungspolynom ist. Also suchen wir erstmal alle d, die 15 teilen... Das wären dann 1,3,5,15. Dabei sind:
$\begin{eqnarray*} \Phi_1(X)=X-1 \end{eqnarray*}$
$\begin{eqnarray*} \Phi_3(X)=X^2+X+1 \end{eqnarray*}$
$\begin{eqnarray*} \Phi_5(X)=X^4+X^3+X^2+X+1 \end{eqnarray*}$
Das Kreisteilungspolynom von 15 ist mir leider nicht bekannt, aber das dürfte dann durch Polynomdivison auch schnell gefunden sein. Hat dann wahrscheinlich den Grad 8, wenn das so stimmt, was du schon ausgerechnet hast!

21.01.2011, 20:06

Harty

Auf diesen Beitrag antworten »

So, hab das 15te Kreisteilungspolynom in einer Liste gefunden:
$\begin{eqnarray*} \Phi_5(X)=X^8-X^7+X^5-X^4+X^3-X+1 \end{eqnarray*}$
Würde mich freuen, wenn du das durch Polynomdivision, oder durch ausmultipizieren bestätigen könntest!!!

22.01.2011, 10:06

Riemannson

Auf diesen Beitrag antworten »

super

(an das Kreisteilungspolynom hab ich nicht gedacht)

bei mir ergibt nach nochmaliger polynomdivision: $\begin{eqnarray*} \frac {X^{12}+X^9+X^6+X^3+1}{\Phi_5}=\Phi_{15} \end{eqnarray*}$

also volle bestätigung!

22.01.2011, 12:20

wieschoo

Auf diesen Beitrag antworten »

Ihr hattet einen Satz in der Vorlesung. Multipliziert alle irreduziblen Polynome in F_2 vom Grad n mit n teilt 4.

22.01.2011, 14:26

Harty

Auf diesen Beitrag antworten »

Hm, das habe ich auch gerade gefunden! Aber warum ist denn die andere Antwort nicht richtig?
Die Kreisteilungspolynome sind doch alle irreduzibel!

22.01.2011, 16:26

wieschoo

Auf diesen Beitrag antworten »

Ja klar sind die irreduzibel aber i.A. nur über Q und Z!

22.01.2011, 17:02

Harty

Auf diesen Beitrag antworten »

Sicher das die Polynome in $\begin{eqnarray*} \mathbb F_2 [X] \end{eqnarray*}$ irreduzibel sein müssen?
Haben ja zum Beispiel auch stehen, dass
$\begin{eqnarray*} X^9-X=X(X-1)(X+1)(X^2+1)(X^2+X-1)(X^2-X-1) \end{eqnarray*}$
Aber $\begin{eqnarray*} (X^2+1) \end{eqnarray*}$ ist reduzibel in $\begin{eqnarray*} \mathbb F_2 [X] \end{eqnarray*}$ , oder nicht?

22.01.2011, 20:05

wieschoo

Auf diesen Beitrag antworten »

Das war das Beispiel für $\begin{eqnarray*} \mathbb{F}_3 \end{eqnarray*}$ .

$\begin{eqnarray*} X-1 \equiv X+1 \mod 2 \end{eqnarray*}$

Neue Frage »

Antworten »

Faktorisierung in F2

Verwandte Themen