Erweiterter Euklidischer Algorithmus (EEA)
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. ;)
##################################################
Zitat:
Thema: Erweiterter Euklidischer Algorithmus
Autor: soulstoned
Published: Free-Hack.com
Quelle(n):
##################################################
Der EEA berechnet für die gegeben Werte http://www.imagebanana.com/img/ixz898d1/1.gif den größten gemeinsamen Teiler:
http://www.imagebanana.com/img/lz493415/2.gif
Wozu braucht man das alles? Man braucht den EEA zum Beispiel, wenn man in der Kryptografie bei einer Affinen Chiffre die modulare Inverse http://www.imagebanana.com/img/b5wnfrd7/CodeCogsEqn.gif berechnen muss.
Die Grundidee sagt aus, dass man in jeder Iteration des normalen Euklidischen Algorithmus http://www.imagebanana.com/img/z04z9...deCogsEqn2.gif berechnet:
http://www.imagebanana.com/img/7vy35...deCogsEqn3.gif mit
http://www.imagebanana.com/img/4jxjs9c/CodeCogsEqn4.gif letzte Iteration
http://www.imagebanana.com/img/tvm7mxo/CodeCogsEqn5.gif
http://www.imagebanana.com/img/n0ueh...deCogsEqn6.gif
Es folgt:
Euklidischer Algorithmus | Erweiterter Euklidischer Algorithmus
http://www.imagebanana.com/img/yqr4h...deCogsEqn7.gif | http://www.imagebanana.com/img/hjmyxq9/CodeCogsEqn8.gif wobei http://www.imagebanana.com/img/606fa...deCogsEqn9.gif und http://www.imagebanana.com/img/u0z7a...eCogsEqn10.gif
http://www.imagebanana.com/img/8w605...eCogsEqn11.gif | http://www.imagebanana.com/img/jnnwz...eCogsEqn13.gif
http://www.imagebanana.com/img/0oixt...eCogsEqn14.gif | http://www.imagebanana.com/img/fe7al...eCogsEqn15.gif
und so weiter, bis gilt:
http://www.imagebanana.com/img/n7cyc...eCogsEqn16.gif | http://www.imagebanana.com/img/39vwr...eCogsEqn17.gif
http://www.imagebanana.com/img/815ti...eCogsEqn18.gif
wobei die http://www.imagebanana.com/img/r4bly...eCogsEqn19.gif anzeigt, dass der Algorithmus fertig ist und aus dem Schritt zuvor http://www.imagebanana.com/img/kvkrb...eCogsEqn20.gif entspricht.
Für die Praxis gibt es folgende Iterationsformeln:
http://www.imagebanana.com/img/0zy9t...eCogsEqn21.gif als Startwert und
http://www.imagebanana.com/img/ugrir...eCogsEqn23.gif
http://www.imagebanana.com/img/g42na...eCogsEqn24.gif
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: http://www.imagebanana.com/img/rbogx...eCogsEqn26.gif mit http://www.imagebanana.com/img/m4awi...eCogsEqn27.gif
gesucht: http://www.imagebanana.com/img/fiecc...eCogsEqn28.gif
http://www.imagebanana.com/img/g4fmz...eCogsEqn29.gif
http://www.imagebanana.com/img/7tfuu...eCogsEqn30.gif
http://www.imagebanana.com/img/znx8x...eCogsEqn31.gif
http://www.imagebanana.com/img/xffy1...eCogsEqn32.gif
http://www.imagebanana.com/img/6obbr...eCogsEqn33.gif
Also: Der Wert http://www.imagebanana.com/img/b1l9q...eCogsEqn34.gif des EEA ist die Inverse von http://www.imagebanana.com/img/30vy7...eCogsEqn35.gif
Eine Beispielrechnung:
gegeben: http://www.imagebanana.com/img/t5vwf...eCogsEqn36.gif
Euklidischer Algorithmus | Erweiterter Euklidischer Algorithmus
http://www.imagebanana.com/img/6ndx3...eCogsEqn37.gif | http://www.imagebanana.com/img/nbeh4...eCogsEqn38.gif
http://www.imagebanana.com/img/5g0uv...eCogsEqn39.gif | http://www.imagebanana.com/img/tjdr7...eCogsEqn40.gif
http://www.imagebanana.com/img/a71ao...eCogsEqn41.gif | http://www.imagebanana.com/img/tkfi2...eCogsEqn42.gif
http://www.imagebanana.com/img/o51sx...eCogsEqn48.gif | http://www.imagebanana.com/img/vmj3u1/CodeCogsEqn44.gif
http://www.imagebanana.com/img/dof8r...eCogsEqn45.gif | http://www.imagebanana.com/img/mzfz5...eCogsEqn52.gif
http://www.imagebanana.com/img/ed6vy...eCogsEqn47.gif
Das wars dann soweit, hoffe es war einigermaßen verständlich. ;)
Gruß
