Definition
Für eine ganze Zahl a, die teilerfremd zu N ist, ist die multiplikative Ordnung die kleinste positive ganze Zahl k mit a^k ≡ 1 (mod N); sie ist die Ordnung von a in der Gruppe (Z/NZ)^×.
Prinzip
Prinzip
Die Ordnung von a teilt φ(N) und bestimmt die Struktur der von a erzeugten zyklischen Untergruppe; Ordnungen legen die Periodizität von Potenzen und den Gültigkeitsbereich diskreter Logarithmen fest.
Demonstration
Demonstration
Für a = 3 und N = 7 gilt: 3^1≡3, 3^2≡2, 3^3≡6, 3^4≡4, 3^5≡5, 3^6≡1 (mod 7), daher ist die multiplikative Ordnung von 3 modulo 7 gleich 6.
Fehlanwendung
Fehlanwendung
Anzunehmen, eine Ordnung existiere für a, das nicht teilerfremd zu N ist, oder die multiplikative Ordnung mit der additiven Ordnung zu verwechseln, führt zu falschen algebraischen Schlüssen.
Konsequenz
Konsequenz
Die Kenntnis der Ordnung von a liefert die Größe der von a erzeugten zyklischen Untergruppe, zeigt, welche Exponenten ein gegebenes Residuum ergeben, und beschränkt Lösungen von Kongruenzen wie a^x ≡ b (mod N).
Umkehrung
Umkehrung
Umgekehrt gibt es Elemente der Ordnung 1 (Identität) oder sehr kleiner Ordnung, die nur triviale oder kleine Untergruppen erzeugen statt voller Zyklen; Elemente deren Ordnung einen echten Teiler von φ(N) teilt, erzeugen nicht alle Einheiten.
Abgrenzung
Abgrenzung
Definiert nur für a mit gcd(a,N)=1; die Ordnung ist endlich und teilt φ(N). Sie gilt nicht für Nullteiler oder für nicht-ganzzahlige Basen, es sei denn, man verallgemeinert die Einheitengruppe.
Semantische Spannung
Semantische Spannung
Man muss die multiplikative Ordnung modulo N von ähnlichen Begriffen in anderen algebraischen Kontexten unterscheiden, etwa bei Matrizen, wo ‚Ordnung‘ ebenfalls die kleinste positive Potenz zur Identitätsmatrix bezeichnet.
Synthese
Synthese
Die multiplikative Ordnung modulo N gibt an, nach wie vielen Multiplikationen mit a man wieder 1 modulo N erhält und beschreibt so die zyklische Untergruppenstruktur, die a in der Einheitengruppe erzeugt.