Berechnung mit einem irreduziblen Polynom

10.06.2011, 11:32

Michael87

Berechnung mit einem irreduziblen Polynom

Meine Frage:
ich habe ein problem mit dieser aufgabe.

Sei der Körper F24 durch das irreduzible Polynom f (z) = z^4 + z^3 + 1 gegeben. Berechnen. Sie (z^3 + z +1) (z^2 +1) mod f (z) (muss nicht notwendigerweise mit Square-and-Multiply berechnet werden).

Meine Ideen:
den anfang krieg ich noch hin

(z^3 + z +1) (z^2 +1) mod (z^4 + z^3 + 1) = (z^3 + z^2 + z +1) mod ( z^4 + z^3 + 1)

aber ich habe probleme mit der modulo rechnung bei polynomen ich glaub das hab ich noch nicht verstanden

10.06.2011, 21:17

juffo-wup

Auf diesen Beitrag antworten »

RE: Berechnung mit einem irreduziblen Polynom

Zitat:

Original von Michael87
(z^3 + z +1) (z^2 +1) mod (z^4 + z^3 + 1) = (z^3 + z^2 + z +1) mod ( z^4 + z^3 + 1)

Das ist falsch.

Ich weiß nicht, ob es bessere Algorithmen gibt, aber warum errechnest du nicht einfach
$\begin{eqnarray*} (z^3 + z +1) (z^2 +1) \end{eqnarray*}$ und teilst es mit Polynomdivision durch $\begin{eqnarray*} z^4+z^3+1 \end{eqnarray*}$ ?

Übrigens sollte es $\begin{eqnarray*} \mathbb{F}_{2^4}=\mathbb{F}_{16} \end{eqnarray*}$ sein, nicht $\begin{eqnarray*} \mathbb{F}_{24} \end{eqnarray*}$

11.06.2011, 11:33

Michi87

Auf diesen Beitrag antworten »

erstmal danke für die tipps Freude

und ups ja das sollte wirklich F2^4 heissen und nicht 24

ich dachte (z^3 + z +1) (z^2 +1) = (z^3 + z^2 + z +1)
oder ich hab das mit der addition verwechselt verwirrt

also wie modulo normalerweise funktionier weiss ich 7%2 = 1
nur bei polynom versteh ich die beispiele die ich dazu gesehen hab nicht.

wenn ich das ergebniss einfach mit polynomdivision teile kommt dann das selbe raus als wenn ich es mit modulo ausgerechnet hätte ?

edit: ach ja bei der multiplikation kommt das hier raus merk ich gerade
(z^3 + z +1) (z^2 +1) = (z^5 + z^2 + z +1)

11.06.2011, 14:43

juffo-wup

Auf diesen Beitrag antworten »

Zitat:

Original von Michi87
erstmal danke für die tipps Freude

und ups ja das sollte wirklich F2^4 heissen und nicht 24

$\begin{eqnarray*} \mathbb{F}_{24} \end{eqnarray*}$ gibt es nämlich garnicht. Augenzwinkern

Zitat:

ich dachte (z^3 + z +1) (z^2 +1) = (z^3 + z^2 + z +1)
oder ich hab das mit der addition verwechselt verwirrt

Wie rechnest du denn? Warum nicht einfach ausmultiplizieren $\begin{eqnarray*} (z^3+z+1)(z^2+1)=z^5+z^3+z^3+z+z^2+1=z^5+z^2+z+1 \end{eqnarray*}$

Zitat:

also wie modulo normalerweise funktionier weiss ich 7%2 = 1
nur bei polynom versteh ich die beispiele die ich dazu gesehen hab nicht.

Man kann mit den Polynomen wie gewöhnlich rechnen, nur werden die Koeffizienten eben modulo der Primzahl (hier 2) reduziert.

Zitat:

wenn ich das ergebniss einfach mit polynomdivision teile kommt dann das selbe raus als wenn ich es mit modulo ausgerechnet hätte ?

Wie rechnest du es denn sonst aus? Bei der Polynomdivision müsstest du in jedem Schritt auch modulo 2 rechnen.

Zitat:

edit: ach ja bei der multiplikation kommt das hier raus merk ich gerade
(z^3 + z +1) (z^2 +1) = (z^5 + z^2 + z +1)

Richtig (siehe oben).

12.06.2011, 16:52

Michi87

Auf diesen Beitrag antworten »

ich bin mir nicht sicher ob ich die division richtig behersche aber kommt hier das raus

(z^5 + z^2 + z +1) / (z^4 + z^3 + 1) = z^2 + z

12.06.2011, 17:02

juffo-wup

Auf diesen Beitrag antworten »

Das kommt bei mir nicht heraus. Addiere doch mal das $\begin{eqnarray*} (z+1) \end{eqnarray*}$ -fache von $\begin{eqnarray*} z^4+z^3+1 \end{eqnarray*}$ zu $\begin{eqnarray*} z^5+z^2+z+1 \end{eqnarray*}$

13.06.2011, 13:35

Michi87

Auf diesen Beitrag antworten »

Zitat:

Original von juffo-wup
Das kommt bei mir nicht heraus. Addiere doch mal das $\begin{eqnarray*} (z+1) \end{eqnarray*}$ -fache von $\begin{eqnarray*} z^4+z^3+1 \end{eqnarray*}$ zu $\begin{eqnarray*} z^5+z^2+z+1 \end{eqnarray*}$

$\begin{eqnarray*} (z^4+z^3+1)*(z+1) = z^5 + z^4 + z + z^4 + z^3 + 1 \end{eqnarray*}$
$\begin{eqnarray*} (z^5+z^2+z+1) + (z^5 + z^4 + z + z^4 + z^3 + 1) = z^3 + z^2 +1 \end{eqnarray*}$

13.06.2011, 16:45

juffo-wup

Auf diesen Beitrag antworten »

Zitat:

Original von Michi87
$\begin{eqnarray*} (z^5+z^2+z+1) + (z^5 + z^4 + z + z^4 + z^3 + 1) = z^3 + z^2 +1 \end{eqnarray*}$

Die beiden Einsen heben sich auch noch weg, also $\begin{eqnarray*} z^3+z^2 \end{eqnarray*}$

Nun alles klar?

14.06.2011, 10:28

Michi87

Auf diesen Beitrag antworten »

ok jetzt hab ichs ... danke Freude

ich hoffe bei anderen aufgaben krieg ich das jetzt auch hin Big Laugh