www.wikidata.de-de.nina.az

Primitivwurzel Als n werden in der Zahlentheorie einem Teilgebiet der Mathematik bestimmte Elemente von primen Restklass

Primitivwurzel

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

Beispiel Bearbeiten

Die Zahl 3 ist eine Primitivwurzel modulo 7, da gilt

Es lassen sich also alle Elemente der primen Restklassengruppe modulo 7 als Potenzen von 3 darstellen, wobei der Exponent der dem jeweiligen Element zugeordnete Index (diskreter Logarithmus) ist. Die Zahl 2 ist keine Primitivwurzel modulo 7, da ist, daher wiederholen sich die Reste in der Folge der Potenzen von 2 modulo 7

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 Bearbeiten

Eine ganze Zahl ist eine Primitivwurzel modulo , wenn die Restklasse die prime Restklassengruppe erzeugt. Dies ist gleichbedeutend damit, dass eine ganze Zahl genau dann eine Primitivwurzel modulo ist, wenn die Ordnung von modulo gleich der Gruppenordnung der primen Restklassengruppe ist:

Hierbei ist die Eulersche φ-Funktion und die multiplikative Ordnung modulo m des Elements , d. h. der kleinste positive Exponent , für welchen ist (für die Schreibweise „mod“ siehe Modulo).

Genau dann ist übrigens auch

wobei die Carmichael-Funktion ist.

Es gibt genau dann Primitivwurzeln modulo , wenn die prime Restklassengruppe eine zyklische Gruppe ist. Dies ist nach einem Satz von C. F. Gauß genau dann der Fall, wenn für den Modul

gilt. Dabei bezeichnet die Menge der Primzahlen.

Wenn modulo Primitivwurzeln existieren, dann existieren genau modulo inkongruente Primitivwurzeln. Jede dieser Primitivwurzeln ist modulo kongruent zu einem Element der Menge:

wobei eine beliebige Primitivwurzel modulo ist.

Berechnung von Primitivwurzeln Bearbeiten

Ausprobieren (Brute force) Bearbeiten

Um festzustellen, ob eine Zahl Primitivwurzel modulo ist, wird zuerst und anschließend die Ordnung von berechnet. Die Ordnung lässt sich beispielsweise bestimmen, indem nacheinander die Werte für berechnet werden. Das erste , für das gilt, ist die Ordnung von .

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

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

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 teilt, da jede Zahl , für die gilt, durch die Ordnung teilbar ist. Darum muss man nur noch für alle Teiler von überprüfen, ob Exponentiation mit ihnen die Zahl auf 1 abbildet, und der kleinste solche Teiler ist die Ordnung.

Primitivwurzeln modulo Primzahlen Bearbeiten

Die primen Restklassengruppen zu Moduln , die Primzahlen sind, bestehen aus genau Elementen. Die Zahlen sind die Repräsentanten der unterschiedlichen Restklassen. Ist eine Primitivwurzel modulo , so nimmt der Ausdruck für alle Werte aus (in scheinbar zufälliger Reihenfolge) an.

Beispiele Bearbeiten

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

Primitivwurzeln modulo
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 Bearbeiten

Ist eine ungerade Primzahl, dann ist eine Primitivwurzel modulo mit auch Primitivwurzel modulo kleineren Potenzen von . Interessant für die Suche nach Primitivwurzeln modulo höheren Potenzen von ist, dass eine Primitivwurzel modulo (mit ) auch Primitivwurzel zu allen höheren Potenzen von ist. Daher genügt es für höhere Potenzen der Primzahl ,

Dann hat man mit jeder im zweiten Schritt bestimmten Zahl eine Primitivwurzel modulo für beliebige .

Ist die so bestimmte Primitivwurzel ungerade, dann ist sie auch Primitivwurzel modulo , sonst gilt dies für .

Anwendungsbeispiel Bearbeiten

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 , Primitivwurzel und ganzen Zahl ein auszurechnen mit ,

es aber

Weblinks Bearbeiten

Literatur Bearbeiten

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ß: 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 Bearbeiten

  1. Letztere liegt generell noch näher an der Elementordnung, denn es gilt für alle
  2. ↑ A. Leutbecher: Zahlentheorie – Eine Einführung in die Algebra. S. 53–54.
  3. Carl Friedrich Gauss: Untersuchungen über höhere Arithmetik. H. Maser, 1889, S. Art. 92, abgerufen am 30. Januar 2017.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Als Primitivwurzeln werden in der Zahlentheorie einem Teilgebiet der Mathematik bestimmte Elemente von primen Restklassengruppen bezeichnet Die definierende Eigenschaft einer Primitivwurzel ist dass jedes Element der primen Restklassengruppe als eine ihrer Potenzen dargestellt werden kann Inhaltsverzeichnis 1 Beispiel 2 Definition und Existenzbedingungen 3 Berechnung von Primitivwurzeln 3 1 Ausprobieren Brute force 3 2 Primitivwurzeln modulo Primzahlen 3 2 1 Beispiele 3 3 Primitivwurzeln modulo Primzahlpotenzen 4 Anwendungsbeispiel 5 Weblinks 6 Literatur 7 EinzelnachweiseBeispiel BearbeitenDie Zahl 3 ist eine Primitivwurzel modulo 7 da gilt 3 1 3 0 3 1 3 3 3 mod 7 3 2 3 1 3 3 3 9 2 mod 7 3 3 3 2 3 2 3 6 6 mod 7 3 4 3 3 3 6 3 18 4 mod 7 3 5 3 4 3 4 3 12 5 mod 7 3 6 3 5 3 5 3 15 1 mod 7 displaystyle begin array rcrcrcrcrcr 3 1 amp amp 3 0 cdot 3 amp equiv amp 1 cdot 3 amp amp 3 amp equiv amp 3 pmod 7 3 2 amp amp 3 1 cdot 3 amp equiv amp 3 cdot 3 amp amp 9 amp equiv amp 2 pmod 7 3 3 amp amp 3 2 cdot 3 amp equiv amp 2 cdot 3 amp amp 6 amp equiv amp 6 pmod 7 3 4 amp amp 3 3 cdot 3 amp equiv amp 6 cdot 3 amp amp 18 amp equiv amp 4 pmod 7 3 5 amp amp 3 4 cdot 3 amp equiv amp 4 cdot 3 amp amp 12 amp equiv amp 5 pmod 7 3 6 amp amp 3 5 cdot 3 amp equiv amp 5 cdot 3 amp amp 15 amp equiv amp 1 pmod 7 end array nbsp Es lassen sich also alle Elemente 1 2 6 displaystyle 1 2 ldots 6 nbsp der primen Restklassengruppe modulo 7 als Potenzen 3 i displaystyle 3 i nbsp von 3 darstellen wobei der Exponent i displaystyle i nbsp der dem jeweiligen Element zugeordnete Index diskreter Logarithmus ist Die Zahl 2 ist keine Primitivwurzel modulo 7 da 2 3 8 1 mod 7 displaystyle 2 3 8 equiv 1 text mod 7 nbsp ist daher wiederholen sich die Reste in der Folge der Potenzen von 2 modulo 7 2 k k N 2 1 1 2 2 1 2 3 1 2 4 2 2 5 2 2 displaystyle 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 nbsp 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 BearbeitenEine ganze Zahl a displaystyle a nbsp ist eine Primitivwurzel modulo m displaystyle m nbsp wenn die Restklasse a m Z displaystyle a m mathbb Z nbsp die prime Restklassengruppe Z m Z displaystyle mathbb Z m mathbb Z times nbsp erzeugt Dies ist gleichbedeutend damit dass eine ganze Zahl a displaystyle a nbsp genau dann eine Primitivwurzel modulo m displaystyle m nbsp ist wenn die Ordnung von a displaystyle a nbsp modulo m displaystyle m nbsp gleich der Gruppenordnung der primen Restklassengruppe ist ord m a f m displaystyle operatorname ord m a varphi m nbsp Hierbei ist f displaystyle varphi nbsp die Eulersche f Funktion und ord m a displaystyle operatorname ord m a nbsp die multiplikative Ordnung modulo m des Elements a displaystyle a nbsp d h der kleinste positive Exponent n displaystyle n nbsp fur welchen a n 1 mod m displaystyle a n equiv 1 text mod m nbsp ist fur die Schreibweise mod siehe Modulo Genau dann ist ubrigens auch ord m a l m displaystyle operatorname ord m a lambda m nbsp wobei l displaystyle lambda nbsp die Carmichael Funktion ist 1 Es gibt genau dann Primitivwurzeln modulo m displaystyle m nbsp wenn die prime Restklassengruppe Z m Z displaystyle mathbb Z m mathbb Z times nbsp eine zyklische Gruppe ist Dies ist nach einem Satz von C F Gauss genau dann der Fall wenn fur den Modul m 2 4 k p a 2 lt p P a N k 1 2 displaystyle m in 2 4 cup kp alpha mid 2 lt p in mathbb P alpha in mathbb N k in 1 2 nbsp gilt Dabei bezeichnet P displaystyle mathbb P nbsp die Menge der Primzahlen 2 3 Wenn modulo m displaystyle m nbsp Primitivwurzeln existieren dann existieren genau f f m displaystyle varphi varphi m nbsp modulo m displaystyle m nbsp inkongruente Primitivwurzeln Jede dieser Primitivwurzeln ist modulo m displaystyle m nbsp kongruent zu einem Element der Menge a n 1 n f m ggT n f m 1 displaystyle a n mid 1 leq n leq varphi m operatorname ggT n varphi m 1 nbsp wobei a displaystyle a nbsp eine beliebige Primitivwurzel modulo m displaystyle m nbsp ist Berechnung von Primitivwurzeln BearbeitenAusprobieren Brute force Bearbeiten Um festzustellen ob eine Zahl a displaystyle a nbsp Primitivwurzel modulo m displaystyle m nbsp ist wird zuerst f m displaystyle varphi m nbsp und anschliessend die Ordnung von a displaystyle a nbsp berechnet Die Ordnung lasst sich beispielsweise bestimmen indem nacheinander die Werte a t mod m displaystyle a t text mod m nbsp fur t 1 2 m 1 displaystyle t in 1 2 ldots m 1 nbsp berechnet werden Das erste t displaystyle t nbsp fur das a t mod m 1 displaystyle a t text mod m 1 nbsp gilt ist die Ordnung von a displaystyle a nbsp Beim Beispiel aus der Einleitung sieht man dass die 3 die Ordnung 6 hat Da zudem f 7 6 displaystyle varphi 7 6 nbsp gilt ist 3 eine Primitivwurzel modulo 7 Eine Zahl die keine Primitivwurzel modulo 7 ist ist die 4 Hier gilt 4 1 4 mod 7 displaystyle 4 1 equiv 4 pmod 7 nbsp 4 2 2 mod 7 displaystyle 4 2 equiv 2 pmod 7 nbsp 4 3 1 mod 7 displaystyle 4 3 equiv 1 pmod 7 nbsp 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 f m displaystyle varphi m nbsp teilt da jede Zahl k N displaystyle k in mathbb N nbsp fur die a k 1 mod m displaystyle a k equiv 1 text mod m nbsp gilt durch die Ordnung teilbar ist Darum muss man nur noch fur alle Teiler von f m displaystyle varphi m nbsp uberprufen ob Exponentiation mit ihnen die Zahl auf 1 abbildet und der kleinste solche Teiler ist die Ordnung Primitivwurzeln modulo Primzahlen Bearbeiten Die primen Restklassengruppen zu Moduln m displaystyle m nbsp die Primzahlen sind bestehen aus genau m 1 displaystyle m 1 nbsp Elementen Die Zahlen 1 2 m 1 displaystyle 1 2 ldots m 1 nbsp sind die Reprasentanten der unterschiedlichen Restklassen Ist a displaystyle a nbsp eine Primitivwurzel modulo m displaystyle m nbsp so nimmt der Ausdruck a t mod m displaystyle a t text mod m nbsp fur t 0 1 2 m 2 displaystyle t in 0 1 2 ldots m 2 nbsp alle Werte aus 1 m 1 displaystyle 1 ldots m 1 nbsp in scheinbar zufalliger Reihenfolge an Beispiele Bearbeiten Die folgende Tabelle zeigt die Primitivwurzeln modulo der Primzahlen bis 100 m displaystyle m nbsp f f m displaystyle varphi varphi m nbsp Primitivwurzeln modulo m displaystyle m nbsp 2 1 13 1 25 2 2 37 2 3 511 4 2 6 7 813 4 2 6 7 1117 8 3 5 6 7 10 11 12 1419 6 2 3 10 13 14 1523 10 5 7 10 11 14 15 17 19 20 2129 12 2 3 8 10 11 14 15 18 19 21 26 2731 8 3 11 12 13 17 21 22 2437 12 2 5 13 15 17 18 19 20 22 24 32 3541 16 6 7 11 12 13 15 17 19 22 24 26 28 29 30 34 3543 12 3 5 12 18 19 20 26 28 29 30 33 3447 22 5 10 11 13 15 19 20 22 23 26 29 30 31 33 35 38 39 40 41 43 44 4553 24 2 3 5 8 12 14 18 19 20 21 22 26 27 31 32 33 34 35 39 41 45 48 50 5159 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 5661 16 2 6 7 10 17 18 26 30 31 35 43 44 51 54 55 5967 20 2 7 11 12 13 18 20 28 31 32 34 41 44 46 48 50 51 57 61 6371 24 7 11 13 21 22 28 31 33 35 42 44 47 52 53 55 56 59 61 62 63 65 67 68 6973 24 5 11 13 14 15 20 26 28 29 31 33 34 39 40 42 44 45 47 53 58 59 60 62 6879 24 3 6 7 28 29 30 34 35 37 39 43 47 48 53 54 59 60 63 66 68 70 74 75 7783 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 8089 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 8697 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 92Primitivwurzeln modulo Primzahlpotenzen Bearbeiten Ist p displaystyle p nbsp eine ungerade Primzahl dann ist eine Primitivwurzel modulo p a displaystyle p alpha nbsp mit a gt 1 displaystyle alpha gt 1 nbsp auch Primitivwurzel modulo kleineren Potenzen von p displaystyle p nbsp Interessant fur die Suche nach Primitivwurzeln modulo hoheren Potenzen von p displaystyle p nbsp ist dass eine Primitivwurzel g displaystyle gamma nbsp modulo p 2 displaystyle p 2 nbsp mit 2 g p 2 1 displaystyle 2 leq gamma leq p 2 1 nbsp auch Primitivwurzel zu allen hoheren Potenzen von p displaystyle p nbsp ist 2 Daher genugt es fur hohere Potenzen der Primzahl p displaystyle p nbsp eine Primitivwurzel g 1 displaystyle gamma 1 nbsp modulo p displaystyle p nbsp zu finden unter den Zahlen 2 3 p 1 displaystyle 2 3 ldots p 1 nbsp die Zahlen g 1 k p 0 k p 1 displaystyle gamma 1 k cdot p 0 leq k leq p 1 nbsp daraufhin zu testen ob sie Primitivwurzeln modulo p 2 displaystyle p 2 nbsp sind Notwendig und bereits hinreichend dafur ist dass g 1 k p p 1 1 mod p 2 displaystyle gamma 1 k cdot p p 1 not equiv 1 text mod p 2 nbsp ist Tatsachlich tritt dies bereits fur k 0 displaystyle k 0 nbsp oder k 1 displaystyle k 1 nbsp ein d h g 1 displaystyle gamma 1 nbsp oder g 1 p displaystyle gamma 1 p nbsp ist eine Primitivwurzel modulo p 2 displaystyle p 2 nbsp 2 Dann hat man mit jeder im zweiten Schritt bestimmten Zahl g 2 displaystyle gamma 2 nbsp eine Primitivwurzel modulo p a displaystyle p alpha nbsp fur beliebige a N displaystyle alpha in mathbb N nbsp Ist die so bestimmte Primitivwurzel g 2 displaystyle gamma 2 nbsp ungerade dann ist sie auch Primitivwurzel modulo 2 p a displaystyle 2 cdot p alpha nbsp sonst gilt dies fur g 2 p a displaystyle gamma 2 p alpha nbsp Anwendungsbeispiel BearbeitenPrimitivwurzeln finden eine Anwendung im Diffie Hellman Schlusselaustausch einem 1976 veroffentlichten kryptografischen Verfahren zum offentlichen Schlusselaustausch Dessen Sicherheit beruht auf der Tatsache dass es einfach ist zu einer gegebenen Primzahl p displaystyle p nbsp Primitivwurzel g displaystyle g nbsp und ganzen Zahl a displaystyle a nbsp ein A displaystyle A nbsp auszurechnen mit A g a mod p displaystyle A equiv g a text mod p nbsp es aber aufwendig ist fur ein bekanntes A displaystyle A nbsp ein entsprechendes a displaystyle a nbsp den sogenannten diskreten Logarithmus zu finden Weblinks BearbeitenBerechnung primitiver WurzelnLiteratur BearbeitenDie Disquisitiones Arithmeticae wurden von Carl Friedrich Gauss auf Lateinisch veroffentlicht Die zeitgenossische deutsche Ubersetzung umfasst alle seine Schriften zur Zahlentheorie Carl Friedrich Gauss Untersuchungen uber hohere Arithmetik deutsche Ubersetzung Original Leipzig 1801 Peter Bundschuh Einfuhrung in die Zahlentheorie 5 Auflage Springer Verlag 2002 ISBN 3 540 43579 4 S 109 120 Armin Leutbecher Zahlentheorie Eine Einfuhrung in die Algebra 1 Auflage Springer Verlag 1996 Berlin Heidelberg New York ISBN 3 540 58791 8 Einzelnachweise Bearbeiten Letztere liegt generell noch naher an der Elementordnung denn es gilt fur alle a m displaystyle a m nbsp ord m a l m f m displaystyle operatorname ord m a lambda m varphi m nbsp a b c A Leutbecher Zahlentheorie Eine Einfuhrung in die Algebra S 53 54 Carl Friedrich Gauss Untersuchungen uber hohere Arithmetik H Maser 1889 S Art 92 abgerufen am 30 Januar 2017 Abgerufen von https de wikipedia org w index php title Primitivwurzel amp oldid 237569478