Zum Inhalt springen

Primitivwurzel

aus Wikipedia, der freien Enzyklopädie

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.

Die Zahl 3 ist eine Primitivwurzel modulo 7, da gilt

31=30⋅3≡1⋅3=3≡3(mod7)32=31⋅3≡3⋅3=9≡2(mod7)33=32⋅3≡2⋅3=6≡6(mod7)34=33⋅3≡6⋅3=18≡4(mod7)35=34⋅3≡4⋅3=12≡5(mod7)36=35⋅3≡5⋅3=15≡1(mod7)

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

(2k)k∈ℕ=(21≢1,22≢1,23≡1,24≡2,25≡22…)

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

[Bearbeiten | Quelltext bearbeiten]

Eine ganze Zahl a ist eine Primitivwurzel modulo m, wenn die Restklasse a+mℤ die prime Restklassengruppe (ℤ/mℤ)× erzeugt. Dies ist gleichbedeutend damit, dass eine ganze Zahl a genau dann eine Primitivwurzel modulo m ist, wenn die Ordnung von a modulo m gleich der Gruppenordnung der primen Restklassengruppe ist:

ordm(a)=φ(m).

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

Genau dann ist übrigens auch

ordm(a)=λ(m),

wobei λ die Carmichael-Funktion ist.[1]

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

m∈{2,4}∪{kpα∣2<p∈ℙ, α∈ℕ, k∈{1,2}}

gilt. Dabei bezeichnet ℙ die Menge der Primzahlen.[2][3]

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

{an∣1≤n≤φ(m), ggT⁡(n,φ(m))=1}

wobei a eine beliebige Primitivwurzel modulo m ist.

Berechnung von Primitivwurzeln

[Bearbeiten | Quelltext bearbeiten]

Ausprobieren (Brute force)

[Bearbeiten | Quelltext bearbeiten]

Um festzustellen, ob eine Zahl a Primitivwurzel modulo m ist, wird zuerst φ(m) und anschließend die Ordnung von a berechnet. Die Ordnung lässt sich beispielsweise bestimmen, indem nacheinander die Werte at(mod m) für t∈{1,2,…,m−1} berechnet werden. Das erste t, für das at(mod m)=1 gilt, ist die Ordnung von a.

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

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

41≡4 (mod7)
42≡2 (mod7)
43≡1 (mod7)

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 φ(m) teilt, da jede Zahl k∈ℕ, für die ak≡1(mod m) gilt, durch die Ordnung teilbar ist. Darum muss man nur noch für alle Teiler von φ(m) überprüfen, ob Exponentiation mit ihnen die Zahl auf 1 abbildet, und der kleinste solche Teiler ist die Ordnung.

Primitivwurzeln modulo Primzahlen

[Bearbeiten | Quelltext bearbeiten]

Die primen Restklassengruppen zu Moduln m, die Primzahlen sind, bestehen aus genau m−1 Elementen. Die Zahlen 1,2,…,m−1 sind die Repräsentanten der unterschiedlichen Restklassen. Ist a eine Primitivwurzel modulo m, so nimmt der Ausdruck at(mod m) für t∈{0,1,2,…,m−2} alle Werte aus {1,…,m−1} (in scheinbar zufälliger Reihenfolge) an.

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

mφ(φ(m))Primitivwurzeln modulo m
211
312
522, 3
723, 5
1142, 6, 7, 8
1342, 6, 7, 11
1783, 5, 6, 7, 10, 11, 12, 14
1962, 3, 10, 13, 14, 15
23105, 7, 10, 11, 14, 15, 17, 19, 20, 21
29122, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27
3183, 11, 12, 13, 17, 21, 22, 24
37122, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35
41166, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35
43123, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 34
47225, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45
53242, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 51
59282, 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, 56
61162, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59
67202, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63
71247, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 69
73245, 11, 13, 14, 15, 20, 26, 28, 29, 31, 33, 34, 39, 40, 42, 44, 45, 47, 53, 58, 59, 60, 62, 68
79243, 6, 7, 28, 29, 30, 34, 35, 37, 39, 43, 47, 48, 53, 54, 59, 60, 63, 66, 68, 70, 74, 75, 77
83402, 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, 80
89403, 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, 86
97325, 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

[Bearbeiten | Quelltext bearbeiten]

Ist p eine ungerade Primzahl, dann ist eine Primitivwurzel modulo pα mit α>1 auch Primitivwurzel modulo kleineren Potenzen von p. Interessant für die Suche nach Primitivwurzeln modulo höheren Potenzen von p ist, dass eine Primitivwurzel γ modulo p2 (mit 2≤γ≤p2−1) auch Primitivwurzel zu allen höheren Potenzen von p ist.[2] Daher genügt es für höhere Potenzen der Primzahl p,

  • eine Primitivwurzel γ1 modulo p zu finden (unter den Zahlen 2,3,…,p−1),
  • die Zahlen γ1+k⋅p,(0≤k≤p−1) daraufhin zu testen, ob sie Primitivwurzeln modulo p2 sind. Notwendig und bereits hinreichend dafür ist, dass (γ1+k⋅p)p−1≢1(mod p2) ist. Tatsächlich tritt dies bereits für k=0 oder k=1 ein, d. h. γ1 oder γ1+p ist eine Primitivwurzel modulo p2.[2]

Dann hat man mit jeder im zweiten Schritt bestimmten Zahl γ2 eine Primitivwurzel modulo pα für beliebige α∈ℕ.

Ist die so bestimmte Primitivwurzel γ2 ungerade, dann ist sie auch Primitivwurzel modulo 2⋅pα, sonst gilt dies für γ2+pα.

Anwendungsbeispiel

[Bearbeiten | Quelltext bearbeiten]

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 p, Primitivwurzel g und ganzen Zahl a ein A auszurechnen mit A≡ga(mod p),

es aber

  • aufwendig ist, für ein bekanntes A ein entsprechendes a (den sogenannten diskreten Logarithmus) zu finden.

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

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. ↑ Letztere liegt generell noch näher an der Elementordnung, denn es gilt für alle a,m
    ordm(a)|λ(m)|φ(m).
  2. 1 2 3 A. Leutbecher: Zahlentheorie – Eine Einführung in die Algebra. S. 53–54.
  3. ↑ Carl Friedrich Gauss: Untersuchungen über höhere Arithmetik. H. Maser, 1889, S. Art. 92, abgerufen am 30. Januar 2017.