Rechner für das multiplikative Inverse modulo m

Finde modulare Inverse für teilerfremde ganze Zahlen mit dem erweiterten euklidischen Algorithmus.

Modulares Inverses berechnen

Gib eine ganze Zahl und einen Modul ein, um das kleinste nichtnegative Inverse zu bestimmen.

Zahl (a)

Modul (m)

Über den Rechner für multiplikative Inverse modulo m

Ein multiplikatives Inverses modulo m ist eine ganze Zahl, die eine Multiplikation in der modularen Arithmetik rückgängig macht. Für eine ganze Zahl a erfüllt ein Inverses x die Bedingung, dass a mal x bei Division durch m den Rest 1 lässt. Üblicherweise schreibt man: a mal x ist kongruent zu 1 modulo m. Zum Beispiel ergibt 3 mal 4 den Wert 12, und 12 lässt bei Division durch 11 den Rest 1. Daher ist 4 das multiplikative Inverse von 3 modulo 11. Nicht jedes Paar ganzer Zahlen besitzt ein Inverses. Die notwendige und hinreichende Bedingung ist, dass a und m teilerfremd sind, also den größten gemeinsamen Teiler 1 haben. Betrachte 6 modulo 9: Jedes Vielfache von 6 hat mit 9 den Faktor 3 gemeinsam und kann daher nicht den Rest 1 lassen. Dagegen haben 7 und 26 den ggT 1. Das Inverse von 7 modulo 26 ist 15, denn 105 lässt bei Division durch 26 den Rest 1. Der Rechner prüft den ggT, bevor er eine Antwort ausgibt. Der erweiterte euklidische Algorithmus findet das Inverse effizient. Der gewöhnliche Algorithmus berechnet den größten gemeinsamen Teiler durch wiederholtes Dividieren und Restbilden. Die erweiterte Fassung verfolgt zusätzlich Koeffizienten, sodass sich der ggT als ganzzahlige Linearkombination der ursprünglichen Eingaben darstellen lässt. Ist der ggT gleich 1, ist der Koeffizient von a ein Inverses. Dieser kann negativ sein. Deshalb reduziert der Rechner ihn modulo m und zeigt den kleinsten nichtnegativen Repräsentanten zwischen null und m minus eins an. Modulare Inverse ermöglichen Division innerhalb eines Kongruenzsystems. Um a mal x kongruent zu b modulo m zu lösen, multiplizierst du b mit dem Inversen von a, sofern es existiert. Sie sind wichtig für lineare Kongruenzen, den chinesischen Restsatz, modulare Brüche, Hashing, Fehlererkennung und Public-Key-Kryptografie. Zur RSA-Schlüsselerzeugung gehört beispielsweise das Bestimmen eines inversen Exponenten modulo einem Wert der eulerschen Phi-Funktion. Echte kryptografische Implementierungen verwenden sorgfältig auditierte Bibliotheken mit beliebiger Genauigkeit statt gewöhnlicher Browserzahlen. Gib nur ganze Zahlen ein und verwende einen Modul größer als 1. Negative Werte für a sind zulässig, da jede negative ganze Zahl einen äquivalenten kleinsten nichtnegativen Rest modulo m hat. Der Rechner nutzt sicher darstellbare JavaScript-Ganzzahlen und eignet sich für Unterrichtsübungen und Zahlentheorieaufgaben mittlerer Größe. Er zeigt den ggT und eine direkte Multiplikationsprobe an, damit du den Rest 1 überprüfen kannst. Für sehr große kryptografische Eingaben solltest du Software für große Ganzzahlen und sicherheitskritische Berechnungen verwenden.

Beispiele für modulare Inverse

Jedes Ergebnis ist die kleinste nichtnegative ganze Zahl, deren Produkt den Rest 1 lässt.

Zahl und Modul	Inverses	Überprüfung
3 modulo 11	4	Drei mal 4 ergibt 12, und 12 mod 11 ergibt 1.
7 modulo 26	15	Sieben mal 15 ergibt 105, und 105 mod 26 ergibt 1.
17 modulo 3120	2753	Siebzehn mal 2753 lässt modulo 3120 den Rest 1.
10 modulo 17	12	Zehn mal 12 ergibt 120, und 120 mod 17 ergibt 1.

So berechnest du ein modulares Inverses

Gib die ganze Zahl ein, deren multiplikatives Inverses du suchst.
Gib einen ganzzahligen Modul größer als 1 ein.
Wähle Modulares Inverses berechnen, um den erweiterten euklidischen Algorithmus auszuführen.
Prüfe, ob das angezeigte Produkt bei diesem Modul den Rest 1 hat.

Häufige Fragen zum multiplikativen Inversen modulo m

Wann existiert ein multiplikatives Inverses modulo m?

Genau dann, wenn die Zahl und der Modul teilerfremd sind. Gleichbedeutend damit muss ihr größter gemeinsamer Teiler 1 sein.

Warum scheinen mehrere inverse Werte möglich zu sein?

Durch Addition eines beliebigen ganzzahligen Vielfachen des Moduls entsteht ein kongruenter Repräsentant. Der Rechner vereinheitlicht die Ausgabe auf das kleinste nichtnegative Inverse.

Wie findet der erweiterte euklidische Algorithmus das Inverse?

Er berechnet den ggT und verfolgt dabei die Koeffizienten der ursprünglichen Zahlen. Ist der ggT 1, ist der Koeffizient der eingegebenen Zahl ein modulares Inverses.

Kann ich ein Inverses für eine negative Zahl berechnen?

Ja. Eine negative ganze Zahl lässt sich zunächst auf ihren äquivalenten Rest modulo m reduzieren. Der Rechner erledigt dies und liefert das kleinste nichtnegative Inverse.

Wie werden modulare Inverse in der Kryptografie eingesetzt?

Sie machen modulare Multiplikation in Algorithmen wie RSA und elliptischen Kurvensystemen rückgängig. Sicherheitsanwendungen benötigen große Ganzzahlen und Implementierungen mit konstanter Laufzeit, die über diesen Lernrechner hinausgehen.