Modulare Inverse Berechnen

01.04.2009, 15:24	dabudai	Auf diesen Beitrag antworten »
Modulare Inverse Berechnen Hallo alle miteinander, ich soll von 5 modulo 28 die Inverse berechnen. Dabei komme ich nicht ganz weiter: Hier mein Anfang: 1. Euklidischer Algorythmus $\begin{eqnarray} <br /> 28 = (55)+3<br /> 5=(13)+2<br /> 3=(12)+1<br /> 2=(21)+0<br /> --> ggt= 1<br /> \end{eqnarray}$ 2. Rückweg aufstellen: $\begin{eqnarray} <br /> 1=3-(12)<br /> 2=5-(13)<br /> 3=28-(55)<br /> \end{eqnarray}$ 3. Modulare Inverse vorbereiten $\begin{eqnarray} <br /> 1=3-(12)<br /> 1=3-(1(5-(13)))<br /> 1=3-(1(5-(1(28-(55)))))<br /> .........<br /> \end{eqnarray*}$ 4. Modulare Inverse berechnen ......
01.04.2009, 23:51	Cordovan	Auf diesen Beitrag antworten »
Verwende den erweiterten euklidischen Algorithmus, um eine Darstellung der Form $\begin{eqnarray} a\cdot 5+b\cdot 28=\operatorname{ggT}(5,28)=1 \end{eqnarray}$ mit $\begin{eqnarray} a,b\in\mathbb Z \end{eqnarray}$ zu bestimmen. Dann gilt $\begin{eqnarray} a\cdot 5\equiv 1\mod 28 \end{eqnarray}$ , also ist $\begin{eqnarray} 5^{-1}\equiv a\mod 28 \end{eqnarray}$ . Versuch also, mit deinen bisherigen Rechnungen so eine Darstellung zu finden. Cordovan

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »