Die multiplikative Ordnung

Die multiplikative Ordnung

Das Konzept der multiplikativen Ordnung ist sehr alt und hat seit der Zeit von Fermat viele Mathematiker interessiert. Es spielt eine Rolle in vielen verschiedenen Zweigen der Mathematik. Wir werden einen kurzen Überblick über die Geschichte der Forschung in diesem Bereich geben bis hin zu neueren Arbeiten, die die Verteilung der Ordnung bezüglich Restklassen betreffen.

Jeder ist damit vertraut, dass 1/3 = 0.3333^{. . .} = 0.3¯, wobei mit 3¯ angegeben wird, dass die Ziffer 3 unendlich oft wiederholt wird. Man sagt, dass die Dezimaldarstellung von 1/3 periodisch mit Periode eins ist. ähnlich kann man sich fragen, welche Struktur die Dezimaldarstellung von 1/n hat, wenn n eine natürliche Zahl ist (Tab. 1).

Tabelle 1: Dezimaldarstellung von 1/n .

Nehmen wir an, dass n ungerade und nicht durch fünf teilbar ist. Wenn man eine schriftliche Division ausführt, wie sie jeder in der Schule kennengelernt hat, sieht man, dass die Dezimaldarstellung von 1/n die Periode m hat, wobei m die kleinste Zahl ≥ 1 ist, die die Eigenschaft hat, dass 10^m ≡ 1(mod n), d.h. 10^m hat den Rest eins nach Division durch n. Zum Beispiel gilt 10 ≠ 1 (mod 11) (das bedeutet, 10 hat nicht den Rest eins nach Division durch 11) und 10² = 100 ≡ 1 (mod 11) und deshalb sollte 1/11 eine Dezimaldarstellung mit Periode zwei haben. Tatsächlich gilt 1/11 = 0.0909... = 0.09. Es ist nicht schwer einzusehen, dass es immer eine Zahl (und somit eine kleinste Zahl) m gibt mit 10^m ≡ 1 (mod n), und allgemeiner für je zwei teilerfremde Zahlen g und n eine kleinste Zahl m mit g^m ≡ 1 (mod n). Diese Zahl m wird die multiplikative Ordnung von g modulo n genannt und mit ord_g(n) bezeichnet. Sie gibt die Länge der Periode der Entwicklung von 1/n in der Basis g an.

Der Begriff der multiplikativen Ordnung spielt eine Rolle in vielen verschiedenen Zweigen der Mathematik, wie etwa der Gruppentheorie oder der Kodierungstheorie. Zum Beispiel benutzt das so genannte RSA (Ramir-Shamir-Adleman) Kryptosystem, eine Methode zum sicheren Austausch von kodierten Informationen, die vom Banken häufig bei elektronischen Transaktionen angewendet wird, ganz wesentlich die Potenzbildung x → g^x und das Rechnen modulo einer großen Zahl n. Dies ist aber nur dann nützlich, falls die Ordnung von g modulo n groß ist, da die Kodierung sonst leicht von Unbefugten entziffert werden könnte. Man will also Zahlen n und g finden, für die ord_g(n) möglichst groß ist. Aus Resultaten von Fermat, Euler und Gauss weiß man, dass diese Ordnung immer kleiner als n ist, und dass der maximale Wert ord_g(n) = n - 1 nur dann angenommen werden kann, wenn n eine Primzahl ist. Umgekehrt gibt es für jede Primzahl p Zahlen g mit ord_g(p) = p - 1, die so genannten primitiven Wurzeln modulo p. Die Anwendung in der Kryptographie führt uns also zu der Frage, wie die primitiven Wurzeln von Primzahlen verteilt sind und speziell, ob jede natürliche Zahl g (Quadratzahlen muss man hier ausschließen) eine primitive Wurzel von unendlich vielen Primzahlen ist. Dass dies so ist, wurde von Artin 1927 vermutet. Die Gültigkeit der Artinschen Vermutung ist bis heute nicht nachgewiesen, konnte aber von Hooley (1967) unter Annahme der Verallgemeinerten Riemannschen Vermutung (VRV) - einer der berühmtesten offenen mathematischen Fragen überhaupt - gezeigt werden.

Trotz der Tatsache, dass der Begriff der multiplikativen Ordnung so alt ist, ist die Frage nach ihrer Verteilung über Restklassen modulo d erst vor kurzem untersucht worden, zuerst von den japanischen Mathematikern K.Chinen und L. Murata (2000) und dann von P. Moree am MPIM. Das wesentlich leichtere Problem der Teilbarkeit der Ordnungsfunktion durch eine vorgegebene Zahl d wurde schon früher von H. Hasse, R. Odoni und K. Wiertelak untersucht. Hier man kann unkonditionell zeigen, dass für gegebene Zahlen g und d die Dichte der Primzahlen p, für die ord_g(p) durch d teilbar ist, stets existiert und eine rationale Zahl ist. Ein typisches Resultat ist z.B.: für eine feste ungerade Zahl g ist die Ordnung ord_g(p) für zwei Drittel von allen Primzahlen p gerade (also nicht nur für die Hälfte, wie man naiverweise erwarten würde), während für g = 2 (also für die binäre Entwicklung von 1/p) die entsprechende Dichte 17/24 beträgt. Es ist aber viel schwieriger, und bisher nur unter Annahme der VRV gelungen, zu zeigen, dass für vorgegebene Zahlen g, d und a die Dichte δ_g(a, d) der Primzahlen p mit ord_g(p) ≡ a (mod d) existiert und diese zu bestimmen.

Es zeigt sich, dass die Analyse dieses naiv klingenden Problems komplizierte Überlegungen unter Verwendung tiefliegender Ergebnisse sowohl aus der analytischen wie auch aus der algebraischen Zahlentheorie (Klassenkörpertheorie) erfordert. Auch die Ergebnisse sind in verschiedenen Hinsichten überraschend. Zum Beispiel würde man erwarten, dass die Dichten δ_g(1, 4) und δ_g(3, 4) stets gleich sind, das heißt, dass die Periode der Entwicklung von 1/p in einer gegebenen Basis g, falls ungerade, mit gleicher Wahrscheinlichkeit den Rest 1 oder 3 nach Division durch 4 lässt. Es stellt sich aber heraus, dass diese Dichten durchaus voneinander abweichen können, und sogar ziemlich stark (Tab. 2), wobei allerdings immer δ_g(1, 4) ≤ δ_g(3, 4). Diese fehlende Gleichverteilung kann in bestimmten kryptografischen Umgebungen benutzt werden. Zweitens zeigt sich (immer noch unter Annahme der VRV), dass sich die Dichten δ_g(a, d) um eine bestimmte von g unabhängige Größe δ(a, d) orientieren, die man aus der Theorie der endlichen Körper gewinnt. Zum Beispiel sind die Werte von δ(a, d) für d = 4 und a = 0, 1, 2, 3 gleich 1/3, 1/6, 1/3, 1/6. Die Dichte δ_g(a, d) ist für fast alle Zahlen g gleich δ(a, d), und auch wenn diese zwei Zahlen verschieden sind, liegen sie meistens einander sehr nah, speziell dann, wenn g einen großen Primfaktor hat. Nur für Zahlen g, die eine hohe Potenz einer kleinen Zahl enthalten, wie g = 6²⁷ (s. Tabelle 2) kann δ_g(a, d) stark von dem Mittelwert δ(a, d) abweichen. Schließlich brauchen die Dichten δ_g(a, d), im Gegensatz zu den Zahlen δ(a, d) oder den Dichten bei dem einfacheren Problem von Wiertelak, nicht rational zu sein. Zum Beispiel ist die Differenz zwischen δ_g(3, 4) und δ_g(1, 4) immer ein rationales Vielfaches von einer bestimmten, vermutlich irrationalen Konstanten B = 0.643650679662^{. . .}, die eine Variante einer berühmten universellen Konstanten ist, die Artin bei der Untersuchung seiner Vermutung über primitive Wurzeln eingeführt hat.

Auf Grund der arithmetischen Komplexität der auftretenden Rechnungen sind einige numerische Experimente von Interesse. In Tabelle 2 werden für einige Werte von g die experimentellen Daten über die Differenz δ_g(3, 4) - δ_g(1, 4) für die ersten 100 Millionen Primzahlen p (also für alle p ≤ 2038074743) mit den theoretischen Werten verglichen. Die übereinstimmung ist exzellent.

Tabelle 2: Der Fall d = 4

Wie so häufig in der Zahlentheorie sieht man auch hier, wie eine elementar zu formulierende Frage zu tiefliegenden Überlegungen und zu überraschenden Ergebnissen und Anwendungen führen kann.