matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenUni-Lineare Algebrareduzible Polynome
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Uni-Lineare Algebra" - reduzible Polynome
reduzible Polynome < Lineare Algebra < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Lineare Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

reduzible Polynome: Polynom reduzibel oder nicht?
Status: (Frage) beantwortet Status 
Datum: 16:44 Mi 13.07.2005
Autor: marthasmith

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




        
Bezug
reduzible Polynome: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
reduzible Polynome: danke
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:05 Mi 13.07.2005
Autor: marthasmith

Hey Hanno,

cool, das war ja man nicht besonders helle von mir da nicht drauf zu kommen.
:o)

Alice

Bezug
        
Bezug
reduzible Polynome: Folgefrage
Status: (Frage) beantwortet Status 
Datum: 11:40 Do 14.07.2005
Autor: marthasmith

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



Bezug
                
Bezug
reduzible Polynome: Antwort
Status: (Antwort) fertig Status 
Datum: 12:37 Do 14.07.2005
Autor: holy_diver_80

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

Bezug
                
Bezug
reduzible Polynome: Berechnung Restpolynome
Status: (Frage) beantwortet Status 
Datum: 17:39 Do 14.07.2005
Autor: marthasmith

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


Bezug
                        
Bezug
reduzible Polynome: Mitteilung + Hilfe
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                
Bezug
reduzible Polynome: Korrekturmitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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!

Bezug
                        
Bezug
reduzible Polynome: Antwort
Status: (Antwort) fertig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Lineare Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]