Primitivwurzel-Rechner

Was ist eine Primitivwurzel?

Eine Primitivwurzel modulo n, auch Erzeuger der multiplikativen Gruppe genannt, ist eine ganze Zahl g, deren Potenzen g¹, g², g³, ..., g^φ(n) alle zu n teilerfremden Restklassen jeweils genau einmal erzeugen. In der Gruppentheorie ist g ein Erzeuger der zyklischen Gruppe (ℤ/nℤ)*.

Die multiplikative Ordnung eines Elements a modulo n ist die kleinste positive ganze Zahl k mit aᵏ ≡ 1 (mod n). Ein Element ist genau dann eine Primitivwurzel, wenn seine Ordnung φ(n), also der Ordnung der gesamten Gruppe, entspricht. Seine Potenzen durchlaufen die ganze Gruppe, bevor sie zu 1 zurückkehren.

Welche Moduln besitzen Primitivwurzeln?

Nicht für jedes n gibt es primitive Wurzeln. Der von Gauß bewiesene Satz über primitive Wurzeln liefert eine vollständige Charakterisierung. Primitivwurzeln existieren genau dann, wenn:

• n = 1 oder n = 2 (triviale Fälle)
• n = 4
• n = p^k für eine ungerade Primzahl p und k ≥ 1
• n = 2·p^k für eine ungerade Primzahl p und k ≥ 1

Zahlen wie n = 8, 12, 15, 16, 20 oder 24 erfüllen diese Bedingung nicht. Ihre multiplikativen Gruppen sind nicht zyklisch, daher kann kein einzelnes Element die gesamte Gruppe erzeugen. Beispielsweise gilt (ℤ/8ℤ)* ≅ ℤ&sub2; × ℤ&sub2;, die Kleinsche Vierergruppe, in der jedes von der Identität verschiedene Element Ordnung 2 hat.

Wie viele Primitivwurzeln gibt es?

Wenn Primitivwurzeln modulo n existieren, beträgt ihre Anzahl genau φ(φ(n)). Eine zyklische Gruppe der Ordnung m besitzt genau φ(m) Erzeuger. Da (ℤ/nℤ)* in diesem Fall zyklisch und von Ordnung φ(n) ist, besitzt sie φ(φ(n)) Erzeuger.

Für n = 7 gilt etwa φ(7) = 6 und φ(6) = 2. Damit sind 3 und 5 die beiden Primitivwurzeln. Für n = 23 erhält man φ(23) = 22 und φ(22) = 10, also zehn Primitivwurzeln.

Alle Primitivwurzeln aus einer einzigen erzeugen

Ist g eine Primitivwurzel modulo n, dann haben alle weiteren Primitivwurzeln die Form gᵏ (mod n), wobei ggT(k, φ(n)) = 1 und 1 ≤ k ≤ φ(n) gilt. So lassen sich aus der kleinsten gefundenen Primitivwurzel schnell alle weiteren bestimmen.

Referenztabelle: Häufige Primitivwurzeln

n	Typ	φ(n)	φ(φ(n))	Primitivwurzeln	Vorhanden?
2	2	1	1	{1}	JA
3	Primzahl	2	1	{2}	JA
4	4	2	1	{3}	JA
5	Primzahl	4	2	{2, 3}	JA
7	Primzahl	6	2	{3, 5}	JA
8	2³	4	—	keine	NEIN
9	3²	6	2	{2, 5}	JA
10	2·5	4	2	{3, 7}	JA
12	4·3	4	—	keine	NEIN
23	Primzahl	22	10	{5, 7, 10, 11, 14, 15, 17, 19, 20, 21}	JA

Anwendungen in der Kryptografie

Diffie-Hellman-Schlüsselaustausch: Das Verfahren verwendet eine große Primzahl p und eine Primitivwurzel g modulo p. Beide Seiten potenzieren g mit einem geheimen Exponenten und tauschen das Ergebnis aus. Die gemeinsame geheime Zahl folgt aus gᵃᵇ = (gᵃ)ᵇ = (gᵇ)ᵃ (mod p). Eine Primitivwurzel nutzt die gesamte Gruppe und verhindert Angriffe über kleine Untergruppen.

ElGamal-Verschlüsselung: Auch ElGamal beruht auf einem Erzeuger g modulo einer Primzahl p. Beim Verschlüsseln wird ein zufälliger Exponent verwendet; die Sicherheit hängt wie bei Diffie-Hellman von der Schwierigkeit des diskreten Logarithmus ab.

Problem des diskreten Logarithmus: Zu g und gᵏ mod p soll k gefunden werden. Die modulare Potenzierung ist effizient, ihre Umkehrung gilt für große geeignete Primzahlen jedoch als praktisch unlösbar. Darauf beruht die Sicherheit zahlreicher kryptografischer Protokolle.

Bezug zum kleinen Satz von Fermat: Für eine Primzahl p gilt aᵖ⁻¹ ≡ 1 (mod p), sofern p die Zahl a nicht teilt. Daher teilt die Ordnung jedes Elements von (ℤ/pℤ)* die Zahl p-1 = φ(p). Eine Primitivwurzel hat genau die maximale Ordnung p-1.