Moin,
wie berechnet man denn Modulokongruenz?
ab = 1 mod n
nur b und n sind bekannt, wie krieg ich jetzt a???
Ich weiss jetzt nicht, wie das in der Vorlesung gemacht wird,
aber man kann das mit den euklidischen Algorithmus machen:
Notwendige Voraussetzung ist ja, dass b,n teilerfremd sind,
d.h. den ggT 1 haben. Daher genügt ein Algorithmus, der
den ggT 1 von b und n darstellt als 1=ab+yn. Denn betrachtet
man diese Gleichung modulo n, so ergibt sich 1=ab mod n.
Und das macht der euklidische Algorithmus: er findet eine
Darstellung des ggT d von m,n als Linearkombination
d=xm+yn. In Scheme sieht das dann etwa so aus:
; Findet eine Darstellung d=xm+yn,
; wobei d der ggT von m und n ist.
; Gibt Liste (x y) zurück.
; Vorbedingung: m >= n >= 0.
(define (ggTdarst m n)
(if (or (= n 0) (= m n)) (list 1 0)
(let* (
; Finde f,r mit m=fn+r und r<n
(r (modulo m n))
(f (quotient m n))
; n,r haben denselben ggT wie m,n und r<n
; Finde also rekursiv Darstellung d=sn+tr
(l (ggTdarst n r))
(s (car l))
(t (cadr l)))
; Wegen r=m-fn gilt
; d=sn+tr=sn+t(m-fn)
; =tm + (s-tf)n
; Darstellung fuer d ist gefunden
(list t (- s (* t f))))))
Dabei können negative Zahlen rauskommen, aber dann addiert
man einfach ein Vielfaches von n zu a, das ändert nichts
an der Gültigkeit von 1=ab mod n.
Ist schon ziemlich spaet, aber vielleicht hilft es dir ja noch:
Bei so kleinen Zahlen, wie sie in dem GBI-Beispiel verwendet werden, kannst du die Gleichung auch durch Ausprobieren loesen.. immerhin sollen wir die Aufgabe ja "per Hand" loesen, also keine Computer verwenden.
es soll gelten:
e * d = 1 mod ((p -1) * (q -1))
in der aufgabe also
29 * d = 1 mod 396
das heisst ja nix anderes als
29 * d = 1 + x * 396
( x muss ganzzahlig sein, d ja sowieso )
Du bekommst also eine sogenannte diophantische Gleichung (kannte ich vorher auch nicht):
396 * x - 29 * d + 1 = 0
Fuer x = 0, 1 und 2 gibt es keine ganzzahllige Loesung fuer d. Setzt du x = 3 ergibt sich d = 41.
Ist vielleicht nicht so mathematisch wie euklidischer Algorithmus, aber man kann es mit nem billigen Taschenrechner berechnen.
