Addition und Multiplikation von Polynomen in endlichen Körpern

17.10.2015, 22:09

icetea01

Addition und Multiplikation von Polynomen in endlichen Körpern

Hallo, folgendes Beispiel:

Man berechne die Summe und das Produkt der Elemente $\begin{eqnarray*} (1+x^{2})+2x \end{eqnarray*}$ und $\begin{eqnarray*} (1+x^{2})+1+2x \end{eqnarray*}$ in GF(9) isomorph zu $\begin{eqnarray*} \mathbb Z_{3}[x]/(1+x^{2}) \end{eqnarray*}$ .

Das $\begin{eqnarray*} \mathbb Z[x]_{3}/(1+x^{2}) \end{eqnarray*}$ hat 9 Elemente, wenn ich das richtig verstanden habe (hab in der Literatur ein ähnliches Beispiel gefunden, da wirds aber nicht so genau erläutert).

Wie die Multiplikation und Addition von Polynomen geht weiß ich schon. Wenn ich beispielsweise die beiden Polynome miteinander multipliziere, dann kommt $\begin{eqnarray*} x^{4}+4x^{3}+7x^{2}+6x+2 \end{eqnarray*}$ raus. Dann müsste ich das durch $\begin{eqnarray*} 1+x^{2} \end{eqnarray*}$ dividieren. Als Rest kommt bei mir dann $\begin{eqnarray*} 2x+6 \end{eqnarray*}$ raus. Doch es gibt ja 9 verschiedene Restmöglichkeiten, welcher Möglichkeit entspricht dann mein Ergebnis? Wie gehe ich da dann vor?

Danke schon mal im Voraus!
lg

17.10.2015, 23:13

HAL 9000

Auf diesen Beitrag antworten »

Alle Koeffizienten sind modulo 3 zu betrachten, d.h. in $\begin{align*} \mathbb{Z}_3[x] \end{align*}$ , und damit erst recht in $\begin{align*} \mathbb{Z}_3[x]/(x^2+1) \end{align*}$ gilt $\begin{align*} 2x+6 = 2x \end{align*}$ .

EDIT: Offenbar hast du dich aber bereits bei dem 2x+6 verrechnet. unglücklich

18.10.2015, 12:27

icetea01

Auf diesen Beitrag antworten »

Wenn ich die Polynome normal miteinander multipliziere, kommt bei mir $\begin{eqnarray*} x^{4}+4x^{3}+7x^{2}+6x+2 \end{eqnarray*}$ raus. D.h., ich muss jetzt bei allen Koeffizienten mod 3 rechnen? Dann erhalte ich: $\begin{eqnarray*} x^{4}+x^{3}+x^{2}+2 \end{eqnarray*}$ . Wenn ich das durch ( $\begin{eqnarray*} x_{2}+1 \end{eqnarray*}$ ) dividiere, erhalte ich als Rest $\begin{eqnarray*} 2-x \end{eqnarray*}$ . Richtig so, oder versteh ich da was falsch?

18.10.2015, 13:23

Elvis

Auf diesen Beitrag antworten »

Ja, das ist richtig, aber es ist noch nicht die ganze Wahrheit. Ich sehe 3 verschiedene Möglichkeiten, zum Ziel zu kommen.

1.) In $\begin{eqnarray*} \mathbb Z_3[x]/(x^2+1) \end{eqnarray*}$ ist $\begin{eqnarray*} x^2+1\equiv 0 \end{eqnarray*}$ , also $\begin{eqnarray*} (1+x^2+2x)(1+x^2+1+2x)\equiv 2x(2x+1)\equiv x^2+2x \; (mod(x^2+1)) \end{eqnarray*}$

2.) So wie Du es gemacht hast : $\begin{eqnarray*} (x^2+2x+1)(x^2+2x+2)=x^4+4x^3+7x^2+6x+2\equiv 2x-4 \; (mod(x^2+1)) \end{eqnarray*}$

3.) So wie HAL 9000 vorgeschlagen hat : $\begin{eqnarray*} x^4+x^3+x^2+2\equiv -x+2 \; (mod(x^2+1)) \end{eqnarray*}$

Als Standardlösung schlage ich $\begin{eqnarray*} 2x+2 \end{eqnarray*}$ vor, weil das aus der 2. und 3. Lösung offensichtlich mod 3 kongruent ist und Koeffizienten in $\begin{eqnarray*} \mathbb Z_3=\{0,1,2\} \end{eqnarray*}$ hat.
Wegen $\begin{eqnarray*} x^2+2x-2x-2=x^2-2\equiv x^2+1 \; (mod\;3) \end{eqnarray*}$ ist auch die erste Lösung richtig, und man spart sich hier die Multiplikation zweier quadratischer Plynome.
Von $\begin{eqnarray*} x^2+2x \end{eqnarray*}$ kommt man auch ganz schnell zur Standardlösung indem man 1 addiert und subtrahiert : $\begin{eqnarray*} x^2+2x=x^2+1-1+2x\equiv 2x-1 \; (mod(x^2+1)) \equiv 2x+2 \; (mod\; 3) \end{eqnarray*}$

18.10.2015, 15:21

icetea01

Auf diesen Beitrag antworten »

Danke @Elvis!

Hätte da noch eine weitere Frage: wie kann ich das inverse Element zu $\begin{eqnarray*} 1+x^{2} \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb Z_{3}/(1+x^{2}) \end{eqnarray*}$ bestimmen? Was wäre da ein möglicher Lösungsweg? Hab bisher keine Idee wie ich da vorgehen muss. verwirrt

Danke schon mal im Voraus!

18.10.2015, 15:44

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von icetea01
Danke @Elvis!

Hätte da noch eine weitere Frage: wie kann ich das inverse Element zu $\begin{eqnarray*} 1+x^{2} \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb Z_{3}/(1+x^{2}) \end{eqnarray*}$ bestimmen?

Inverses Element der Addition oder der Multiplikation? Ich erinnere mal beiläufig daran, dass in diesem Körper $\begin{align*} 1+x^2 = 0 \end{align*}$ gilt...

18.10.2015, 16:26

icetea01

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Inverses Element der Addition oder der Multiplikation? Ich erinnere mal beiläufig daran, dass in diesem Körper $\begin{align*} 1+x^2 = 0 \end{align*}$ gilt...

Multiplikation.

Das inverse Element müsste ja die Form $\begin{eqnarray*} a_{0}+a_{1}x \end{eqnarray*}$ haben, durch Ausprobieren könnte mann auf die Lösung kommen??? Dein Hinweis hilft mir im Moment nicht viel... verwirrt

18.10.2015, 16:27

icetea01

Auf diesen Beitrag antworten »

Edit, sry...

18.10.2015, 16:30

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von icetea01
Dein Hinweis hilft mir im Moment nicht viel... verwirrt

Traurig. Wie lautet denn das multiplikative Inverse der 0 (d.h. des neutralen Elements der Addition) in einem Körper?

18.10.2015, 18:47

Elvis

Auf diesen Beitrag antworten »

Ein Körper $\begin{eqnarray*} (K,+,\cdot) \end{eqnarray*}$ ist eine abelsche Gruppe $\begin{eqnarray*} (K,+) \end{eqnarray*}$ , eine abelsche Gruppe $\begin{eqnarray*} (K\backslash \{0\},\cdot) \end{eqnarray*}$ , und es gelten die Distributivgesetze.

Daraus folgt: IN EINEM KÖRPER KANN MAN NIEMALS DURCH 0 DIVIDIEREN !!! Lehrer