Erweiterteter Euklidscher Algorithmus

02.02.2011, 17:18	Henne	Auf diesen Beitrag antworten »
Erweiterteter Euklidscher Algorithmus Meine Frage: Hallo, ich bekomme die Umformung zu der Vielfachsummendarstellung nicht hin. Wäre schön wenn mir das einer zeigen könnte bzw. an meinem Beispiel zeigen kann, brauche das für eine Facharbeit und sitze den ganzen Nachmittag schon dran -.-' Geht übrigends um die RSA Verschlüsselung Meine Ideen: Aus den Primzahlen 7 und 11 habe ich Phi(qp)=60=a gebildet und b=13 a=q_1b+r_1 60=413+8 13=18+5 8=15+3 5=13+2 3=1*2+1
03.02.2011, 11:14	Mystic	Auf diesen Beitrag antworten »
RE: Erweiterteter Euklidscher Algorithmus Ich nehme mal an, e=13 ist der öffentliche Schlüssel für RSA und du möchtest das y berechnen, sodass $\begin{eqnarray} 60x+13y=1 \end{eqnarray}$ gilt... Dazu muss du einfach dein Divisionschema noch einmal wiederholen, aber mit $\begin{eqnarray} y_0=0, y_1=1 \end{eqnarray}$ an Stelle von a=30 und b=13 und unter Verwendung der gleichen (!) Quotienten wie vorher für a und b... Dies ergibt dann die weiteren Glieder der Folge $\begin{eqnarray} y_2=-4,y_3=5,y_4=-9,y_5=14,y_6=-23 \end{eqnarray}$ genau an der Stelle wo früher die Reste standen und das letzte Folgenglied ist das gewünschte y...Am besten, ich führe dir das an deinem Beispiel einfach vor: $\begin{eqnarray} \begin{array}{rlcc}0 &= 41&+&(-4)\\ 1 &= 1(-4)&+&5\\ -4 &=15&+&(-9)\\ 5&=1(-9)&+&14\\ -9&=114&+&(-23)\end{array} \end{eqnarray}$ $\begin{eqnarray} y=-23 \equiv 37 \mod 60 \end{eqnarray}$ ist somit das gewünschte Inverse zu 13 mod 60... Es wird vermutlich nichts nützen, aber ich möchte auch an dieser Stelle darauf hinweisen, dass man ganz allgemein im RSA statt $\begin{eqnarray} \varphi(n)=(p-1)(q-1)=610=60 \end{eqnarray}$ besser $\begin{eqnarray} \lambda(n)=kgV(p-1,q-1)=kgV(6,10)=30 \end{eqnarray}$ verwenden sollte, d.h., der "richtige" (im Sinne von optimale) private Schlüssel wäre hier eigentlich $\begin{eqnarray} d=7 \end{eqnarray}$ (wegen $\begin{eqnarray} d \equiv 37 \mod 30 \end{eqnarray*}$ )...
16.02.2011, 13:32	Henne92	Auf diesen Beitrag antworten »
danke, also das Ergebnis hat mir schon viel geholfen aber so ganz blick ich da immer noch nicht durch^^
16.02.2011, 17:36	Mystic	Auf diesen Beitrag antworten »
RE: Erweiterteter Euklidscher Algorithmus Zum Verständnis des Ganzen solltest in dein Divisionschema für alle Reste $\begin{eqnarray} r_i \neq 0, i=0,1,2,... \end{eqnarray}$ Darstellungen der Form $\begin{eqnarray} r_i=x_ia+y_ib, \quad x_i,y_i \in \mathbb Z \end{eqnarray}$ einsetzen... Für $\begin{eqnarray} r_0:=a=1\cdot a+0\cdot b,\quad r_1:=b=0\cdot a+1\cdot b \end{eqnarray}$ gibt es solche Darstellungen sicher, für die anderen Reste ergeben sie sich dann induktiv...Du musst dann dieses eine Divisionsschema in zwei Schemata "auftrennen", eines für die $\begin{eqnarray} x_i \end{eqnarray}$ und eines für die $\begin{eqnarray} y_i \end{eqnarray}$ ... Jenes für die $\begin{eqnarray} y_i \end{eqnarray}$ (aber bereits mit eingesetzten Werten, wie sie sich sukzessiv der Reihe nach ergeben) habe ich dir oben hingeschrieben... Kannst du damit etwas anfangen? Wenn nein, was ist konkret unklar?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »