Als Primitivwurzeln werden in der Zahlentheorie, einem Teilgebiet der Mathematik, bestimmte Elemente von primen Restklassengruppen bezeichnet. Die definierende Eigenschaft einer Primitivwurzel ist, dass jedes Element der primen Restklassengruppe als eine ihrer Potenzen dargestellt werden kann.

Beispiel Die Zahl 3 ist eine Primitivwurzel modulo 7, da gilt

Es lassen sich also alle Elemente der primen Restklassengruppe modulo 7 als Potenzen von 3 darstellen, wobei der Exponent der dem jeweiligen Element zugeordnete Index (diskreter Logarithmus) ist. Die Zahl 2 ist keine Primitivwurzel modulo 7, da ist, daher wiederholen sich die Reste in der Folge der Potenzen von 2 modulo 7

bereits nach jeweils 3 Schritten, daher werden nicht alle 6 verschiedenen primen Reste modulo 7 erreicht und 2 erzeugt die prime Restklassengruppe nicht.

Definition und Existenzbedingungen Eine ganze Zahl ist eine Primitivwurzel modulo , wenn die Restklasse die prime Restklassengruppe erzeugt. Dies ist gleichbedeutend damit, dass eine ganze Zahl genau dann eine Primitivwurzel modulo ist, wenn die Ordnung von modulo gleich der Gruppenordnung der primen Restklassengruppe ist: .

Hierbei ist die Eulersche φ-Funktion und die multiplikative Ordnung modulo m des Elements , d. h. der kleinste positive Exponent , für welchen ist (für die Schreibweise „mod“ siehe Modulo).

Genau dann ist übrigens auch , wobei die Carmichael-Funktion ist.Letztere liegt generell noch näher an der Elementordnung, denn es gilt für alle .

Es gibt genau dann Primitivwurzeln modulo , wenn die prime Restklassengruppe eine zyklische Gruppe ist. Dies ist nach einem Satz von C. F. Gauß genau dann der Fall, wenn für den Modul

gilt. Dabei bezeichnet die Menge der Primzahlen.

Wenn modulo Primitivwurzeln existieren, dann existieren genau modulo inkongruente Primitivwurzeln. Jede dieser Primitivwurzeln ist modulo kongruent zu einem Element der Menge:

wobei eine beliebige Primitivwurzel modulo ist.

Berechnung von Primitivwurzeln Ausprobieren (Brute force) Um festzustellen, ob eine Zahl Primitivwurzel modulo ist, wird zuerst und anschließend die Ordnung von berechnet. Die Ordnung lässt sich beispielsweise bestimmen, indem nacheinander die Werte für berechnet werden. Das erste , für das gilt, ist die Ordnung von .

Beim Beispiel aus der Einleitung sieht man, dass die 3 die Ordnung 6 hat. Da zudem gilt, ist 3 eine Primitivwurzel modulo 7.

Eine Zahl, die keine Primitivwurzel modulo 7 ist, ist die 4. Hier gilt

Die Ordnung von 4 ist deshalb 3 und die 4 keine Primitivwurzel modulo 7.

Man kann viele Versuche sparen, indem man die Tatsache benutzt, dass die Ordnung nach dem Satz von Lagrange teilt, da jede Zahl , für die gilt, durch die Ordnung teilbar ist. Darum muss man nur noch für alle Teiler von überprüfen, ob Exponentiation mit ihnen die Zahl auf 1 abbildet, und der kleinste solche Teiler ist die Ordnung.

Primitivwurzeln modulo Primzahlen Die primen Restklassengruppen zu Moduln , die Primzahlen sind, bestehen aus genau Elementen. Die Zahlen sind die Repräsentanten der unterschiedlichen Restklassen. Ist eine Primitivwurzel modulo , so nimmt der Ausdruck für alle Werte aus (in scheinbar zufälliger Reihenfolge) an.

Beispiele Die folgende Tabelle zeigt die Primitivwurzeln modulo der Primzahlen bis 100.

Primitivwurzeln modulo 2 1 13 1 25 2 2, 37 2 3, 511 4 2, 6, 7, 813 4 2, 6, 7, 1117 8 3, 5, 6, 7, 10, 11, 12, 1419 6 2, 3, 10, 13, 14, 1523 10 5, 7, 10, 11, 14, 15, 17, 19, 20, 2129 12 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 2731 8 3, 11, 12, 13, 17, 21, 22, 2437 12 2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 3541 16 6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 3543 12 3, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 3447 22 5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 4553 24 2, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 5159 28 2, 6, 8, 10, 11, 13, 14, 18, 23, 24, 30, 31, 32, 33, 34, 37, 38, 39, 40, 42, 43, 44, 47, 50, 52, 54, 55, 5661 16 2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 5967 20 2, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 6371 24 7, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 6973 24 5, 11, 13, 14, 15, 20, 26, 28, 29, 31, 33, 34, 39, 40, 42, 44, 45, 47, 53, 58, 59, 60, 62, 6879 24 3, 6, 7, 28, 29, 30, 34, 35, 37, 39, 43, 47, 48, 53, 54, 59, 60, 63, 66, 68, 70, 74, 75, 7783 40 2, 5, 6, 8, 13, 14, 15, 18, 19, 20, 22, 24, 32, 34, 35, 39, 42, 43, 45, 46, 47, 50, 52, 53, 54, 55, 56, 57, 58, 60, 62, 66, 67, 71, 72, 73, 74, 76, 79, 8089 40 3, 6, 7, 13, 14, 15, 19, 23, 24, 26, 27, 28, 29, 30, 31, 33, 35, 38, 41, 43, 46, 48, 51, 54, 56, 58, 59, 60, 61, 62, 63, 65, 66, 70, 74, 75, 76, 82, 83, 8697 32 5, 7, 10, 13, 14, 15, 17, 21, 23, 26, 29, 37, 38, 39, 40, 41, 56, 57, 58, 59, 60, 68, 71, 74, 76, 80, 82, 83, 84, 87, 90, 92

Primitivwurzeln modulo Primzahlpotenzen Ist eine ungerade Primzahl, dann ist eine Primitivwurzel modulo mit auch Primitivwurzel modulo kleineren Potenzen von . Interessant für die Suche nach Primitivwurzeln modulo höheren Potenzen von ist, dass eine Primitivwurzel modulo (mit ) auch Primitivwurzel zu allen höheren Potenzen von ist.A. Leutbecher: Zahlentheorie – Eine Einführung in die Algebra. S. 53–54. Daher genügt es für höhere Potenzen der Primzahl ,

eine Primitivwurzel modulo zu finden (unter den Zahlen ),

die Zahlen daraufhin zu testen, ob sie Primitivwurzeln modulo sind. Notwendig und bereits hinreichend dafür ist, dass ist. Tatsächlich tritt dies bereits für oder ein, d. h. oder ist eine Primitivwurzel modulo .

Dann hat man mit jeder im zweiten Schritt bestimmten Zahl eine Primitivwurzel modulo für beliebige .

Ist die so bestimmte Primitivwurzel ungerade, dann ist sie auch Primitivwurzel modulo , sonst gilt dies für .

Anwendungsbeispiel Primitivwurzeln finden eine Anwendung im Diffie-Hellman-Schlüsselaustausch, einem 1976 veröffentlichten kryptografischen Verfahren zum öffentlichen Schlüsselaustausch. Dessen Sicherheit beruht auf der Tatsache, dass es einfach ist, zu einer gegebenen Primzahl , Primitivwurzel und ganzen Zahl ein auszurechnen mit , es aber aufwendig ist, für ein bekanntes ein entsprechendes (den sogenannten diskreten Logarithmus) zu finden.

Weblinks Berechnung primitiver Wurzeln

Literatur Die Disquisitiones Arithmeticae wurden von Carl Friedrich Gauß auf Lateinisch veröffentlicht. Die zeitgenössische deutsche Übersetzung umfasst alle seine Schriften zur Zahlentheorie: Carl Friedrich Gauß: Untersuchungen über höhere Arithmetik (deutsche Übersetzung), Original: Leipzig 1801. Peter Bundschuh: Einführung in die Zahlentheorie. 5. Auflage. Springer Verlag, 2002, ISBN 3-540-43579-4, S. 109–120 Armin Leutbecher: Zahlentheorie – Eine Einführung in die Algebra. 1. Auflage. Springer Verlag, 1996, Berlin Heidelberg New York. ISBN 3-540-58791-8.

Einzelnachweise

Kategorie:Zahlentheorie