Dies ist eine alte Version des Dokuments!


Modulo-Inverse

(zu tm.jpg, Restklassen, Kryptographie)

  • Das Einheitselement bezüglich der Multiplikation (mod m) ist 1, denn tex:\forall a \in Z: 1 \cdot a \equiv a \cdot 1 \equiv a (mod m).
  • Die Modulo-Inverse r-1 zu r hat die Eigenschaft tex:r^{-1} \cdot r \equiv r \cdot r^{-1} \equiv 1 (mod m).

Rechenbeispiele:

  • Die Modulo-Inverse von 3 (mod 5) ist 2, denn tex:2 \cdot 3 \equiv 1 (mod 5)
  • Die Modulo-Inverse von 5 (mod 7) ist 3, denn tex:5 \cdot 3 \equiv 1 (mod 7)

Hinweis: Im letzten Beispiel muss die Gleichung tex:5x \equiv 1 (mod 7) gelöst werden. Da tex:0 < x < 7 gilt, ist die Lösung durch Probieren rasch gefunden.

  • Gesucht ist die Modulo-Inverse von 4 (mod 8). Also ist die Gleichung tex:4 \cdot x \equiv 1 (mod 8) zu lösen. Dies ist nicht möglich, da tex:4x - 1 eine ungerade Zahl ist und somit kein Vielfaches von 8 sein kann.

Hinweis: In Anwendungen zur Kryptographie (Digitale Unterschrift) wählen wir als Modul eine Primzahl p und bestimmen die Modulo-Inversen zu r (mod p - 1). Dabei setzen wir voraus, dass r und (p - 1) teilferfremd sind.

Wähle im folgenden GeoGebra-Applet einen Modul m und eine Zahl r. Suche anschließend die Modulo-Inverse rinv!

Screenshot: Alfred Nussbaumer

Download der GeoGebra-Datei

Aufgaben:

  • Achte darauf, dass die Zahlen r und m teilerfremd sind (gcd(r,m) = 1). Untersuche, ob du eine Modulo-Inverse bestimmen kannst, wenn gcd(r,m) = 1 nicht gilt!
  • Untersuche: Gibt es immer eine Modulo-Inverse zu r, wenn r und m teilerfremd sind (gcd(r,m) = 1)?
  • Ist die Modulo-Inverse eindeutig? Untersuche dies bei verschiedenen Modulen m und vielen Zahlen r!
  • Recherchiere: Mit welchen Rechenverfahren kann die Modulo-Inverse bestimt werden?

Zurück zu Restklassen | Kryptographie | Digitale Unterschrift | RSA | GeoGebra 3.2: Texte codieren, Listen bearbeiten, Restklassenarithmetik ...