Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Primitive_Polynome

Primitive_Polynome

Universität / Fachhochschule

Tags: LFSR, Primitve Polynome

michael1989 aktiv_icon

07:40 Uhr, 22.04.2019

Seit einiger Zeit beschäftige ich mich mit LFSR (Linear Rückgekoppelte Schieberegister). Nun ist es so, dass LFSR, die die maximale Periodenlänge aufweisen, durch Primitive Polynome dargestellt werden können.
Primitive Polynome gehören zu den irreduziblen Polynomen, diese können nicht in Faktoren zerlegt werden. Meine Frage ist, ob mir jemand in einfachen Worten erklären kann, was Primitive Polynome sind und man berechnet, ob ein irreduzibles Polynom primitiv ist oder nicht, ich wäre sehr dankbar dafür.
Meines Wissens nach ist

x^{4} + x^{3} + x^{2} + x + 1

zwar ein irreduzibles Polynom, aber es ist kein primitives Polynom. Die beiden Polynome

x^{4} + x + 1

und

x^{4} + x^{3} + 1

(beide vom Grad

4)

sind irreduzible und primitive Polynome. Warum?

ermanus aktiv_icon

11:57 Uhr, 22.04.2019

Hallo,
ein irreduzibles Polynom

f \in F [X]

über einem endlichen Körper

F

ist primitiv, wenn die Restklasse

x

von

X

E := F [X] / (f)

die zyklische Gruppe

E^{*}

erzeugt, wenn also

E^{*} = {1, x, x^{2}, x^{3}, \dots}

ist.
Betrachten wir als Beispiele zu dieser Begriffsbildung gemäß deinem
Beitrag die Polynome

f = X^{4} + X^{3} + X^{2} + X + 1

und

g = X^{4} + X + 1

.
Der zugrundeliegende Körper sei

F_{2}

f

und

g

sind beide irreduzibel.
Die Anzahl der Elemente in

E^{*}

ist

∣ E^{*} ∣ = 16 - 1 = 15

.

1.

f

: In

E

gilt:

x^{4} = x^{3} + x^{2} + x + 1

.
Die Potenzen von

x

sind:

1, x, x^{2}, x^{3}, x^{3} + x^{2} + x + 1, x^{5} = 1

. Mehr kommt da nicht.
Das sind weniger als 15 Elemente, also ist

f

nicht primitiv.

2. g: In

E

gilt:

x^{4} = x + 1

.
Die Potenzen von

x

sind nun:

1, x, x^{2}, x^{3}, x + 1, x^{2} + x, x^{3} + x^{2}, x^{3} + x + 1, x^{2} + 1, x^{3} + x,

x^{2} + x + 1, x^{3} + x^{2} + x, x^{3} + x^{2} + x + 1, x^{3} + x^{2} + 1, x^{3} + 1

.
Das sind die 15 verschiedenen Elemente von

E^{*}

.
Also ist

g

primitiv.

Gruß ermanus

michael1989 aktiv_icon

14:03 Uhr, 22.04.2019

Besten Dank für die schnelle und klare Antwort. Eine Frage hätte ich noch: warum kann man

x^{4} + x^{3} + x^{2} + x^{1} + x

und

x^{4} + x + 1

gleich Null setzen?

ermanus aktiv_icon

14:11 Uhr, 22.04.2019

Weil man in

F [X] / (f)

doch modulo

f

rechnet.
In

F_{2} = ℤ / 2 ℤ

rechnest du doch auch in

ℤ

modulo

2

,
indem du die Restklasse von

2

als

0

schreibst.
Bei Polynomringen und Körpererweiterungen ist doch gerade das der ganze
Sinn der Restklassenringe. Das Rechnen in

E

wird doch durch die Gleichung

f (x) = 0

bestimmt. Damit hat man sich eine "künstliche" Nullstelle von

f

verschafft.

1466844

1466812

	Status: nicht eingeloggt	Noch nicht registriert?