| Autor |
Beitrag |
    
needhelp
| | Veröffentlicht am Samstag, den 24. März, 2001 - 21:58: | 
|
Hallo,
ich suche eine Möglichkeit das inverse Element von x in Zm zu ermitteln.
Irgendwie soll es mit dem euklideschen Alg. funtionieren.
Durch rueckwärts einsetzen oder so ?
Weiß jemand näheres ? |
Hans (Birdsong)
| | Veröffentlicht am Sonntag, den 25. März, 2001 - 15:04: |
|
Hallo :
Das gegebene Element heisse a. Gesucht ist x so,
dass
(1) a*x kongruent 1 (mod m)
oder also
(2) a*x = 1 + k*m <==> a*x + (-k)*m = 1
mit k in Z. (2) besagt: a ist invertierbar g.d.w.
a und m teilerfremd sind, d.h. GgT(a,m) = 1 ist.
Die Loesung von (1) bzw.(2) laeuft darauf heraus,
den GgT von a und m in der Form
(3) GgT(a,m) = a*x + m*y mit x,y in Z
darzustellen. Der Hauptsatz Ÿber den GgT besagt
gerade, dass das stets moeglich ist. Konstruktiv
zeigt man das mit Hilfe des erweiterten Euklidischen Algorithmus. Dazu berechnet man
rekursiv die Folgen (a_n), (q_n), (x_n), (y_n)
mit den Startwerten ([ ] := Ganzteilfunktion)
(4) a_0 := a , a_1 := m , q_1 := [a/m] ,
(5) x_0 := 1 , y_0 := 0 , x_1 := 0 , y_1 := 1
und gemaess den Rekursionsformeln
(6) q_n = [a_(n-1)/a_n] , a_n = a_(n-2) - q_n*a_n
(7) x_(n+1) = x_(n-1) - q_n*x_n
(8) y_(n+1) = y_(n-1) - q_n*y_n.
Die Zahlen a_n bilden eine streng monoton fallende
Folge, daher sind von einem Index N+1 ab alle a_n
= 0. Die Zahl a_N , d.h. der letzte nicht verschwindende Rest in der Kette (6) der "Divisionen mit Rest" ist dann der gesuchte GgT,
und die Zahlen x_N =:x , y_N =:y sind die
gesuchten Koeffizienten in der Darstellung (3).
Falls GgT(a,m) = 1, so lautet (3) also
(9) a*x + m*y = 1 ==> a*x kongruent 1 (mod m),
und die Restklasse von x ist die gesuchte
Inverse der Restklasse von a (mod m).
Am besten legst Du dir ein Rechenschema mit den
SpaltenŸberschriften n , a_n , q_n , x_n , y_n
an, traegst in den Zeilen 0 und 1 die Startwerte
(4) , (5) ein und rechnest weiter gemaess den
Formeln (6) - (8). Tritt das letzte nicht
verschwindende a_n in der Zeile Nr. N auf, so
liest man in dieser Zeile das Resultat ab.
Viel Spass
Hans |
|
