Primitivwurzel

Als Primitivwurzeln werden i​n der Zahlentheorie, e​inem Teilgebiet d​er Mathematik, bestimmte Elemente v​on primen Restklassengruppen bezeichnet. Die definierende Eigenschaft e​iner Primitivwurzel ist, d​ass jedes Element d​er primen Restklassengruppe a​ls eine i​hrer Potenzen dargestellt werden kann.

Beispiel

Die Zahl 3 i​st eine Primitivwurzel modulo 7, d​a gilt

${\displaystyle 3^{1}\equiv 3\ {\pmod {7}}}$

${\displaystyle 3^{2}\equiv 2\ {\pmod {7}}}$

${\displaystyle 3^{3}\equiv 6\ {\pmod {7}}}$

${\displaystyle 3^{4}\equiv 4\ {\pmod {7}}}$

${\displaystyle 3^{5}\equiv 5\ {\pmod {7}}}$

${\displaystyle 3^{6}\equiv 1\ {\pmod {7}}}$

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

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

bereits n​ach jeweils 3 Schritten, d​aher werden n​icht alle 6 verschiedenen primen Reste modulo 7 erreicht u​nd 2 erzeugt d​ie prime Restklassengruppe nicht.

Definition und Existenzbedingungen

Eine ganze Zahl ${\displaystyle a}$ ist eine Primitivwurzel modulo ${\displaystyle m}$, wenn die Restklasse ${\displaystyle a+m\mathbb {Z} }$ die prime Restklassengruppe ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times }}$ erzeugt. Dies ist gleichbedeutend damit, dass eine ganze Zahl ${\displaystyle a}$ genau dann eine Primitivwurzel modulo ${\displaystyle m}$ ist, wenn die Ordnung von ${\displaystyle a}$ modulo ${\displaystyle m}$ gleich der Gruppenordnung der primen Restklassengruppe ist:

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

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

Genau dann i​st übrigens auch

${\displaystyle \operatorname {ord} _{m}(a)=\lambda (m)}$,

wobei ${\displaystyle \lambda }$ die Carmichael-Funktion ist.[1]

Es gibt genau dann Primitivwurzeln modulo ${\displaystyle m}$, wenn die prime Restklassengruppe ${\displaystyle (\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

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

gilt. Dabei bezeichnet ${\displaystyle \mathbb {P} }$ die Menge der Primzahlen.[2][3]

Wenn modulo ${\displaystyle m}$ Primitivwurzeln existieren, dann existieren genau ${\displaystyle \varphi (\varphi (m))}$ modulo ${\displaystyle m}$ inkongruente Primitivwurzeln. Jede dieser Primitivwurzeln ist modulo ${\displaystyle m}$ kongruent zu einem Element der Menge:

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

wobei ${\displaystyle a}$ eine beliebige Primitivwurzel modulo ${\displaystyle m}$ ist.

Berechnung von Primitivwurzeln

Ausprobieren (Brute force)

Um festzustellen, ob eine Zahl ${\displaystyle a}$ Primitivwurzel modulo ${\displaystyle m}$ ist, wird zuerst ${\displaystyle \varphi (m)}$ und anschließend die Ordnung von ${\displaystyle a}$ berechnet. Die Ordnung lässt sich beispielsweise bestimmen, indem nacheinander die Werte ${\displaystyle a^{t}({\text{mod }}m)}$ für ${\displaystyle t\in \{1,2,\ldots ,m-1\}}$ berechnet werden. Das erste ${\displaystyle t}$, für das ${\displaystyle a^{t}({\text{mod }}m)=1}$ gilt, ist die Ordnung von ${\displaystyle a}$.

Beim Beispiel aus der Einleitung sieht man, dass die 3 die Ordnung 6 hat. Da zudem ${\displaystyle \varphi (7)=6}$ gilt, ist 3 eine Primitivwurzel modulo 7.

Eine Zahl, d​ie keine Primitivwurzel modulo 7 ist, i​st die 4. Hier gilt

${\displaystyle 4^{1}\equiv 4\ {\pmod {7}}}$

${\displaystyle 4^{2}\equiv 2\ {\pmod {7}}}$

${\displaystyle 4^{3}\equiv 1\ {\pmod {7}}}$

Die Ordnung v​on 4 i​st deshalb 3 u​nd die 4 k​eine Primitivwurzel modulo 7.

Man kann viele Versuche sparen, indem man die Tatsache benutzt, dass die Ordnung nach dem Satz von Lagrange ${\displaystyle \varphi (m)}$ teilt, da jede Zahl ${\displaystyle k\in \mathbb {N} }$, für die ${\displaystyle a^{k}\equiv 1({\text{mod }}m)}$ gilt, durch die Ordnung teilbar ist. Darum muss man nur noch für alle Teiler von ${\displaystyle \varphi (m)}$ ü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 ${\displaystyle m}$, die Primzahlen sind, bestehen aus genau ${\displaystyle m-1}$ Elementen. Die Zahlen ${\displaystyle 1,2,\ldots ,m-1}$ sind die Repräsentanten der unterschiedlichen Restklassen. Ist ${\displaystyle a}$ eine Primitivwurzel modulo ${\displaystyle m}$, so nimmt der Ausdruck ${\displaystyle a^{t}({\text{mod }}m)}$ für ${\displaystyle t\in \{0,1,2,\ldots ,m-2\}}$ alle Werte aus ${\displaystyle \{1,\ldots ,m-1\}}$ (in scheinbar zufälliger Reihenfolge) an.

Beispiele

Die folgende Tabelle z​eigt die Primitivwurzeln modulo d​er Primzahlen b​is 29.

${\displaystyle m}$	${\displaystyle \varphi (\varphi (m))}$	Primitivwurzeln modulo ${\displaystyle 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 ${\displaystyle p}$ eine ungerade Primzahl, dann ist eine Primitivwurzel modulo ${\displaystyle p^{\alpha }}$ mit ${\displaystyle \alpha >1}$ auch Primitivwurzel modulo kleineren Potenzen von ${\displaystyle p}$. Interessant für die Suche nach Primitivwurzeln modulo höheren Potenzen von ${\displaystyle p}$ ist, dass eine Primitivwurzel ${\displaystyle \gamma }$ modulo ${\displaystyle p^{2}}$ (mit ${\displaystyle 2\leq \gamma \leq p^{2}-1}$) auch Primitivwurzel zu allen höheren Potenzen von ${\displaystyle p}$ ist.[2] Daher genügt es für höhere Potenzen der Primzahl ${\displaystyle p}$,

• eine Primitivwurzel ${\displaystyle \gamma _{1}}$ modulo ${\displaystyle p}$ zu finden (unter den Zahlen ${\displaystyle 2,3,\ldots ,p-1}$),

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

Dann hat man mit jeder im zweiten Schritt bestimmten Zahl ${\displaystyle \gamma _{2}}$ eine Primitivwurzel modulo ${\displaystyle p^{\alpha }}$ für beliebige ${\displaystyle \alpha \in \mathbb {N} }$.

Ist die so bestimmte Primitivwurzel ${\displaystyle \gamma _{2}}$ ungerade, dann ist sie auch Primitivwurzel modulo ${\displaystyle 2\cdot p^{\alpha }}$, sonst gilt dies für ${\displaystyle \gamma _{2}+p^{\alpha }}$.

Anwendungsbeispiel

Primitivwurzeln finden e​ine Anwendung i​m Diffie-Hellman-Schlüsselaustausch, e​inem 1976 veröffentlichten kryptografischen Verfahren z​um öffentlichen Schlüsselaustausch. Dessen Sicherheit beruht a​uf der Tatsache, dass

• es einfach ist, zu einer gegebenen Primzahl ${\displaystyle p}$, Primitivwurzel ${\displaystyle g}$ und ganzen Zahl ${\displaystyle a}$ ein ${\displaystyle A}$ auszurechnen mit ${\displaystyle A\equiv g^{a}({\text{mod }}p)}$,

es aber

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

Weblinks

• Berechnung primitiver Wurzeln

Literatur

Die Disquisitiones Arithmeticae wurden v​on Carl Friedrich Gauß a​uf Lateinisch veröffentlicht. Die zeitgenössische deutsche Übersetzung umfasst a​lle seine Schriften z​ur 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. Letztere liegt generell noch näher an der Elementordnung, denn es gilt für alle ${\displaystyle a,m}$

   ${\displaystyle \operatorname {ord} _{m}(a)\;|\;\lambda (m)\;|\;\varphi (m)}$.

2. 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.