Inverse Element zu Divisionsresten

Neue Frage »

08.10.2011, 12:06	HeikoB	Auf diesen Beitrag antworten »
Inverse Element zu Divisionsresten Meine Frage: Wie findet man das Inverse z.B. zu x^{7} + x + 1, welches sich bei einer Division eines Polynoms aus $\begin{eqnarray} \mathbb Z_{n} \end{eqnarray}$ [x] durch das Polynom f = x^{8} + x^{4} + x^{3} + x + 1 ergibt? Meine Ideen: Bräuchte eine allgemeine Anleitung, wie man bei solchen Problemen vorgeht. Danke
08.10.2011, 12:34	galoisseinbruder	Auf diesen Beitrag antworten »
Meinst Du folgendes: Das Inverse zu $\begin{eqnarray} x^7+x+1 \end{eqnarray}$ in $\begin{eqnarray} R[X]/(f) \end{eqnarray}$ mit $\begin{eqnarray} R:=\mathbb{Z}/n \mathbb{Z} \end{eqnarray}$ .
08.10.2011, 12:44	HeikoB	Auf diesen Beitrag antworten »
ich meinte $\begin{eqnarray} R:=\mathbb{Z}/2 \mathbb{Z} \end{eqnarray}$ .
08.10.2011, 12:48	galoisseinbruder	Auf diesen Beitrag antworten »
O.K. n ist 2. Aber meinst Du das was ich geschrieben hab´oder was anderes. Denn was Du im ersten Post geschrieben hast ergibt nicht wirklich viel Sinn(zumindest für mich).
08.10.2011, 13:52	HeikoB	Auf diesen Beitrag antworten »
$\begin{eqnarray} [x^{7} + x + 1]_{f}[s]_{f} = [1]_{f} \end{eqnarray*}$ ist die Definition des inversen Elements das ich suche. Weis aber nicht wie man an sowas ran geht
08.10.2011, 13:57	galoisseinbruder	Auf diesen Beitrag antworten »
Da wir uns jetzt einig sind worüber wir reden: Kennst Du den erweiterten euklidischen Algorithmus?
Anzeige

08.10.2011, 14:39	HeikoB	Auf diesen Beitrag antworten »
ja den ggT für Polynome beherrsche ich mittlerweile, habe mir schon gedacht dass es irgendetwas damit zu tun hat, bekomme aber nachdem $\begin{eqnarray} [x^{7} + x + 1]_{f}[s]_{f} = [1]_{f} \end{eqnarray}$ ausgerechnet habe und die Probe mache mit $\begin{eqnarray} [x^{7} + x + 1]_{f}[s]_{f} \end{eqnarray}$ durch f teilen kein korrektes Ergebnis raus Probiere nochmal den Algorithmus und poste mal meine Ergebnisse
08.10.2011, 14:41	galoisseinbruder	Auf diesen Beitrag antworten »
Was hast Du denn konkret gerechnet?
08.10.2011, 14:45	HeikoB	Auf diesen Beitrag antworten »
ich mache den erweiterten ggT mit polynomen und erhalte dann eine Linearkombination: 1 = rf + k $\begin{eqnarray} [x^{7} + x + 1] \end{eqnarray}$
08.10.2011, 14:49	galoisseinbruder	Auf diesen Beitrag antworten »
Und damit ist das gesuchte s?
08.10.2011, 14:54	HeikoB	Auf diesen Beitrag antworten »
Was hast du gemeint, wie soll ich den erweiterten ggT dann anwenden oder was erhalte ich, wenn ich den erweiterten ggT durchführe?
08.10.2011, 14:57	galoisseinbruder	Auf diesen Beitrag antworten »
Ausführlich: Erweiterter Euklid liefert: $\begin{eqnarray} 1=r\cdot f+k \cdot (X^7+X+1) \end{eqnarray}$ Als Gleichung in $\begin{eqnarray} R[X]/(f) \end{eqnarray}$ gelesen ergibt das welche Gleichung?
08.10.2011, 14:59	HeikoB	Auf diesen Beitrag antworten »
oder kannst du mal schreiben wie der ansatz dann aussieht
08.10.2011, 15:04	galoisseinbruder	Auf diesen Beitrag antworten »
Ich dachte soweit wären wir schon gewesen: Wir suchen doch ein $\begin{eqnarray} s \in R[X]/(f) \end{eqnarray}$ mit $\begin{eqnarray} R:=\mathbb{Z}/2 \mathbb{Z} \end{eqnarray}$ mit der Eigenschaft $\begin{eqnarray} s \cdot (X^7+X+1)\equiv 1 \mod f \end{eqnarray}$ Anders ausgedrückt: $\begin{eqnarray} s \cdot (X^7+X+1)= 1 +g \cdot f \end{eqnarray}$ für ein Polynom g. Sind wir uns soweit einig?
08.10.2011, 15:08	HeikoB	Auf diesen Beitrag antworten »
wollte ich auch grad schreiben. soweit ja
08.10.2011, 15:24	HeikoB	Auf diesen Beitrag antworten »
$\begin{eqnarray} 1\equiv [x^{5} + x^{3}][x^{7} + x + 1] \end{eqnarray*}$ mod(f) hab ich jetzt als lösung raus
08.10.2011, 15:25	galoisseinbruder	Auf diesen Beitrag antworten »
Du hast folgendes ausgerechnet: $\begin{eqnarray} 1=r\cdot f+k \cdot (X^7+X+1) \end{eqnarray}$ In welchem Zusammenhang mit dem hier $\begin{eqnarray} s \cdot (X^7+X+1)= 1 +g \cdot f \end{eqnarray}$ steht das?
08.10.2011, 15:27	HeikoB	Auf diesen Beitrag antworten »
statt k:= s
08.10.2011, 15:32	galoisseinbruder	Auf diesen Beitrag antworten »
Ja genau, das k das Du mittels erweitertem Euklid ausgrechnet hast ist das Inverse von f.
08.10.2011, 15:45	HeikoB	Auf diesen Beitrag antworten »
ich glaube $\begin{eqnarray} x^{7} \end{eqnarray}$ ist die richtige Lösung bei der Probe kam Rest 1 raus, dann müsste es doch stimmen oder?
08.10.2011, 15:59	HeikoB	Auf diesen Beitrag antworten »
Danke für die Unterstützung
08.10.2011, 16:07	galoisseinbruder	Auf diesen Beitrag antworten »
Sry für diee späte Meldung, hab´ etwas gebraucht zu rechnen. Krieg auch $\begin{eqnarray} X^7 \end{eqnarray}$ raus.

Neue Frage »

Antworten »

Inverse Element zu Divisionsresten

Verwandte Themen