Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Faktorisierung von Polynomen über Fp

Faktorisierung von Polynomen über Fp

Universität / Fachhochschule

Polynome

Tags: polynom

Stochastikerin

13:45 Uhr, 09.04.2025

Ich habe folgenden Algorithmus zur Bestimmung einer Faktorisierung von Polynomen über

F_{p},

welche auf dem Satz "Das Polynom

x^{p^{n}} - x

ist das Produkt aller normierter irreduzibler Polynome in

F_{p} [x]

vom Grad

d

mit

d

teilt n" beruht:

Eingabe: Ein (normiertes) Polynom

f \in F_{p} [x]

mit

p > 2

Ausgabe: Nachweis, dass

f

irreduzibel ist, oder einen echten Faktor von

f

1)

Setze

d = 1

und

g = x

2)

Berechne

g = g^{p^{d}} mod f

und bestimme h=ggT(f,g-x)

3)

Ist

h \neq 1

und

h \neq f,

so gebe

h

zurück (Bedeutet

h

ist Faktor). Ist

h = 1

und

d \geq

deg(f)/2 abgerundet, so gebe zurück, dass

f

irreduzibel.
Sonst:

d = d + 1

und wieder zu Punkt 2

4)

Wähle ein zufälliges

g \in F_{p} [x],

deg(g)<deg(f). Bestimme h=ggT(

g^{\frac{p^{d} - 1}{2}} - 1, f)

5)

Ist

h \neq 1

und

h \neq f,

so gebe

h

zurück. Sonst wieder zu Punkt 4

Jetzt habe ich folgendes Polynom:

x^{4} - x - 1 \in F_{3} [x]

1) d = 1, g = x

2) g = x^{3^{1}} mod f = x^{3}

h =

ggT(

x^{4} - x - 1, x^{3} - x) = 1

d = 1

und somit noch kleiner als deg(f)/2, können wir wieder zu Punkt 2 mit

d = 2

2) g = x^{3^{2}} mod f = x^{9} mod f = x^{3} + 2 x^{2} + x

. h=ggT((

x^{3} + 2 x^{2} + x) - x, x^{4} - x - 1) = x^{2} + 2

Stimmt das bis hierhin?
Denn es handelt sich hier um eine Klausurprüfungsaufgabe, welche lediglich mit einem Taschenrechner gerechnet werden darf (und vergleichsweise wenig Punkte gibt). Deswegen bin ich hier etwas überfragt..

Mir ist bewusst, dass das Polynom

f = x^{4} - x - 1

nur Faktoren von maximal 2. Grades haben kann.
Ersten Grades sind Nullstellen.

f (0) mod 3 = 2

f (1) mod 3 = 2

f (2) mod 3 = 1

Also schon mal keine Faktoren ersten Grades.

2. Grades: x^2+ax+b mit

a, b \in {0, 1, 2}

also Möglichkeiten:

x^{2}

x^{2} + x

x^{2} + 2 x

usw...

Aber für mich wären das viel zu viele Möglichkeiten zum rumprobieren..

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Polynomfunktionen / ganzrationale Funktionen - Einführung

HAL9000

16:52 Uhr, 09.04.2025

Ich verstehe deine Rechnung nicht: Ich komme auf

ggT (x^{3} + 2 x^{2}, x^{4} - x - 1) = 1

statt

x^{2} + 2

Stochastikerin

21:08 Uhr, 09.04.2025

Du hast recht!

Nehmen wir an, dass

h = 1

und

d = 2

und somit

2 = d \geq

deg(f)/2
Dann wären wir hier fertig und hätten, dass

f

irreduzibel ist.
Nun lautet die Aufgabe aber, es zu faktorisieren; Deswegen bin ich mir unsicher..

HAL9000

08:51 Uhr, 10.04.2025

> Dann wären wir hier fertig und hätten, dass

f

irreduzibel ist.

Was auch stimmt:

x^{4} - x - 1

hat keine Nullstellen, also bleibt allenfalls zu untersuchen, ob es ein Produkt zweier quadratischer irreduzibler Polynome ist.

In

F_{3} [x]

gibt es genau drei solche irreduziblen Polynome:

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

Da es kein

x^{3}

im Produktergebnis

x^{4} - x - 1

gibt, bleiben allenfalls

{(x^{2} + 1)}^{2}

oder

(x^{2} + x - 1) (x^{2} - x - 1)

als zu untersuchende Varianten übrig, aber in beiden Fällen haben wir Absolutglied 1 statt -1. Damit ist die Irreduzibilität von

x^{4} - x - 1

F_{3} [x]

klar.

Stochastikerin

18:03 Uhr, 10.04.2025

Vielen Dank :-)

Eine abschließende Sache hätte ich noch:

>

Schritt 3 besagt:

Ist

h \neq f

und

h \neq 1,

so ist

h

ein Faktor. Ist

h = 1

und

d \geq

deg(f)

/ 2

(abgerundet), dann ist

f

irreduzibel.

Ansonsten:

d = d + 1

und wieder von Schritt 2.

Das verstehe ich soweit.
Wie komme ich aber zu Schritt 4 und 5?

Ich habe folgendes Polynom:

f = x^{8} + x^{6} + x^{5} + x^{4} + x^{3} + 2 x^{2} + 2 x + 1 \in F_{3} [x]

. deg(f)/2

= 4

p = 3, d = 1,

also ist

g = x^{3}, h =

ggT(

f, x^{3} - x) = 1

p = 3, d = 2,

also ist

g = x^{9}, h =

ggT(

f, x^{9} - x) = 1

p = 3, d = 3,

also ist

g = x^{27},

h=ggT(

f, x^{27} - x) = 1

p = 3, d = 4,

also ist

g = x^{81},

h=ggT

(f, x^{81} - x) = 1

Jetzt würde ich laut Algorithmus sagen, dass

f

irreduzibel, weil bei

d = 4

immer noch

h = 1

.
Das Problem:
Die Lösung sagt, dass

f = (x^{4} + x + 2) \cdot (x^{4} + x^{2} + 2)

Ich hänge ein bisschen an dem Schritt mit der "Entscheidung", ob das Polynom nun irreduzibel oder nicht ist bzw wie ich zu Schritt 4 gelange. Hat das eventuell etwas damit zu tun, in welchem Körper ich bin bzw. mit "

g = g^{p^{d}} mod f)

HAL9000

10:54 Uhr, 14.04.2025

p = 3, d = 4

, also ist

g = x^{81}, h = ggT (f, x^{81} - x) = 1

Mein CAS sagt was anderes - nämlich

h = f

, d.h.

x^{81} - x

ist durch

f

teilbar!!!

Deine algorithmische Beschreibung ist in Punkt 3) ein wenig konfus. Ich nehme an, folgendes ist gemeint:

3.1) Weder

h = 1

noch

h = f

: Gebe

h

als Faktor zurück (d.h.

f

ist reduzibel).

3.2)

h = 1

:
3.2.1)

d \geq \frac{1}{2} deg (f)

: Gebe zurück, dass

f

irreduzibel.
3.2.2)

d < \frac{1}{2} deg (f)

: Setze

d = d + 1

und weiter mit 2).

3.3)

h = f

: Weiter mit 4).

Hier erhältst du nun im Schritt

d = 4

das Polynom

h = f

. Weiter geht es dann mit 4). Wenn ich das Verfahren richtig verstanden habe, gelangt man dann und nur dann zu Punkt 4), wenn

f

zerlegbar ist in zwei oder mehr irreduzible Polynome vom Grad

d

. Die Punkte 4) und 5) dienen nur der Bestimmung eines solchen Faktors - dass

f

in diesem Zweig reduzibel ist, steht ohnehin fest.

P.S.: Im anderen Thread bist du auch noch eine Antwort schuldig. Eigentlich hatte ich die abwarten wollen, bis ich hier antworte...

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1590658

1590628

	Status: nicht eingeloggt	Noch nicht registriert?