imported>DJGrandfather: Beispiel etwas erweitert

2023-09-23T12:24:10Z

Beispiel etwas erweitert

Neue Seite

Als '''Primitivwurzeln''' werden in der [[Zahlentheorie]], einem [[Teilgebiete der Mathematik|Teilgebiet der Mathematik]], bestimmte Elemente von [[Prime Restklassengruppe|primen Restklassengruppen]] bezeichnet. Die definierende Eigenschaft einer Primitivwurzel ist, dass jedes Element der primen Restklassengruppe als eine ihrer [[Potenz (Mathematik)|Potenzen]] dargestellt werden kann.

== Beispiel ==
Die Zahl 3 ist eine Primitivwurzel modulo 7, da gilt
:<math>
\begin{array}{rcrcrcrcrcr}
3^1 &=& 3^0 \cdot 3 &\equiv& 1 \cdot 3 &=& 3 &\equiv& 3 \pmod 7 \\
3^2 &=& 3^1 \cdot 3 &\equiv& 3 \cdot 3 &=& 9 &\equiv& 2 \pmod 7 \\
3^3 &=& 3^2 \cdot 3 &\equiv& 2 \cdot 3 &=& 6 &\equiv& 6 \pmod 7 \\
3^4 &=& 3^3 \cdot 3 &\equiv& 6 \cdot 3 &=& 18 &\equiv& 4 \pmod 7 \\
3^5 &=& 3^4 \cdot 3 &\equiv& 4 \cdot 3 &=& 12 &\equiv& 5 \pmod 7 \\
3^6 &=& 3^5 \cdot 3 &\equiv& 5 \cdot 3 &=& 15 &\equiv& 1 \pmod 7 \\
\end{array}
</math>
Es lassen sich also alle Elemente <math>1, 2, \ldots, 6</math> der primen Restklassengruppe modulo 7 als Potenzen <math>3^i</math> von 3 darstellen, wobei der Exponent <math>i</math> der dem jeweiligen Element zugeordnete ''Index'' ([[diskreter Logarithmus]]) ist. Die Zahl 2 ist ''keine'' Primitivwurzel modulo 7, da <math>2^3 =8 \equiv 1\ (\text{mod } 7)</math> ist, daher wiederholen sich die Reste in der Folge der Potenzen von 2 modulo 7
:<math>(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)</math>
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 <math>a</math> ist eine Primitivwurzel modulo <math>m</math>, wenn die [[Restklasse]] <math>a + m\mathbb{Z}</math> die [[prime Restklassengruppe]] <math>(\mathbb{Z} /m\mathbb{Z})^\times</math> [[Erzeuger (Algebra)|erzeugt]]. Dies ist gleichbedeutend damit, dass eine ganze Zahl <math>a</math> genau dann eine Primitivwurzel modulo <math>m</math> ist, wenn die Ordnung von <math>a</math> modulo <math>m</math> gleich der Gruppenordnung der primen Restklassengruppe ist:
:<math>\operatorname{ord}_m(a)=\varphi(m)</math>.

Hierbei ist <math>\varphi</math> die [[Eulersche φ-Funktion]] und <math>\operatorname{ord}_m(a)</math> die [[Ordnung eines Gruppenelementes|multiplikative Ordnung modulo ''m'']] des Elements <math>a</math>, d. h. der kleinste positive Exponent <math>n</math>, für welchen <math>a^n \equiv 1 \; (\text{mod } m) </math> ist (für die Schreibweise „mod“ siehe [[Modulo]]).

[[Carmichael-Funktion#Die Carmichael-Funktion und die eulersche φ-Funktion|Genau dann]] ist übrigens auch
:<math>\operatorname{ord}_m(a)=\lambda(m)</math>,
wobei <math>\lambda</math> die [[Carmichael-Funktion]] ist.<ref>Letztere liegt generell noch näher an der Elementordnung, denn es gilt für alle <math>a,m</math>
:<math>\operatorname{ord}_m(a) \; | \; \lambda(m)\; | \; \varphi(m)</math>.</ref>

Es gibt genau dann Primitivwurzeln modulo <math>m</math>, wenn die prime Restklassengruppe <math>(\mathbb{Z} /m\mathbb{Z})^\times</math> eine [[zyklische Gruppe]] ist. Dies ist nach einem Satz von [[Carl Friedrich Gauß|C. F. Gauß]] genau dann der Fall, wenn für den Modul
:<math>m \in \{2, 4\} \cup \{ kp^\alpha \mid 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N},\ k \in \{1,2\} \}</math>
gilt. Dabei bezeichnet <math>\mathbb{P} </math> die Menge der Primzahlen.<ref name="Leutbecher" /><ref>{{Internetquelle|url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=PPN373456743|titel=Untersuchungen über höhere Arithmetik|autor=Carl Friedrich Gauss|hrsg=H. Maser|werk=|seiten=Art. 92|datum=1889|sprache=de|zugriff=2017-01-30}}</ref>

Wenn modulo <math>m</math> Primitivwurzeln existieren, dann existieren genau <math>\varphi(\varphi(m))</math> modulo <math>m</math> inkongruente Primitivwurzeln. Jede dieser Primitivwurzeln ist modulo <math>m</math> kongruent zu einem Element der Menge:

: <math>\{a^n \mid 1 \le n \le \varphi(m),\ \operatorname{ggT}(n, \varphi(m))=1\}</math>

wobei <math>a</math> eine beliebige Primitivwurzel modulo <math>m</math> ist.

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

Beim Beispiel aus der Einleitung sieht man, dass die 3 die Ordnung 6 hat. Da zudem <math>\varphi(7) = 6</math> gilt, ist 3 eine Primitivwurzel modulo 7.

Eine Zahl, die keine Primitivwurzel modulo 7 ist, ist die 4. Hier gilt
:<math>4^1 \equiv 4\ \pmod 7</math>
:<math>4^2 \equiv 2\ \pmod 7</math>
:<math>4^3 \equiv 1\ \pmod 7</math>
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]] <math>\varphi(m)</math> teilt, da jede Zahl <math>k \in \mathbb N</math>, für die <math>a^k \equiv 1 (\text{mod } m)</math> gilt, durch die Ordnung teilbar ist. Darum muss man nur noch für alle Teiler von <math>\varphi(m)</math> ü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 <math>m</math>, die [[Primzahl]]en sind, bestehen aus genau <math>m - 1</math> Elementen. Die Zahlen <math>1, 2, \ldots, m - 1</math> sind die Repräsentanten der unterschiedlichen Restklassen. Ist <math>a</math> eine Primitivwurzel modulo <math>m</math>, so nimmt der Ausdruck <math>a^t (\text{mod } m)</math> für <math>t \in \{0, 1, 2, \ldots, m-2\}</math> alle Werte aus <math>\{1,\ldots,m-1\}</math> (in scheinbar zufälliger Reihenfolge) an.

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

{| class="wikitable"
! <math>m</math> || <math>\varphi(\varphi(m))</math> || Primitivwurzeln modulo <math>m</math>
|-
|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
|-
|31 || 8 || 3, 11, 12, 13, 17, 21, 22, 24
|-
|37 || 12 || 2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35
|-
|41 || 16 || 6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35
|-
|43 || 12 || 3, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 34
|-
|47 || 22 || 5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45
|-
|53 || 24 || 2, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 51
|-
|59 || 28 || 2, 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
|-
|61 || 16 || 2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59
|-
|67 || 20 || 2, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63
|-
|71 || 24 || 7, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 69
|-
|73 || 24 || 5, 11, 13, 14, 15, 20, 26, 28, 29, 31, 33, 34, 39, 40, 42, 44, 45, 47, 53, 58, 59, 60, 62, 68
|-
|79 || 24 || 3, 6, 7, 28, 29, 30, 34, 35, 37, 39, 43, 47, 48, 53, 54, 59, 60, 63, 66, 68, 70, 74, 75, 77
|-
|83 || 40 || 2, 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
|-
|89 || 40 || 3, 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
|-
|97 || 32 || 5, 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 ===
Ist <math>p</math> eine ''ungerade'' Primzahl, dann ist eine Primitivwurzel modulo <math>p^{\alpha}</math> mit <math>\alpha >1</math> auch Primitivwurzel modulo kleineren Potenzen von <math>p</math>. Interessant für die Suche nach Primitivwurzeln modulo höheren Potenzen von <math>p</math> ist, dass eine Primitivwurzel <math>\gamma</math> modulo <math>p^2</math> (mit <math>2\leq \gamma\leq p^2-1 </math>) auch Primitivwurzel zu allen höheren Potenzen von <math>p</math> ist.<ref name="Leutbecher">A. Leutbecher: ''Zahlentheorie – Eine Einführung in die Algebra.'' S. 53–54.</ref>
Daher genügt es für höhere Potenzen der Primzahl <math>p</math>,

:* eine Primitivwurzel <math>\gamma_1</math> modulo <math>p</math> zu finden (unter den Zahlen <math>2,3,\ldots,p-1</math>),

:* die Zahlen <math>\gamma_1 + k\cdot p,\; (0\leq k \leq p-1)</math> daraufhin zu testen, ob sie Primitivwurzeln modulo <math>p^2</math> sind. Notwendig und bereits hinreichend dafür ist, dass <math>(\gamma_1 + k\cdot p)^{p-1} \not\equiv 1 (\text{mod } p^2)</math> ist. Tatsächlich tritt dies bereits für <math>k=0</math> oder <math>k=1</math> ein, d. h. <math>\gamma_1</math> oder <math>\gamma_1 +p</math> ist eine Primitivwurzel modulo <math>p^2</math>.<ref name="Leutbecher" />

Dann hat man mit jeder im zweiten Schritt bestimmten Zahl <math>\gamma_2</math> eine Primitivwurzel modulo <math>p^\alpha</math> für beliebige <math>\alpha \in \N</math>.

Ist die so bestimmte Primitivwurzel <math>\gamma_2</math> ungerade, dann ist sie auch Primitivwurzel modulo <math>2\cdot p^\alpha</math>, sonst gilt dies für <math>\gamma_2+p^\alpha</math>.

== Anwendungsbeispiel ==
Primitivwurzeln finden eine Anwendung im [[Diffie-Hellman-Schlüsselaustausch]], einem 1976 veröffentlichten [[Kryptografie|kryptografischen Verfahren]] zum öffentlichen Schlüsselaustausch. Dessen Sicherheit beruht auf der Tatsache, dass
* es einfach ist, zu einer gegebenen Primzahl <math>p</math>, Primitivwurzel <math>g</math> und ganzen Zahl <math>a</math> ein <math>A</math> auszurechnen mit <math>A \equiv g^a (\text{mod } p)</math>,
es aber
* aufwendig ist, für ein bekanntes <math> A </math> ein entsprechendes <math>a</math> (den sogenannten ''[[Diskreter Logarithmus|diskreten Logarithmus]]'') zu finden.

== Weblinks ==
* [http://services.informatik.hs-mannheim.de/KryptoLern/primitive_wurzel.php 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ß]]: ''[http://resolver.sub.uni-goettingen.de/purl?PPN373456743 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 ==
<references />

[[Kategorie:Zahlentheorie]]

Primitivwurzel - Versionsgeschichte

imported>DJGrandfather: Beispiel etwas erweitert