Hi,
im Zuge meiner Klausurvorbereitung möchte ich euch hier den Erweiterten Euklidischen Algorithmus (EEA) kurz vorstellen. Bitte habt Gnade mit mir, ich bin auch nur ein Boon. Solltet ihr einen Fehler finden, einfach sofort bescheid geben. 
##################################################
Thema: Erweiterter Euklidischer Algorithmus
Autor: soulstoned
Published: Free-Hack.com
Quelle(n):
##################################################
Der EEA berechnet für die gegeben Werte
den größten gemeinsamen Teiler:

Wozu braucht man das alles? Man braucht den EEA zum Beispiel, wenn man in der Kryptografie bei einer Affinen Chiffre die modulare Inverse
berechnen muss.
Die Grundidee sagt aus, dass man in jeder Iteration des normalen Euklidischen Algorithmus
berechnet:
mit
letzte Iteration


Es folgt:
Euklidischer Algorithmus | Erweiterter Euklidischer Algorithmus
|
wobei
und 
| 
| 
und so weiter, bis gilt:
| 

wobei die
anzeigt, dass der Algorithmus fertig ist und aus dem Schritt zuvor
entspricht.
Für die Praxis gibt es folgende Iterationsformeln:
als Startwert und


Für die Informatiker unter euch kann folgender Pseudo-Code genommen werden:
Oder als Java-Source-Code:
Code:
public int[] extEuclid(int a, int b) {
if (b == 0) {
int result[] = {1, 0, a};
return result;
}
int u = a;
int v = b;
int x1, x2, x3, y1, y2, y3;
if (u < v) {
x1 = 0; x2 = 1; x3 = v;
y1 = 1; y2 = 0; y3 = u;
} else {
x1 = 1; x2 = 0; x3 = u;
y1 = 0; y2 = 1; y3 = v;
}
while (y3 > 1) {
int q = (int) (x3/y3);
int t1 = x1 - q*y1;
int t2 = x2 - q*y2;
int t3 = x3 - q*y3;
x1 = y1; x2 = y2; x3 = y3;
y1 = t1; y2 = t2; y3 = t3;
}
if (y3 == 0) {
int result[] = {x1, x2, x3};
return result;
} else {
int result[] = {y1, y2, y3};
return result;
}
}
Anwendung findet das ganze zum Beispiel in RSA:
gegeben:
mit 
gesucht: 





Also: Der Wert
des EEA ist die Inverse von 
Eine Beispielrechnung:
gegeben: 
Euklidischer Algorithmus | Erweiterter Euklidischer Algorithmus
| 
| 
| 
| 
| 

Das wars dann soweit, hoffe es war einigermaßen verständlich. 
Gruß