Irreduzibilität und Primitivität

[Stephan]

Hey,

ich hab ne Frage zur Überprüfung von Polynomen auf Primitivität und damit ja auch auf Irreduzibilität ... Wenn ich jetzt ein Polynom vom Grad k auf genau das untersuchen will, muss ich dann tatsächlich alle 2^k Möglichkeiten der Teilbarkeit durchprobieren oder gibts da ein paar tricks?
Das Überprüfen von Nullstellen im GF2 wäre ja nur notwendig, aber nicht hinreichend oder?


danke schonmal

[Christian Bredtmann]

Hi!

Also meiner Meinung nach reicht es aus, dass man überprüft, ob das Polynom den Term
ohne Rest teilen kann, wobei ist. (n = Grad des Polynoms)

Beispiel:

Grad des Polynoms: n = 3
Damit ist .
Dann ist
=> ohne Rest teilbar
=> primitiv

VIele Grüße
Christian

[stinson]

Hi, ich habe eine Verständnisfrage zu der Primitivität von Polynomen.

In der Lösung zu Auf.Blatt 10 (4d)steht, dass es eine hinreichende Bedingung für Primitiviät ist, wenn das Polynom g(x) vom Grad k irreduzibel ist und 2^k-1 eine Primzahl ist.

Auf Auf.Blatt 11 (1a) ist das Polynom x^4 + x + 1 gegeben und es wird in der Lösung gesagt, dass dieses primitiv ist. Doch 2^4-1 = 15 ist keine Primzahl.

Wo ist mein Denkfehler?

Wie sieht es mit Zyklenfreiheit?

Stimmt die Bedingung: g(x) muss jedes Codewort teilen und x^n-1 mit n=2^k-1 ?

[mailerdaimon]

So wie ich das Verstanden habe geht das so:

n = 2^k-1 ist n Primzahl?
Wenn ja --> aufhören, ist primitiv
Wenn nein --> x^n+1 durch g(x) teilen
ohne Rest --> ist Primitiv
mit Rest --> nicht primitiv


>> Stimmt die Bedingung: g(x) muss jedes Codewort teilen und x^n-1 mit n=2^k-1 ?

Ich meine es muss x^n+1 heissen (ist aber im gf(2) nicht relevant soweit ich weiß), ansonsten ja!

mfg

[Xserio]

wenn man das nur mit der Primzahl machen würde, dann wären ja alle polynome vom grad 3 primitiv, das ist
aber nciht der Fall soweit ich weiß..

[mailerdaimon]

Also ich habe auf dieserWebsite folgenden Satz gefunden:

Code: Alles auswählen

Es existieren keine nichtprimitiven Polynome mten Grades, falls 2^m – 1 eine Primzahl ist.

Kann aber nicht sagen ob das richtig ist oder nicht
Ist ein Fall für ne Sprechstunde.

mfg

[Lucas Rohé]

Also ich denke, dass mailerdaimons Variante vollkommen richtig ist.
und @Xserio n = 2^k-1 soll ja ne Primzahl sein, und nicht g(x)

[Xserio]

ok.. das polynom hat den grad k= 3 also x³+(...)
dann ist n = 2^k - 1 = 7 => primzahl
demnach wäre nach der primzahlregel alle polynome vom grade 3
primitiv..also x³+x²+x+1 usw...das ist aber halt nicht richtig meine ich..
oder wo liegt jetzt mein denkfehler?:s

[Lucas Rohé]

Naja, normalerweise sucht man ja ein primitives Polynom um ein Informationswort zu codieren.
und dann gilt die Regel n=2^k-1=m+k
Also ist es schön und gut, dass deine Miniworte primitiv sind, aber du kannst sie für echte Worte nicht als Generatorpolynome benutzen.

Blah whatever... am besten nicht auf meine Meinung hören, meistens liege ich falsch

[mailerdaimon]

ok.. das polynom hat den grad k= 3 also x³+(...)
dann ist n = 2^k - 1 = 7 => primzahl
demnach wäre nach der primzahlregel alle polynome vom grade 3
primitiv..also x³+x²+x+1 usw...das ist aber halt nicht richtig meine ich..
oder wo liegt jetzt mein denkfehler?:s

Ich glaube du musst noch beachten dass, die Summer deiner Exponenten ungerade sein muss(EDIT: Ich glaub das stimmt gar nicht, hab das was verwechselt), und du das Polynom nicht durch x teilen kannst (brauchst also das +1)

damit bleiben bei grad 3 ja nur noch:

x³+x²+1
x³+1 über, und die dürften primitiv sein.

EDIT2:
So hab mir grad nochmal die Lösungen angeschaut und denke jetz ich habs verstanden.

Also damit ein Polynom Primitiv ist muss es Irreduzibel sein und durch x^n+1 Restfrei teilbar.
D.h. wir schauen erst ob das Polynom durch x teilbar oder Faktorisierbar ist und dann schauen wir ob n ein Primzahl ist! Dann gehts weiter wie oben beschrieben, wenn n Primzahl sind wir fertig da x^n+1 dann immer Restfrei durch g(x) teilbar ist wenn nicht müssen wir das per hand nachweisen!

mfg