Primitive Wurzel

Primitive Wurzel

Als Primitivwurzeln werden in der Zahlentheorie, einem Teilgebiet der Mathematik bestimmte Elemente von primen Restklassengruppen bezeichnet. Die besondere Eigenschaft einer Primitivwurzel ist, dass jedes Element der primen Restklassengruppe als Potenz der Primitivwurzel dargestellt werden kann.

Inhaltsverzeichnis

Beispiel

Die Zahl 3 ist eine Primitivwurzel modulo 7, da gilt

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
3^6 \equiv 1\ \pmod 7

Es lassen sich also alle Elemente 1, 2, \ldots , 6 der primen Restklassengruppe modulo 7 als Potenzen von 3 darstellen. Die Zahl 2 ist keine Primitivwurzel modulo 7, da 2^3 =8 \equiv 1\ \pmod 7 ist, daher wiederholen sich die Reste in der Folge der Potenzen von 2 modulo 7

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

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 a ist eine Primitivwurzel modulo m, wenn die Restklasse a + m\mathbb{Z} die prime Restklassengruppe ( \mathbb{Z} /m\mathbb{Z} )^\times erzeugt. Dies ist gleichbedeutend damit, dass eine ganze Zahl a genau dann eine Primitivwurzel modulo m ist, wenn die Ordnung von a modulo m gleich der Gruppenordnung der primen Restklassengruppe ist:

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

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

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

m \in \{1, 2, 4, p^\alpha, 2p^\alpha | p \in \mathbb{P}\setminus\{2\};\; \alpha \in \mathbb{N}\}

gilt. Dabei bezeichnet \mathbb{P}\setminus\{2\} die Menge der ungeraden Primzahlen.[1]


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.

Berechnung von Primitivwurzeln

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

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

Eine Zahl, die keine Primitivwurzel modulo 7 ist, ist die 4. Hier gilt

4^1 \equiv 4\ \pmod 7
4^2 \equiv 2\ \pmod 7
4^3 \equiv 1\ \pmod 7

Die Ordnung von 4 ist deshalb 3 und die 4 keine Primitivwurzel modulo 7.


Primitivwurzeln modulo Primzahlen

Die primen Restklassengruppen zu Modulen m, die Primzahlen sind, bestehen aus genau m − 1 Elementen. Die Zahlen 1, 2, \ldots, m - 1 sind die Repräsentanten der unterschiedlichen Restklassen. Ist a eine Primitivwurzel modulo m, so nimmt der Ausdruck atmod m für t \in \{0, 1, 2, \ldots, m-2\} alle Werte aus \{1,\ldots,m-1\} (in scheinbar zufälliger Reihenfolge) an.

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

Primitivwurzeln modulo Primzahlpotenzen

Ist p eine ungerade Primzahl dann ist eine Primitivwurzel modulo p^{\alpha};\,\alpha >1 auch Primitivwurzel modulo kleineren Potenzen von p. Interessant für die Suche nach Primtivwurzeln modulo höheren Potenzen von p ist, dass eine Primitivwurzel γ modulo p2 (mit 1\leq \gamma\leq p^2-1 ) auch Primitivwurzel zu allen höheren Potenzen von p ist.[1]. Daher genügt es für höhere Potenzen der Primzahl,

  • eine Primitivwurzel γ1 modulo p zu finden (unter den Zahlen 2,3,\ldots,p-1),
  • die Zahlen \gamma_1 + k\cdot p,\; (0\leq k \leq p-1 ) daraufhin zu testen, ob sie Primtivwurzeln modulo p2 sind - notwendig und bereits hinreichend dafür ist, dass (\gamma_1 + k\cdot p)^{p-1} \not\equiv 1 \mod p^2 ist. Tatsächlich tritt dies bereits für k = 0 oder k = 1 ein, d. h. γ1 oder γ1 + p ist eine Primitivwurzel modulo p2.[1]

Dann hat man mit jeder im zweiten Schritt bestimmten Zahl γ2 eine Primitivwurzel modulo pα für beliebige \alpha\geq 1.

Ist die so bestimmte Primitivwurzel γ2 ungerade, dann ist sie auch Primitivwurzel modulo 2\cdot p^\alpha, sonst gilt dies für γ2 + pα.

Anwendungsbeispiel

Primitivwurzeln finden eine Anwendung im Diffie-Hellman-Schlüsselaustausch, einem 1976 veröffentlichten kryptografischen Verfahren zum öffentlichen Schlüsselaustausch. Dessen Sicherheit beruht auf der Tatsache, dass

  • es einfach ist, zu einer gegebenen Primzahl m, Primitivwurzel a und ganzen Zahl i ein b auszurechnen mit b = aimod m,

es aber

  • aufwendig ist, für ein bekanntes b ein entsprechendes i (den sogenannten diskreten Logarithmus) zu finden.

Literatur

Die Disquisitiones Arithmeticae wurden von Carl Friedrich Gauß auf Lateinisch veröffentlicht. Die zeitgenössische deutsche Übersetzung umfasst alle seine Schriften zur Zahlentheorie:

  • 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. a b c A. Leutbecher: Zahlentheorie - Eine Einführung in die Algebra, S. 53-54.

Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Diskrete Fourier-Transformation — Die Diskrete Fourier Transformation oder DFT ist eine Transformation aus dem Bereich der Fourier Analysis. Sie bildet ein zeitdiskretes, endliches Signal, welches periodisch fortgesetzt wird, auf ein diskretes, periodisches Frequenzspektrum ab,… …   Deutsch Wikipedia

  • Diskrete Fouriertransformation — Die Diskrete Fourier Transformation oder DFT ist die Fourier Transformation eines zeitdiskreten periodischen Signals. Dabei wird das periodische Signal als Superposition eines Gleichanteils, einer Grundschwingung und ihrer Oberschwingungen in ein …   Deutsch Wikipedia

  • Emil Artin — (* 3. März 1898 in Wien; † 20. Dezember 1962 in Hamburg) war ein österreichischer Mathematiker und einer der führenden Algebraiker des 20. Jahrhunderts. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Heath-Brown — David Rodney „Roger“ Heath Brown (* 1952 ) ist ein britischer Mathematiker, der sich mit analytischer Zahlentheorie beschäftigt. Leben und Wirken Heath Brown studierte am Trinity College der University of Cambridge, wo er 1979 bei Alan Baker… …   Deutsch Wikipedia

  • Roger Heath-Brown — David Rodney „Roger“ Heath Brown (* 1952 ) ist ein britischer Mathematiker, der sich mit analytischer Zahlentheorie beschäftigt. Roger Heath Brown (links), Oberwolfach 1986 Leben und Wirken Heath Brown studierte am Trinity College der University… …   Deutsch Wikipedia

  • Pythagoreisches Tripel — Pythagoreische Tripel im kartesischen Koordinatensystem mit x und y von 1 bis 2500. Die deutlich dunklen Linien markieren Tripel der Form (3n)² + (4n)² = (5n)²; weitere Regelmäßigkeiten werden in der Vergrößerung sichtbar. Die …   Deutsch Wikipedia

  • Zahn — Fossiler wurzelloser Zahn eines Hais. Länge 4 cm …   Deutsch Wikipedia

  • Zähne — Beißer (umgangssprachlich); Gebiss; Kauleiste (umgangssprachlich) * * * Zähne,   Dẹntes, in der Mundhöhle der meisten Wirbeltiere vorhandene, modifizierte Teile des Hautskeletts, die in ihrer Gesamtheit das Gebiss bilden. Zähne fehlen bei… …   Universal-Lexikon

  • Evolution: Pflanzen erobern das Festland —   Vor 400 Millionen Jahren, an der Wende vom Silur zum Devon, veränderte sich das Leben auf der Erde grundlegend. Höhere Organismen besiedelten die bis dahin lebensfeindlichen Kontinente. Als erste erschienen die »Ur Landpflanzen«, die aufgrund… …   Universal-Lexikon

  • Totem und Tabu — Original Broschur des Erstdrucks 1913 Totem und Tabu mit dem Untertitel: Einige Übereinstimmungen im Seelenleben der Wilden und der Neurotiker ist ein Buch Sigmund Freuds aus dem Jahr 1913. Es besteht aus vier Aufsätzen, die in den Jahren 1912… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”