Modulare Inverse im Polynomring

09.09.2022, 11:31	_Bastii	Auf diesen Beitrag antworten »
Modulare Inverse im Polynomring Guten Morgen, ich möchte das modulare Inverse von $\begin{eqnarray} f(x) = x^4 + x^3 + 1 \end{eqnarray}$ im Polynomring $\begin{eqnarray} Z_2[x]_{\Pi} \end{eqnarray}$ , mit $\begin{eqnarray} \Pi(x) = x^5 + x^2 + 1 \end{eqnarray}$ , berechnen. Zuerst soll ich dafür den ggT von $\begin{eqnarray} f(x) \end{eqnarray}$ und $\begin{eqnarray} \Pi(x) \end{eqnarray}$ berechnen. Meine Idee war, den ggT und gleichzeitig das modulare Inverse mit dem erweiterten euklidischen Algorithmus zu berechnen. $\begin{eqnarray} \begin{array}{c\|c\|c\|c\|c} i & g & s & u & v \\<br /> \hline<br /> 0 & x^5 + x^2 + 1 & - & 1 & 0 \\<br /> 1 & x^4 + x^3 + 1 & s_1 & 0 & 1 \\<br /> 2 & g_2 & s_2 & u_2 & v_2<br /> \end{array} \end{eqnarray}$ NR: $\begin{eqnarray} (x^5 + x^2 + 1) : (x^4 + x^3 + 1) = x+1 \end{eqnarray}$ , Rest: $\begin{eqnarray} x^3+x^2+x \end{eqnarray}$ $\begin{eqnarray} u_2 = 1 - 0 \cdot (x+1) = 1 \end{eqnarray}$ $\begin{eqnarray} v_2 = 0 - 1 \cdot (x+1) = x+1 \end{eqnarray}$ $\begin{eqnarray} \begin{array}{c\|c\|c\|c\|c} i & g & s & u & v \\<br /> \hline<br /> 0 & x^5 + x^2 + 1 & - & 1 & 0 \\<br /> 1 & x^4 + x^3 + 1 & x+1 & 0 & 1 \\<br /> 2 & x^3+x^2+x & s_2 & 1 & x+1 \\<br /> 3 & g_3 & s_3 & u_3 & v_3<br /> \end{array} \end{eqnarray}$ NR: $\begin{eqnarray} (x^4+x^3+1) : (x^3+x^2+x) = x \end{eqnarray}$ , Rest: $\begin{eqnarray} x^2+1 \end{eqnarray}$ $\begin{eqnarray} u_3 = 0 - 1 \cdot x = x \end{eqnarray}$ $\begin{eqnarray} v_3 = 1 - (x+1) \cdot x = x^2+x \end{eqnarray}$ $\begin{eqnarray} \begin{array}{c\|c\|c\|c\|c} i & g & s & u & v \\<br /> \hline<br /> 0 & x^5 + x^2 + 1 & - & 1 & 0 \\<br /> 1 & x^4 + x^3 + 1 & x+1 & 0 & 1 \\<br /> 2 & x^3+x^2+x & x & 1 & x+1 \\<br /> 3 & x^2+1 & s_3 & x & x^2+x \\<br /> 4 & g_4 & s_4 & u_4 & v_4<br /> \end{array} \end{eqnarray}$ NR: $\begin{eqnarray} (x^3+x^2+x)<img src="images2/smilies/frown2.gif" border="0" alt="unglücklich" title="unglücklich" /> x^2+1)=x+1 \end{eqnarray}$ , Rest: $\begin{eqnarray} 1 \end{eqnarray}$ $\begin{eqnarray} u_4 = 1 - x \cdot (x+1) = x^2+x \end{eqnarray}$ $\begin{eqnarray} v_4 = (x+1) - (x^2+x) \cdot (x+1) = x^3+1 \end{eqnarray}$ $\begin{eqnarray} \begin{array}{c\|c\|c\|c\|c} i & g & s & u & v \\<br /> \hline<br /> 0 & x^5 + x^2 + 1 & - & 1 & 0 \\<br /> 1 & x^4 + x^3 + 1 & x+1 & 0 & 1 \\<br /> 2 & x^3+x^2+x & x & 1 & x+1 \\<br /> 3 & x^2+1 & x+1 & x & x^2+x \\<br /> 4 & 1 & s_4 & x^2+x & x^3+1 \\<br /> 5 & g_5 & s_5 & u_5 & v_5<br /> \end{array} \end{eqnarray}$ $\begin{eqnarray} (x^2+1):1=x^2+1 \end{eqnarray}$ , Rest: $\begin{eqnarray} 0 \end{eqnarray}$ $\begin{eqnarray} \begin{array}{c\|c\|c\|c\|c} i & g & s & u & v \\<br /> \hline<br /> 0 & x^5 + x^2 + 1 & - & 1 & 0 \\<br /> 1 & x^4 + x^3 + 1 & x+1 & 0 & 1 \\<br /> 2 & x^3+x^2+x & x & 1 & x+1 \\<br /> 3 & x^2+1 & x+1 & x & x^2+x \\<br /> 4 & 1 & x^2+1 & x^2+x & x^3+1 \\<br /> 5 & 0 & - & - & -<br /> \end{array} \end{eqnarray}$ $\begin{eqnarray} \implies ggT(x^5 + x^2 + 1, x^4 + x^3 + 1) = 1 \end{eqnarray}$ $\begin{eqnarray} \implies f(x)^{-1} = (x^4 + x^3 + 1)^{-1} = u_4 = x^2+x \end{eqnarray}$ Ist das soweit richtig? Es müsste als Probe anschließend ja gelten: $\begin{eqnarray} f(x)^{-1} \cdot f(x) \equiv_{x^5+x^2+1} 1 \end{eqnarray}$ Wenn ich das jedoch berechne, erhalte ich als Rest nicht 1: $\begin{eqnarray} f(x)^{-1} \cdot f(x) = x^4+x^3+1 \cdot x^2+x = x^6 + x^4 + x^2 + x \end{eqnarray}$ $\begin{eqnarray} (x^6 + x^4 + x^2 + x) : (x^5+x^2+1) = x \end{eqnarray}$ , Rest: $\begin{eqnarray} x^4+x^3+x^2 \end{eqnarray}$ Habe ich also einen Fehler gemacht?
09.09.2022, 20:47	jester.	Auf diesen Beitrag antworten »
Ja, du hast dich verrechnet. Was auch immer du da tust, es ist wirklich wahnsinnig unübersichtlich. Ich werde das nicht nachrechnen. Du brauchst nur diese drei Gleichungen aus dem Euklidischen Algorithmus: $\begin{eqnarray} &\Pi &= (x+1)f &+ &x^3 +x^2+x \\ &f &= x(x^3+x^2+x) &+ &x^2+1 \\ &x^3+x^2+x &= (x+1)(x^2+1) &+ &1 \end{eqnarray}$ Das kannst du dann rückwärts auflösen zu $\begin{eqnarray} 1 = ... = (x^3+x)f ~+~ (x^2+x+1)\Pi \end{eqnarray}$ , dementsprechend ist $\begin{eqnarray} f^{-1} \end{eqnarray}$ die Restklasse von $\begin{eqnarray} x^3+x \end{eqnarray}$ . PS: Ich wusste bisher nicht, dass die Unsitte mit der Schreibweise $\begin{eqnarray} \mathbb{Z}_2 \end{eqnarray}$ für den Restklassenring sich noch durch $\begin{eqnarray} \mathbb{Z}_2[x]_\Pi \end{eqnarray}$ überbieten lässt Soll aber nicht dein Problem sein.
10.09.2022, 13:43	_Bastii	Auf diesen Beitrag antworten »
Schade aber das verstehe ich. Trotzdem kurz zur Erklärung warum es so unübersichtlich ist. Ich wollte gerne die Tabelle Schritt-für-Schritt "befüllen", weshalb ich immer eine neue Tabelle hinzugefügt habe. Die Gleichungen verstehe ich nicht wirklich. Woher kommen die? Grundsätzlich müsste es aber mit dem erweiterten euklidischen Algorithmus gehen und das letzte $\begin{eqnarray} u_i \end{eqnarray}$ müsste dann doch die Inverse sein, oder? Ich rechne es nochmal nach.
10.09.2022, 14:32	_Bastii	Auf diesen Beitrag antworten »
Ich habe es jetzt nachgerechnet und den Fehler gefunden. Außerdem habe ich mich scheinbar in der Spalte vertan. Jetzt sieht die vollständige Tabelle so aus: $\begin{eqnarray} \begin{array}{c\|c\|c\|c\|c} i & g & s & u & v \\<br /> \hline<br /> 0 & x^5 + x^2 + 1 & - & 1 & 0 \\<br /> \hline<br /> 1 & x^4 + x^3 + 1 & x+1 & 0 & 1 \\<br /> \hline<br /> 2 & x^3+x^2+x & x & 1 & x+1 \\<br /> \hline<br /> 3 & x^2+1 & x+1 & x & x^2+x+1 \\<br /> \hline<br /> 4 & 1 & x^2+1 & x^2+x+1 & x^3+x \\<br /> \hline<br /> 5 & 0 & - & - & -\\<br /> \end{array} \end{eqnarray}$ Und daraus folgt: $\begin{eqnarray} \Rightarrow (x^5+x^2+1) \cdot (x^2+x+1)+(x^4+x^3+1) \cdot (x^3 +x) = \;...\;= 1 \end{eqnarray}$ $\begin{eqnarray} \Rightarrow f^{-1} = x^3+x \end{eqnarray}$ Probe: $\begin{eqnarray} f \cdot f^{-1} = (x^4+x^3+1) \cdot (x^3+x) = \; ... \; = x^7 + x^6 + x^5 + x^4 + x^3 + x \end{eqnarray}$ $\begin{eqnarray} (x^7 + x^6 + x^5 + x^4 + x^3 + x) \bmod (x^5+x^2+1) = 1 \end{eqnarray}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »