Rsa Multiplikatives Inverse?
Hallo! Ich habe ein Problem mit dem M.I. Man versucht ja eine Zahl zu finden für die gilt
a*a^(-1) = 1 mod n
Beispiel:
ggT(8, 11) = 1
8*8^(-1) = 1 mod 11 ----> für 8^(-1) = 7
Das Beispiel ergibt für mich noch Sinn, aber ich verstehe nicht wie:
1 mod n = 1
Ergeben kann so wie es dir Formel beschreibt. Oder ist fiese schlichtweg falsch.
Ich entschuldige mich schonmal für mein brüchigen Satzbau (Schreibe diese Frage auf dem Weg zum Bus)
Ich würde mich über eine erläuternde Antwort freuen :)
1 Antwort
Du verwechselst die Schreibweise der Mathematiker für Kongruenz mit dem Modulo-Operator in Programmiersprachen:
a ≡ b (mod n) (sprich "a kongruent b, modulo n") heißt, dass a und b derselben Restklasse modulo n angehören.
b mod n ist eine zweistellige Funktion, die den ganzzahligen Rest von b/n liefert. In manchen Programmiersprachen schreibt man dafür auch b % n.
Die zweite Variante ist zum Rechnen ganz nett, aber für formale Beweise ist die erste Darstellung wesentlich praktischer. Wenn Du damit nicht klar kommst, kannst Du umformen:
- a ≡ b (mod n) ⇔ a%n = b%n
Das gilt aber nur für a, b≥0 und n>0. Bei negativen Zahlen klappt das nur, wenn der Modulo-Operator einen Wertebereich der Größe n hat. Das ist in vielen Programmiersprachen leider nicht der Fall.
Nein, 8 und 7 liegen natürlich in verschiedenen Restklassen. Deine Kongruenzgleichung sagt nur, dass das Produkt (8·7) in derselben Restklasse wie 1 liegt: 56≡1 (mod 11) – passt!
Wenn ich es richtig interpretiere, kann das Inverse von a durch diese Gleichung definiert werden – klappt aber nur, wenn n prim ist.
Also gehören 8 und 8^-1 bzw. 7 der selben restklasse modulo 11 an ? Oder verstehe ich das falsch.