Primitivwurzel

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Die Primitivwurzel ist ein Begriff aus dem mathematischen Teilgebiet Zahlentheorie. Eine Primitivwurzel zeichnet sich dadurch aus, dass jedes Element eines primen Restesystems als Potenz dieser Primitivwurzel dargestellt werden kann. Beispielsweise ist die 3 eine Primitivwurzel modulo 7, da gilt

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

$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$

Es lassen sich also alle Elemente $1, 2, \ldots , 6$ der primen Restklassengruppe modulo 7 als Potenzen von 3 darstellen.

[Bearbeiten] Die genaue mathematische Definition

In der Zahlentheorie heißt eine ganze Zahl $a$ Primitivwurzel modulo $m$ , wenn die Restklasse $a + m\mathbb{Z}$ die prime Restklassengruppe $( \mathbb{Z} /m\mathbb{Z} )^\times$ erzeugt. Dies bedeutet anders ausgedrückt, dass eine Zahl $a \in \mathbb{N}$ genau dann eine Primitivwurzel modulo $m$ ist, wenn gilt

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

Hierbei ist $\varphi$ die Eulersche φ-Funktion und $\operatorname{ord}_m(a)$ die multiplikative Ordnung modulo m.

Ist $a$ speziell eine Primitivwurzel einer Primzahl $m$ , so bedeutet das, dass der Ausdruck $a t mod m$ für $0 \le t \le m-2$ alle Werte aus $\{1,\ldots,m-1\}$ (in scheinbar zufälliger Reihenfolge) annimmt (für die Schreibweise "mod" siehe Modulo (Rest)).

Wenn modulo $m$ Primitivwurzeln existieren, dann existieren genau $\varphi(\varphi(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.

[Bearbeiten] Beispiel

Sei zum Beispiel $m = 7$ eine Primzahl. Dann ist $( \mathbb{Z} /7\mathbb{Z} )^\times=\left\{1,2,3,4,5,6\right\}$ und $\varphi(7)=6$ . Die Wertetabelle der diskreten Exponentiation der Zahlen $3$ und $4$ ist dann:

$j$	1	2	3	4	5	6
$3 j mod 7$	3	2	6	4	5	1
$4 j mod 7$	4	2	1	4	2	1

Es ist also $\operatorname{ord}_7(3)=6$ und $\operatorname{ord}_7(4)=3$ . Damit ist $3$ eine Primitivwurzel modulo $7$ , $4$ hingegen nicht. In der Notation der Erzeuger ausgedrückt ist $\langle3\rangle = \left\{3, 2, 6, 4, 5, 1\right\} = ( \mathbb{Z} /7\mathbb{Z} )^\times$ und $\langle4\rangle = \left\{4, 2, 1\right\} \neq ( \mathbb{Z} /7\mathbb{Z} )^\times$ .

Die folgende Tabelle zeigt die Primitivwurzeln 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

[Bearbeiten] Existenz von Primitivwurzeln

Nach einem Satz von C. F. Gauß existieren genau dann Primitivwurzeln modulo $m$ , wenn $m$ gleich $1,2,4, p α,2 p α$ mit einer ungeraden Primzahl $p$ und einer natürlichen Zahl $α$ ist.

[Bearbeiten] Anwendungsbeispiel

Die Primitivwurzeln fanden eine Anwendung im Diffie-Hellman-Schlüsselaustausch, einem 1976 veröffentlichten Verfahren der Kryptografie zum öffentlichen Schlüsselaustausch.

Es beruht auf der Tatsache, dass

es einfach ist, zu einer gegebenen Primzahl $m$ , Primitivwurzel $a$ und ganzer Zahl $i$ ein $b$ auszurechnen mit $b = a i mod m$ , aber
es aufwendig ist, für ein bekanntes $b$ ein entsprechendes $i$ zu finden.