Euklidischer Algorithmus

...komplette Frage anzeigen

1 Antwort

Die Aufgabe besteht ja darin, ein Zahlenpaar e und d zu finden, dessen Produkt kongruent zu 1 mod ((p-1)(q-1)) ist. Dazu wird eine Zahl frei gewählt (e=5) und dann mit dem Euklidischen Algorithmus der ggT aus e und (p-1)(q-1) bestimmt, da muß dann 1 rauskommen, sonst muß man eine andere Zahl für e wählen. Mit dem Erweiterten Euklidischen Algorithmus (siehe http://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus) bekommt man als "Nebenprodukt" noch die beiden Faktoren raus, mit denen man den ggT aus den beiden Ausgangszahlen berechnen kann, hier also d und s.

Was möchtest Du wissen?