Rechner für modulare Inverse

Ein multiplikatives Inverses einer ganzen Zahl a modulo m ist eine ganze Zahl x, deren Produkt mit a bei Division durch m den Rest 1 lässt. In Kongruenzschreibweise ist a mal x kongruent zu 1 modulo m. Dieser Rechner ermittelt das kleinste nicht negative Inverse mit dem erweiterten euklidischen Algorithmus und zeigt anschließend eine Multiplikationsprobe. Der Modul muss eine ganze Zahl größer als eins sein. Ein Inverses existiert genau dann, wenn a und m teilerfremd sind, ihr größter gemeinsamer Teiler also 1 ist. Haben sie einen größeren gemeinsamen Faktor, bleibt jedes Produkt mit a modulo m durch diesen Faktor teilbar und kann niemals Rest 1 ergeben. So besitzt 6 modulo 15 kein Inverses, weil der größte gemeinsame Teiler 3 ist. Dagegen ist 4 das Inverse von 3 modulo 11: 3 mal 4 ist 12 und lässt bei Division durch 11 den Rest 1. Der erweiterte euklidische Algorithmus berechnet nicht nur den größten gemeinsamen Teiler. Er findet auch Koeffizienten x und y, sodass ax plus my diesem Teiler entspricht. Ist der Teiler 1, ergibt die Reduktion von x modulo m das modulare Inverse. Bei negativem x verschiebt das Addieren ausreichend vieler m den Wert in den Standardbereich von null bis m minus eins, ohne die Kongruenzklasse zu ändern. Modulare Inverse ersetzen die Division in der modularen Arithmetik. Gewöhnliche Division lässt sich nicht einfach auf Restklassen anwenden, da verschiedene ganze Zahlen denselben Rest darstellen. Durch a modulo m zu teilen bedeutet, mit dem Inversen von a zu multiplizieren, sofern es existiert. Diese Technik ist zentral für lineare Kongruenzen, modulare Brüche, den chinesischen Restsatz und viele zahlentheoretische Algorithmen. Die Kryptografie nutzt modulare Inverse häufig. Bei der RSA-Schlüsselerzeugung wird das Inverse eines Exponenten modulo einem mit der eulerschen Phi-Funktion verbundenen Wert berechnet. Elliptische Kurven verwenden Inverse bei Punktformeln über endlichen Körpern. Auch Codierungstheorie, Prüfsummen, Pseudozufallsgeneratoren und Computeralgebra benötigen effiziente Inversenberechnungen. Reale kryptografische Implementierungen nutzen sorgfältig entwickelte Großzahl- und Constant-Time-Routinen statt der Zahlenarithmetik des Browsers; die zugrunde liegende Zahlentheorie bleibt gleich. Das Inverse ist modulo m eindeutig, nicht als gewöhnliche ganze Zahl. Ist 4 ein Inverses von 3 modulo 11, dann stellen auch 15, minus 7 und alle Zahlen, die sich um ein Vielfaches von 11 von 4 unterscheiden, dieselbe inverse Restklasse dar. Der Rechner gibt 4 aus, da sich der kleinste nicht negative Vertreter am einfachsten vergleichen und weiterverwenden lässt. Zur Prüfung multiplizieren Sie die ursprüngliche Zahl mit dem angezeigten Inversen, teilen durch den Modul und kontrollieren, ob der Rest 1 ist. Für negative Eingaben gilt dieselbe Regel, da Reste in den Standardbereich normalisiert werden können. Meldet das Tool, dass kein Inverses existiert, berechnen Sie den größten gemeinsamen Teiler unabhängig: Jeder Wert über 1 belegt das Hindernis.