Primitivwurzel (suchen und bestimmen)

13.07.2013, 21:36

Matheversteher

Primitivwurzel (suchen und bestimmen)

Hallo alle zusammen Wink

ich habe folgendes Problem:
Ich möchte gerne Primitivwurzeln von Restklassen mod m suchen.

Was ich weis:
1.) Also ich weis, dass ich die Anzahl der Primitivwurzeln, mit $\begin{eqnarray*} \phi(\phi(m)) \end{eqnarray*}$ berechnen kann. $\begin{eqnarray*} \phi(m) \end{eqnarray*}$ ist die Eulersche-Phi-Funktion. Außerdem, habe ich eine Primitivwurzel gefunden, so kann ich die fehlenden Primitivwurzeln mit dieser darstellen.

Bsp: a=b mod 5
$\begin{eqnarray*} \phi(\phi(5))=\phi(4)=2 \end{eqnarray*}$ --> es gibt 2 Primitivwurzeln für mod 5. Nun suche ich die Zahlen, $\begin{eqnarray*} 1\leq n <4 \end{eqnarray*}$ mit $\begin{eqnarray*} ggT(n,4) =1= \{1,3\} \end{eqnarray*}$

Nun suche ich die erste Primitwurzel:
$\begin{eqnarray*} 2^1\equiv 2 \mod 5 \end{eqnarray*}$
$\begin{eqnarray*} 2^2\equiv 4 \mod 5 \end{eqnarray*}$
$\begin{eqnarray*} 2^3\equiv 3 \mod 5 \end{eqnarray*}$
$\begin{eqnarray*} 2^4\equiv 1 \mod 5 \end{eqnarray*}$

Durch einsetzen, finde ich die erste Primitivwurzel 2.

Nun kann ich mit der 2 die anderen Primitivwurzeln finden, in dem ich nach und nach 2 mit den Zahlen aus der Menge $\begin{eqnarray*} ggT(n,4) =1= \{1,3\} \end{eqnarray*}$ potenziere.

$\begin{eqnarray*} 2^1\equiv 2 \mod 5 \end{eqnarray*}$ (bereits bekannt)
$\begin{eqnarray*} 2^3\equiv 3 \mod 5 \end{eqnarray*}$ 3 ist eine weitere Primitivwurzel.

2.) Weiter weis ich, dass es in Restklassen mod m, genau dann Primitivwurzeln gibt, wenn $\begin{eqnarray*} m \in \{2,4,p^z,2p^z\} \end{eqnarray*}$ mit $\begin{eqnarray*} z \in \mathbb Z, p \in \mathbb P_{>2} \end{eqnarray*}$

Unter Umständen dauert das Verfahren aber trotzdem noch lang, etwa wenn ich die Primitivwurzeln mod 29 bestimmen möchte.

$\begin{eqnarray*} \phi(\phi(29))=12 \end{eqnarray*}$ Das heißt es gibt 12 Primitivwurzeln,denn 28 hat die zu sich primen Teiler (1,3,5,9,11,13,15,17,19,23,25,27).

Deshalb lautet meine Frage, wie kann ich die Primitivwurzeln schneller berechnen? Ich habe zum einen dieses Verfahren gefunden, was ich aber nicht ganz verstehe (hier wird 28 in seine Primfaktoren zerlegt) und ich habe gelesen, dass es über die Ordnung einer Restklasse funktioniert.

Ich hoffe mir kann das jemand erklären. smile

13.07.2013, 22:15

watcher

Auf diesen Beitrag antworten »

Hallo,

bei 1) keine Widersprüche.
Bei

Zitat:

2.) Weiter weis ich, dass es in Restklassen mod m, genau dann Primitivwurzeln gibt, wenn $\begin{eqnarray*} m \in \{2,4,p^z,2p^z\} \end{eqnarray*}$ mit $\begin{eqnarray*} z \in \mathbb Z, p \in \mathbb P_{>2} \end{eqnarray*}$

würd ich gern ein $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ statt des $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ kaufen.

Zum Finden der Primitivwurzeln hab ich leider schlechte Nachrichten, es gibt keinen sinnvollen Algorithmus außer Brute-Force (d.h. durchprobieren).
Man nimmt ein Element x und schaut ob es maximale Ordnung, also $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ , hat.
Dank Lagrange genügt es dann zu zeigen, dass $\begin{eqnarray*} ord(x) \end{eqnarray*}$ kein echter Teiler von $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ ist. (Es gilt ja $\begin{eqnarray*} ord(x)|\varphi(n) \end{eqnarray*}$ .)
Das ist was der Algorithmus dort macht.

18.07.2013, 12:48

Matheversteher

Auf diesen Beitrag antworten »

Hey watcher smile

ist jetzt schon einige Zeit her, dass ich die Frage gestellt habe, dan weiß ich bescheid.

Vielen Dank für deine Hilfe smile

Neue Frage »

Antworten »

Primitivwurzel (suchen und bestimmen)

Verwandte Themen