Primitivwurzel

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.

Beispiel

Die Zahl 3 ist eine Primitivwurzel modulo 7, da gilt

$3^1 \equiv 3\ \pmod 7$

$3^2 \equiv 2\ \pmod 7$

$3^3 \equiv 6\ \pmod 7$

$3^4 \equiv 4\ \pmod 7$

$3^5 \equiv 5\ \pmod 7$

$3^6 \equiv 1\ \pmod 7$

Es lassen sich also alle Elemente $1, 2, \ldots, 6$ der primen Restklassengruppe modulo 7 als Potenzen von 3 darstellen. Die Zahl 2 ist keine Primitivwurzel modulo 7, da $2^3 =8 \equiv 1\ \pmod 7$ ist, daher wiederholen sich die Reste in der Folge der Potenzen von 2 modulo 7

$(2^k)_{k\in \mathbb{N}}=(2^1,2^2,2^3\equiv 1, 2^4\equiv 2\,\ldots)$

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 a ist eine Primitivwurzel modulo m, wenn die Restklasse $a + m\mathbb{Z}$ die prime Restklassengruppe $(\mathbb{Z} /m\mathbb{Z})^\times$ 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:

$\operatorname{ord}_m(a)=\varphi(m)$.

Hierbei ist φ die Eulersche φ-Funktion und $\operatorname{ord}_m(a)$ die multiplikative Ordnung modulo m des Elements a, d. h. der kleinste positive Exponent n, für welchen $a^n \equiv 1 \; (\bmod \; m)$ ist (für die Schreibweise „mod“ siehe Modulo).

Es gibt genau dann Primitivwurzeln modulo m, wenn die prime Restklassengruppe $(\mathbb{Z} /m\mathbb{Z})^\times$ eine zyklische Gruppe ist. Dies ist nach einem Satz von C. F. Gauß genau dann der Fall, wenn für den Modul

$m \in \{2, 4, p^\alpha, 2p^\alpha | p \in \mathbb{P}\setminus\{2\};\; \alpha \in \mathbb{N}\}$

gilt. Dabei bezeichnet $\mathbb{P}\setminus\{2\}$ die Menge der ungeraden Primzahlen.^[1]

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:

$\{a^n \mid 1 \le n \le \varphi(m),\ \operatorname{ggT}(n, \varphi(m))=1\}$

wobei a eine beliebige Primitivwurzel modulo m ist.

Berechnung von Primitivwurzeln

Ausprobieren (Brute force)

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 a^tmod m für $t \in \{1, 2, \ldots, m - 1\}$ berechnet werden. Das erste t, für das a^tmod 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

$4^1 \equiv 4\ \pmod 7$

$4^2 \equiv 2\ \pmod 7$

$4^3 \equiv 1\ \pmod 7$

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

Primitivwurzeln modulo Primzahlen

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

Beispiele

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

m	$\varphi(\varphi(m))$	Primitivwurzeln modulo m
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 Primzahlpotenzen

Ist p eine ungerade Primzahl, dann ist eine Primitivwurzel modulo $p^{\alpha};\,\alpha >1$ auch Primitivwurzel modulo kleineren Potenzen von p. Interessant für die Suche nach Primtivwurzeln modulo höheren Potenzen von p ist, dass eine Primitivwurzel γ modulo p² (mit $1\leq \gamma\leq p^2-1$) auch Primitivwurzel zu allen höheren Potenzen von p ist.^[1]. Daher genügt es für höhere Potenzen der Primzahl,

• eine Primitivwurzel γ₁ modulo p zu finden (unter den Zahlen $2,3,\ldots,p-1$),

• die Zahlen $\gamma_1 + k\cdot p,\; (0\leq k \leq p-1)$ daraufhin zu testen, ob sie Primitivwurzeln modulo p² sind - notwendig und bereits hinreichend dafür ist, dass $(\gamma_1 + k\cdot p)^{p-1} \not\equiv 1 \mod p^2$ ist. Tatsächlich tritt dies bereits für k = 0 oder k = 1 ein, d. h. γ₁ oder γ₁ + p ist eine Primitivwurzel modulo p².^[1]

Dann hat man mit jeder im zweiten Schritt bestimmten Zahl γ₂ eine Primitivwurzel modulo p^α für beliebige $\alpha\geq 1$.

Ist die so bestimmte Primitivwurzel γ₂ ungerade, dann ist sie auch Primitivwurzel modulo $2\cdot p^\alpha$, sonst gilt dies für γ₂ + p^α.

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 m, Primitivwurzel a und ganzen Zahl i ein b auszurechnen mit b = aⁱmod m,

es aber

• aufwendig ist, für ein bekanntes b ein entsprechendes i (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

1. ↑ ^{a b c} A. Leutbecher: Zahlentheorie - Eine Einführung in die Algebra, S. 53-54.