reduzible Polynome < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo,
die Frage lautet:
Untersuche ob die 3 Polynome über GF(3) reduzibel oder irreduzibel sind:
$ [mm] p_1(z)=z^2+z+1$
[/mm]
$ [mm] p_2(z)=z^3+2z+1$
[/mm]
[mm] $p_3(z)=z^3+z^2+z+1$
[/mm]
Ich habe dazu gefunden:
$p(z)$ ist irreduzibel, wenn es ein Primpolynom ist, d.h. im Falle GF(3) keine
Wurzeln $z=0,z=1,z=2$ hat.
Dann habe ich eine einfache Polynomdivision gemacht,
also: [mm] $p_1(z):z$,$p_1(z):(z-1)$ [/mm] etc. und dabei festgestellt, dass
alle irreduzibel sind. Das kommt mir aber spanisch vor.
Außerdem erscheint mir der Aufwand recht hoch, weil man soviel
rechnen muss.
Was habe ich falsch gemacht?
Falls nix, wie würde es schneller gehen? (Kann man es vielleicht irgendwie "sehen", ob es reduzibel ist?)
Danke schon mal für Antworten
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:56 Mi 13.07.2005 | | Autor: | Hanno |
Hallo Martha!
Nehmen wir an, es sei ein Polynom [mm] $p\in [/mm] GF(3)[x]$. 2. oder 3. Grades gegeben, welches auf Teilbarkeit durch andere Polynome bzw. auf Irreduzibilität zu prüfen ist. Nehmen wir an, es sei nicht irreduzibel. Dann gibt es ein nichtkonstantes Polynom $p'$ mit [mm] $p'\vert [/mm] p$ und [mm] $grad(p')\leq [/mm] grad(p)-1$. Dann muss der Grad dieses Polynomes entweder 1 oder 2 sein. Im ersteren Falle ist $p$ ein Linearfaktor, d.h. $p$ muss eine Nullstelle besitzen. Im zweiten Fall scheidet $grad(p)=2$ aus, also $grad(p)=3$ (nach Annahme). Betrachten wir nun das Polynom $p''$ mit [mm] $p=p'\cdot [/mm] p''$. Da $grad(p')=2$, muss nach der Gradformel $grad(p'')=1$ gelten. D.h. $p''$ ist ein Linearfaktor, der $p$ teilt; insbesondere besitzt $p$ eine Nullstelle.
Du siehst: sollst du ein Polynom vom grad 2 oder 3 auf Irreduzibilität prüfen, so ist es sicher irreduzibel, wenn es keine Nullstellen besitzt. Es reicht also aus, in deinem Falle einfach $0,1,2,3$ einzusetzen und somit zu prüfen, ob die dir gegebenen Polynome Nullstellen besitzen. Dabei musst du keine einzige Polynomdivision durchführen.
Ich finde den Aufwand nicht besonders hoch, ein einfacheres Verfahren ist mir in diesem Falle auch nicht bekannt.
Ich hoffe ich konnte dir helfen.
Liebe Grüße,
Hanno
|
|
|
| |
|
Hey Hanno,
cool, das war ja man nicht besonders helle von mir da nicht drauf zu kommen.
:o)
Alice
|
|
|
| |
|
Hallo,
meine Polynome sind daher alle irreduzibel.
Nun kommt die Folgefrage:
Welches der angegebenen Polynome
(also die von oben:
[mm] $p_1(z)=z^2+z+1$
[/mm]
[mm] $p_2(z)=z^3+2z+1$
[/mm]
[mm] $p_3(z)=z^3+z^2+z+1$)
[/mm]
ist zur Erzeugung eines [mm] GF(3^3) [/mm] geeignet? Welche Bedingung muss darüber hinaus gelten?
Meine Antwort:
Es ist nur [mm] $p_2$ [/mm] bzw. [mm] $p_3$ [/mm] geeignet, da [mm] $p_1$ [/mm] nur den Grad 2 hat.
Welche Bedingung darüber hinaus gelten muss, ist mir unklar
Richtig?
Weitere Frage:
Für welches der oben genannten Polynome (d.h. es bleiben nur noch
[mm] $p_2$ [/mm] und [mm] $p_3$) [/mm] passt die folgende Tabelle:
i $z^imodp(z)$
0 1
1 z
2 [mm] z^2
[/mm]
3 z+2
und da habe ich [mm] $z^3 [/mm] $ jeweils durch [mm] $p_2$ [/mm] und [mm] $p_3$ [/mm] geteilt, da
kam aber nicht als Rest $z+2$ raus.
Wäre dankbar um Hilfe,
Alice
|
|
|
| |
|
Hallo Alice,
Damit ein Polynom für die Erzeugung eines endlichen Körpers [mm] GF(p^k) [/mm] taugt, muss es modulo p irreduzibel sein. Für k [mm] \le [/mm] 3 ist diese Bedingung genau dann erfüllt, wenn das Polynom modulo p keine Nullstellen hat.
[mm] p_2, [/mm] und [mm] p_3 [/mm] erfüllen diese Bedingung, funktionieren also.
Nun zu der anderen Frage. Es gilt:
[mm] z^3 [/mm] - [mm] (z^3 [/mm] + 2z +1) = -2z +1 [mm] \equiv [/mm] z + 2 mod 3
Also ist [mm] p_2 [/mm] unser "Gewinner".
Beachte: Wir rechnen in [mm] \IZ_3[z]. [/mm] Also sind die Koeffizienten der Polynome nur modulo 3 bestimmt.
Liebe Grüße,
Holy Diver
|
|
|
| |
|
Hallo,
soweit bin ich nun gekommen.
Jetzt suche ich also zu dem Polynom
[mm] $p_3(z)=z^3+2z+1$ [/mm] die Restpolynome $z^imodp(z)$ für
$i=4,...,25$
Dazu steht in meinem Skript" man kann davon Gebrauch machen, dass
der Rest für [mm] z^{i+1} [/mm] aus dem für [mm] z^i [/mm] ermittelt werden kann."
das wäre dann mit gegebenem i=3:
i z^imodp(z)
3 z+2
4: $z(z+2)$ [mm] $z^2+2z$
[/mm]
5: $ [mm] z(z^2+2z)$=z^3+2z^2
[/mm]
In dem Beispiel was ich habe, wird dann wenn man die Maximalpotenz
erreicht p(z) addiert, (weil sich der Rest dadurch nicht ändert?)
[mm] $z^3+2z^2+p(z)=z^3+2z^2+z^3+2z+1=2z^3+2z^2+2z+1=2z^2$
[/mm]
Irgendwie aber komisch, könnte sich da jemand zu äußern wie man
das genau macht?
Danke,
Alice
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:07 Fr 15.07.2005 | | Autor: | statler |
Hallo,
man arbeitet jetzt im Polynomring F3[Z] mod p(Z), und der ist als Vektorraum über F3 3dimensional mit 9 Elementen. 1, Zquer und ZquerQuadrat sind eine Basis, und die Menge der Elemente entsteht natürlich, indem ich für jedes Basiselement noch alle 3 möglichen Koeffizienten zulasse und die Linearkombinationen bilde. Im Restklassenring ist Zhoch3 = -2Z-1 = Z+2 und dann ist Zhoch4 = Z mal Zhoch3 = Z(Z+2) = ZQuadrat + 2Z, Zhoch5 = Z mal Zhoch4 = Z(ZQuadrat + 2Z) = Zhoch3 + 2ZQuadrat = Z + 2 +2ZQuadrat = 2ZQuadrat + Z + 2 usw. Wenn man das bis Zhoch25 durchzieht, muß es sich irgendwann wiederholen, weil es ja nur 9 verschiedene Elemente gibt (in der multiplikativen Gruppe sogar nur 8), es kann also nicht so aufwendig sein. Sind meine Formeln eigentlich verständlich?
Gruß aus Harburg und schönes Wochenende
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:18 Mo 18.07.2005 | | Autor: | statler |
Oh Mist,
als VR über F3 sind es natürlich 3hoch3 = 27 Elemente, also hat die multiplikative Gruppe 26 Elemente. Die Restklasse von X mod p(X) erzeugt die multiplikative Gruppe, ich habe es am Wochenende nachgerechnet. Meinen Fehler bitte ich zu entschuldigen.
Alter ist grausam!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:46 Fr 15.07.2005 | | Autor: | Hanno |
Hallo Alice!
Ich konnte deine Ausführungen nicht ganz nachvollziehen, wollte dir aber hinsichtlich des Gewinnens neuer Restpolynome aus alten eine Hilfe geben, d.h. auf
> Dazu steht in meinem Skript" man kann davon Gebrauch machen, dass der Rest für $ [mm] z^{i+1} [/mm] $ aus dem für $ [mm] z^i [/mm] $ ermittelt werden kann."
eingehen.
Nehmen wir an, wir wüssten für [mm] $z^i$ [/mm] bereits, dass
[mm] $z^i [/mm] = [mm] q_i\cdot p_3+r_i$.
[/mm]
Wir wollen aus dieser Darstellung nun eine für [mm] $z^{i+1}$ [/mm] gewinnen. Multiplizieren wir dazu beide Seiten mit $z$, so erhalten wir
[mm] $z^{i+1}=q_i\cdot z\cdot p_3+r_i\cdot [/mm] z$.
Nehmen wir an, es sei [mm] $3>grad(r_i)+1$, [/mm] so ist die Darstellung [mm] $z^{i+1}=(q_i\cdot z)\cdot p_3+r_i\cdot [/mm] z$ die gesuchte Zerlegung. Betrachten wir nun den Fall [mm] $grad(r_i)=2$, [/mm] d.h. [mm] $r_i=az^2+bz+c$. [/mm] Dann ist [mm] $r_i\cdot z=az^3+bz^2+cz$; [/mm] setzen wir die [bereits bekannte] Zerlegung [mm] $z^3=q_3\cdot p_3+r_3$ [/mm] ein, erhalten wir [mm] $r_i\cdot z=a(q_3\cdot p_3+r_3)+bz^2+cz$, [/mm] d.h. [mm] $z^{i+1}=(q_i\cdot z)\cdot p_3+r_i\cdot z=(q_i\cdot z)\cdot p_3+a(q_3\cdot p_3+r_3)+bz^2+cz=(q_i\cdot z+a\cdot q_3)\cdot p_3+bz^2+cz+r_3$, [/mm] womit die gewünschte Darstellung von [mm] $z^{i+1}$ [/mm] gefunden wäre.
So, dazu ein Beispiel:
Es ist [mm] $z^3=1\cdot (z^3+2z+1)-2z-1$. [/mm] Multiplikation mit $z$ ergibt [mm] $z^4=z\cdot (z^3+2z+1)-2z^2-z$. [/mm] Dies ist der erste der genannten Fälle; da der Grad des Restpolynomes kleiner gleich 1 war, erhalten wir nach Multiplikation eine gültige Zerlegung von [mm] $z^{i+1}$, [/mm] in diesem Falle [mm] $z^4$. [/mm] Multiplizieren wir nun abermals mit $z$, so ergibt sich: [mm] $z^4 [/mm] = [mm] z^2(z^3+2z+1)-2z^3-z^2$. [/mm] Jetzt müssen wir [mm] $z^3$ [/mm] im Rest durch [mm] $1\cdot (z^3+2z+1)-2z-1$ [/mm] ersetzten; wir erhalten [mm] $z^4 [/mm] = [mm] z^2(z^3+2z+1)-2z^3-z^2=z^4 [/mm] = [mm] z^2(z^3+2z+1)-2((z^3+2z+1)-2z-1)-z^2=(z^2-2)(z^3+2z+1)-z^2+4z+1$, [/mm] und somit die gewünschte Zerlegung von [mm] $z^5$. [/mm] So fahren wir nun fort und erhalten leicht alle gewünschten Zerlegungen der [mm] $z^i,i=3,4,...,25$.
[/mm]
Ich hoffe, dass ich dir helfen konnte - ansonsten frag' bitte nach.
Liebe Grüße,
Hanno
|
|
|
|
