Hauptmenü öffnen

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 Potenz der Primitivwurzel dargestellt werden kann.

Inhaltsverzeichnis

BeispielBearbeiten

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 ExistenzbedingungenBearbeiten

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 n, für welchen   ist (für die Schreibweise „mod“ siehe Modulo).

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.[1][2]

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 PrimitivwurzelnBearbeiten

Ausprobieren (Brute force)Bearbeiten

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 PrimzahlenBearbeiten

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.

BeispieleBearbeiten

Die folgende Tabelle zeigt die Primitivwurzeln modulo der Primzahlen bis 29.

    Primitivwurzeln modulo  
2 1 1
3 1 2
5 2 2, 3
7 2 3, 5
11 4 2, 6, 7, 8
13 4 2, 6, 7, 11
17 8 3, 5, 6, 7, 10, 11, 12, 14
19 6 2, 3, 10, 13, 14, 15
23 10 5, 7, 10, 11, 14, 15, 17, 19, 20, 21
29 12 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27

Primitivwurzeln modulo PrimzahlpotenzenBearbeiten

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.[1] 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  .[1]

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  .

AnwendungsbeispielBearbeiten

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.

WeblinksBearbeiten

LiteraturBearbeiten

Die Disquisitiones Arithmeticae wurden von Carl Friedrich Gauß auf Lateinisch veröffentlicht. Die zeitgenössische deutsche Übersetzung umfasst alle seine Schriften zur Zahlentheorie:

EinzelnachweiseBearbeiten

  1. a b c A. Leutbecher: Zahlentheorie – Eine Einführung in die Algebra. S. 53–54.
  2. Carl Friedrich Gauss: Untersuchungen über höhere Arithmetik. H. Maser, 1889, S. Art. 92, abgerufen am 30. Januar 2017.