Euklidischen Algorithmus < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:01 Mo 31.05.2010 | | Autor: | su92 |
| Aufgabe | | die Bestimmung des multiplikativen Inversen |
Hallo,
also die Aufgabe ist die Bestimmung des multiplikativen Inversen.
Ich glaube um die multiplikativen Inverse zu lösen muss ich doch erst mit der Euklidischen Algorithmus überprüfen ob "a" und "Z" Teilfremd voneinander sind oder ??
Also Gegeben sind:
1.Zwei Primärzahlen:
p=17, q=19,
2.Daraus m=323 ; den öffentlichen Schlüssel ausrechnen
p * q = m ; m =323
3.Hilfszahl Z=288; ausrechnen
Z = (p-1)(q-1) ; Z = 288
4.Zu Z bildet man eine Teilfremdezahl a; wobei a der erste Schlüssel ist.
a=5
4.1. Ob „a“ und „Z“ teilfremd voneinander sind lässt sich durch den Euklidischen Algorithmus überprüfen:
DAZU HABE ICH EINE FRAGE:
Mit welchen WERTE ich die Euklidischen Algorithmus überprüfe??
--> Ich glaube ich muss mit "a" und "Z" überprüfen, oder???
Habe die Aufgabe auch so weitergerechnet:
Prüfung mit „a“ und „Z“:
ggT ( 288, 5); 288 mod 5 = 3
ggT ( 5, 3) ; 5 mod 3 = 2
ggT ( 3, 2) ; 3 mod 2 = 1
ggT ( 2, 1) ; 2 mod 1 = 0
Somit:
Der größte gemeinsame Teiler von a =5 und Z = 288 ist demnach die 1 .
So,jetzt muss ich die Multikative Inverse ausrechnen, aber die Frage ist wie???
Also ich weiß das ich, irgendwie alles rückwärts ausrechnen muss:
dementsprechend habe ich versucht eine Rechnung fort zu setzten..:
Nun rechne ich die multikative Inverse:
3 = 288 - [...];
2 = 5 - 3 ; 1 = 3 – ( 5- 3) = 1
1 = 3 - 2 ; 1 = 3 - 2
So nun weiß ich nicht ob ÜBERHAUPT mein Ansatz bzw. meine Ansätzte richtig sind???
Außerdem hätte ich nebenbei die Frage: Ob die multikative Inverse gleich der privaten Schlüssel b ist???
Ich hoffe dass ihr mir weiter Helfen könnt =)
Würde mich auf nette und hilfreiche Antworte sehr freuen.
Schöne Grüße
Su
|
|
| |
|
Hallo su92,
lies doch erstmal etwas über den ![[]](/images/popup.gif) erweiterten euklischen Algorithmus.
Danach sollten sich Deine Fragen erledigt haben.
Wenn Du doch noch welche hast, dann rechne mal vor, wie Du das anwendest.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:24 Di 01.06.2010 | | Autor: | su92 |
Hi,
danke der Link hat mir einiger maßen geholfen.
Im Anhang ist eine Berechnung der Multiplikativen Inverse.
Auf der rechten Spalte (von oben nach unten) Zeile 10:
1= 13 - 4 * (16 - 13) = 5 * 13 - 4 * 16
Die Zahl 5 : Wie kommt man auf die Zahl 5 ??
Und was ist die "Multiplikative Inverse" ??
[Dateianhang nicht öffentlich]
Bedanke mich im voraus.
Lg Su92
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
Hallo Su92,
ok, das hast Du Dir offenbar gut erarbeitet, jedenfalls hast du das Prinzip richtig angewandt!
> Hi,
> danke der Link hat mir einiger maßen geholfen.
> Im Anhang ist eine Berechnung der Multiplikativen
> Inverse.
Es heißt "das Inverse", also: eine Berechnung des multiplikativen Inversen. Ein Element und sein multiplikativ Inverses ergeben miteinander multipliziert das Einselement (die Einheit).
> Auf der rechten Spalte (von oben nach unten) Zeile 10:
> 1= 13 - 4 * (16 - 13) = 5 * 13 - 4 * 16
>
> Die Zahl 5 : Wie kommt man auf die Zahl 5 ??
Na, durch Umformen:
[mm] 1=\blue{13}-4*(16-\blue{13})=\blue{13}-4*16+4*\blue{13}=1*\blue{13}+4*\blue{13}-4*16=(1+4)*\blue{13}-4*16=\red{5}*\blue{13}-4*16
[/mm]
> Und was ist die "Multiplikative Inverse" ??
Siehe oben.
> Bedanke mich im voraus.
> Lg Su92
Na dann: gern geschehen.
Grüße
reverend
|
|
|
|
