Rechner für die multiplikative Ordnung modulo n

Geben Sie eine ganzzahlige Basis a und einen Modul n ein. Das Ergebnis enthält den reduzierten Rest, die eulersche Phi-Funktion, die Ordnung und eine direkte modulare Probe. Die Berechnung ist nur definiert, wenn a und n teilerfremd sind. Ungültige Paare führen deshalb zu einer klaren Fehlermeldung statt zu einer irreführenden Zahl. Das Werkzeug eignet sich für Aufgaben zur modularen Arithmetik, die Untersuchung zyklischer Untergruppen, periodische Muster und die elementare Zahlentheorie.

Bedeutung der multiplikativen Ordnung

Für ganze Zahlen a und n ist die multiplikative Ordnung von a modulo n die kleinste positive ganze Zahl k, sodass a^k bei der Division durch n den Rest 1 besitzt. Der Zusatz „kleinste positive“ ist wesentlich: Auch spätere Exponenten können den Rest 1 ergeben, doch die Ordnung bezeichnet die erste Rückkehr zum neutralen Element der modularen Multiplikation. Die Potenzen von 2 modulo 9 liefern beispielsweise nacheinander die Reste 2, 4, 8, 7, 5 und schließlich 1; die Ordnung beträgt daher 6. Der Begriff beschreibt die Größe der von a erzeugten zyklischen Untergruppe innerhalb der invertierbaren Restklassen modulo n. Vor der Berechnung führt das Werkzeug a auf seinen üblichen nicht negativen Rest zurück. Negative Basen und Basen größer als n werden dadurch einheitlich behandelt. Zusätzlich wird ein Prüfwert aus der angegebenen Ordnung berechnet. Der Prüfwert 1 bestätigt die definierende Kongruenz; zugleich stellt die schrittweise Verkleinerung sicher, dass kein verbliebener echter Teiler des Kandidatenexponenten dieselbe Bedingung erfüllt.

Warum Teilerfremdheit erforderlich ist

Eine multiplikative Ordnung modulo n existiert nur, wenn gcd(a, n) gleich 1 ist. Das ist nicht bloß eine Eingabekonvention. Ein Element benötigt ein multiplikatives Inverses modulo n, damit seine Potenzen zur endlichen Einheitengruppe gehören und zu 1 zurückkehren können. Besitzen a und n einen gemeinsamen Faktor, bleibt bei jeder positiven Potenz von a ein entsprechendes Teilbarkeitshindernis bestehen; die Potenz kann daher nicht kongruent zu 1 modulo n sein. Der Rechner prüft diese Voraussetzung sofort und nennt den tatsächlichen größten gemeinsamen Teiler, falls sie verletzt ist. Außerdem muss der Modul mindestens 2 betragen, da die übliche Ordnungsfrage in einem nicht trivialen Restsystem gestellt wird. Die Basis darf innerhalb der veröffentlichten Grenze null, negativ oder positiv sein. Null ist jedoch für keinen zulässigen Modul gültig, weil sie nie teilerfremd zu n ist. Verwenden Sie für die Eingabe exakte ganze Zahlen und keine Dezimalzahlen oder wissenschaftlichen Näherungen. Nur so bleibt die diskrete Arithmetik erhalten, auf der größter gemeinsamer Teiler, Faktorisierung und modulare Potenzen beruhen.

So wird der kleinste Exponent gefunden

Der Rechner prüft nicht jeden Exponenten der Reihe nach. Zuerst wird n so weit faktorisiert, wie es zur Berechnung der eulerschen Phi-Funktion phi(n) erforderlich ist. Nach dem Satz von Euler ist a hoch phi(n) immer kongruent zu 1, sofern gcd(a, n) gleich 1 ist. Die gesuchte Ordnung muss somit phi(n) teilen. Anschließend faktorisiert der Algorithmus phi(n) und prüft wiederholt, ob die Division des aktuellen Kandidaten durch einen seiner Primfaktoren weiterhin eine modulare Potenz mit dem Wert 1 ergibt. Ist dies der Fall, ersetzt der kleinere Kandidat den bisherigen. Sobald kein Primfaktor mehr entfernt werden kann, ist der verbleibende Kandidat die multiplikative Ordnung. Die modulare Exponentiation arbeitet mit wiederholtem Quadrieren und reduziert Zwischenwerte stets modulo n; sämtliche Ganzzahloperationen bleiben exakt. Dieses Vorgehen ist erheblich schneller als das Durchlaufen aller positiven Exponenten, besonders bei einer großen Ordnung. Eingaben sind auf eine Billion begrenzt, damit die Probedivision eine klare deterministische Obergrenze besitzt und sowohl im Browser als auch bei automatisierten API-Aufrufen zuverlässig einsetzbar bleibt.