Artikel

5: Primitive Wurzeln und quadratische Reste


In diesem Kapitel diskutieren wir die multiplikative Struktur der ganzen Zahlen modulo (n). Wir führen das Konzept der Ordnung ganzzahliger Modulo (n) ein und untersuchen dann seine Eigenschaften. Wir definieren dann primitive Wurzeln modulo (n) und zeigen, wie man bestimmt, ob eine ganze Zahl primitiv modulo (n) ist oder nicht. Wir finden später alle positiven ganzen Zahlen mit primitiven Wurzeln und beweisen die entsprechenden Ergebnisse. Wir definieren den Begriff eines quadratischen Restes und legen seine grundlegenden Eigenschaften fest. Wir führen dann das Legendre-Symbol ein und entwickeln auch seine grundlegenden Eigenschaften. Wir führen auch das Gesetz der quadratischen Reziprozität ein. Danach verallgemeinern wir den Begriff des Legendre-Symbols auf das Jacobi-Symbol und diskutieren das Gesetz der Reziprozität in Bezug auf das Jacobi-Symbol.

  • 5.1: Die Ordnung von ganzen Zahlen und primitiven Wurzeln
  • 5.2: Primitive Wurzeln für Primzahlen
    In diesem Abschnitt zeigen wir, dass jede ganze Zahl eine primitive Wurzel hat. Dazu müssen wir die polynomiale Kongruenz einführen.
  • 5.3: Die Existenz primitiver Wurzeln
    In diesem Abschnitt zeigen wir, welche ganzen Zahlen primitive Wurzeln haben. Wir beginnen damit, dass wir zeigen, dass jede Potenz einer ungeraden Primzahl eine primitive Wurzel hat, und dazu zeigen wir, dass jedes Quadrat einer ungeraden Primzahl eine primitive Wurzel hat.
  • 5.4: Einführung in quadratische Reste und Nichtreste
  • 5.5: Legendre-Symbol
    In diesem Abschnitt definieren wir das Legendre-Symbol, das eine mit quadratischen Resten verbundene Notation ist, und beweisen verwandte Theoreme.
  • 5.6: Das Gesetz der quadratischen Reziprozität
    Vorausgesetzt, p und q sind ungerade Primzahlen. Angenommen, wir wissen, ob q ein quadratischer Rest von p ist oder nicht. Die Frage, die dieser Abschnitt beantworten wird, ist, ob p ein quadratischer Rest von q ist oder nicht. Bevor wir das Gesetz der quadratischen Reziprozität angeben, werden wir ein Lemma von Eisenstein präsentieren, das beim Beweis des Reziprozitätsgesetzes verwendet wird. Das folgende Lemma verbindet das Legendre-Symbol mit den zählenden Gitterpunkten im Dreieck.
  • 5.7: Jacobi-Symbol
    In diesem Abschnitt definieren wir das Jacobi-Symbol, das eine Verallgemeinerung des Legendre-Symbols ist. Das Legendre-Symbol wurde in Form von Primzahlen definiert, während das Jacobi-Symbol für alle ungeraden ganzen Zahlen verallgemeinert und als Legendre-Symbol angegeben wird.

Summen von primitiven Wurzeln und quadratischen Resten bei $p equiv 3pmod 4$

Das sieht so chaotisch aus, also werde ich dieses wirklich interessante Thema erklären (zumindest sehr viel für mich).

Wenn $p equiv 1pmod 4$ ist, ist es wirklich einfach, die Summe aller Elemente in $R_p$ zu berechnen, die ich 'das am wenigsten positive primitive Wurzelrestsystem$pmod p . nenne

Inhalt

Die Zahl 3 ist eine primitive Wurzel modulo 7 [1] weil

Hier sehen wir, dass die Periode von 3 k modulo 7 gleich 6 ist. Die Reste in der Periode, die 3, 2, 6, 4, 5, 1 sind, bilden eine Umordnung aller von Null verschiedenen Reste modulo 7, was bedeutet, dass 3 tatsächlich a . ist Primitivwurzel modulo 7. Dies ergibt sich aus der Tatsache, dass sich eine Folge ( gk modulo n ) immer nach einem Wert von k wiederholt, da Modulo n eine endliche Anzahl von Werten erzeugt. Wenn g eine Primitivwurzel modulo n und n eine Primzahl ist, dann ist die Wiederholungsperiode n − 1 . Seltsamerweise hat sich gezeigt, dass auf diese Weise erzeugte Permutationen (und ihre kreisförmigen Verschiebungen) Costas-Arrays sind.

Wenn n eine positive ganze Zahl ist, bilden die ganzen Zahlen zwischen 0 und n − 1, die zu n teilerfremd sind (oder äquivalent, die Kongruenzklassen teilerfremd zu n ), eine Gruppe, mit der Multiplikation modulo n als Operation wird sie mit Z > ×
n , und heißt die Gruppe der Einheiten modulo n oder die Gruppe der primitiven Klassen modulo n . Wie im Artikel multiplikative Gruppe ganzer Zahlen modulo n erklärt, ist diese multiplikative Gruppe ( Z > ×
n ) ist zyklisch dann und nur dann, wenn n ist gleich 2, 4, pk oder 2pk, wobei pk eine Potenz einer ungeraden Primzahl ist. [2] [3] [4] Wenn (und nur wenn) diese Gruppe Z > ×
n zyklisch ist, heißt ein Generator dieser zyklischen Gruppe a primitive Wurzel modulo n [5] (oder in voller Sprache primitive Einheitswurzel modulo n , betont seine Rolle als grundlegende Lösung der Wurzeln der Einheit Polynomgleichungen X m
− 1 im Ring Z > n ) oder einfach a primitives Element von Z > ×
n . Wenn Z > ×
n nicht zyklisch ist, existieren solche primitiven Elemente mod n nicht.

Für jedes n (ob Z > ×
n zyklisch ist), die Reihenfolge von (d. h. die Anzahl der Elemente in) Z > ×
n ist durch die Eulersche Totient-Funktion φ ( n ) gegeben (Sequenz A000010 im OEIS). Und dann besagt der Satz von Euler, dass a ( n ) 1 (mod n ) für jede a teilerfremde zu n die niedrigste Potenz von a, die zu 1 modulo n kongruent ist, die multiplikative Ordnung von a modulo n heißt. Damit a eine primitive Wurzel modulo n ist, muss insbesondere φ ( n ) die kleinste Potenz von a sein, die zu 1 modulo n kongruent ist.

Die Ordnung von 1 ist 1, die Ordnungen von 3 und 5 sind 6, die Ordnungen von 9 und 11 sind 3 und die Ordnung von 13 ist 2. Somit sind 3 und 5 die primitiven Wurzeln modulo 14.

Da es keine Zahl mit der Ordnung 8 gibt, gibt es keine primitiven Wurzeln modulo 15. Tatsächlich gilt λ (15) = 4 , wobei λ die Carmichael-Funktion ist. (Sequenz A002322 im OEIS)

Tabelle der primitiven Wurzeln Bearbeiten

Zahlen mit einer primitiven Wurzel sind

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29, 31, 34, 37, 38, 41, 43, 46, 47, 49, 50, 53, 54, 58, 59, 61, 62, 67, 71, 73, 74, 79, 81, 82, 83, 86, 89, 94, 97, 98, 101, 103, 106, 107, 109, 113, 118, 121, 122, 125, 127, 131, 134, 137, 139, 142, 146, 149, . (Sequenz A033948 im OEIS)

Dies ist die Gaußsche Tabelle der primitiven Wurzeln aus dem Ersuchen. Im Gegensatz zu den meisten modernen Autoren wählte er nicht immer die kleinste primitive Wurzel. Stattdessen wählte er 10, wenn es sich um eine primitive Wurzel handelt, wenn nicht, wählte er die Wurzel, die 10 den kleinsten Index ergibt, und wenn es mehr als eine gibt, wählte er die kleinste davon. Dies soll nicht nur die Handrechnung erleichtern, sondern wird in § VI verwendet, wo die periodischen Dezimalentwicklungen rationaler Zahlen untersucht werden.

Die Zeilen der Tabelle sind mit Primzahlen (mit Ausnahme von 2, 4 und 8) kleiner als 100 beschriftet. Die zweite Spalte ist eine primitive Wurzel modulo dieser Zahl. Die Spalten sind mit Primzahlen kleiner 100 beschriftet. Der Eintrag in Zeile p , Spalte q ist der Index von q modulo p für die gegebene Wurzel.

In Zeile 11 ist beispielsweise 2 als Primitivwurzel angegeben, und in Spalte 5 ist der Eintrag 4. Dies bedeutet, dass 2 4 = 16 ≡ 5 (mod 11) ist.

Für den Index einer zusammengesetzten Zahl addieren Sie die Indizes ihrer Primfaktoren.

In Zeile 11 ist beispielsweise der Index von 6 die Summe der Indizes für 2 und 3: 2 1 + 8 = 512 ≡ 6 (mod 11) . Der Index von 25 ist doppelt so groß wie der von 5: 2 8 = 256 ≡ 25 (mod 11) . (Natürlich, da 25 ≡ 3 (mod 11) ist der Eintrag für 3 8).

Die Tabelle ist für die ungeraden Primzahlen einfach. Aber die Potenzen von 2 (16, 32 und 64) haben stattdessen keine primitiven Wurzeln, die Potenzen von 5 machen die Hälfte der ungeraden Zahlen kleiner aus als die Potenz von 2, und ihre Negativen modulo der Potenz von 2 machen die andere Hälfte. Alle Potenzen von 5 sind entweder kongruent zu 5 oder 1 (modulo 8) die Spalten mit Zahlen kongruent zu 3 oder 7 (mod 8) enthalten den Index ihres Negativs. (Sequenz A185189 und A185268 in OEIS)

Modulo 32 zum Beispiel ist der Index für 7 2 und 5 2 = 25 −7 (mod 32), aber der Eintrag für 17 ist 4 und 5 4 = 625 ≡ 17 (mod 32) .

Primitive Wurzeln und Indizes
(andere Spalten sind die Indizes von ganzen Zahlen unter den jeweiligen Spaltenüberschriften)
n Wurzel 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
3 2 1
5 2 1 3
7 3 2 1 5
9 2 1 * 5 4
11 2 1 8 4 7
13 6 5 8 9 7 11
16 5 * 3 1 2 1 3
17 10 10 11 7 9 13 12
19 10 17 5 2 12 6 13 8
23 10 8 20 15 21 3 12 17 5
25 2 1 7 * 5 16 19 13 18 11
27 2 1 * 5 16 13 8 15 12 11
29 10 11 27 18 20 23 2 7 15 24
31 17 12 13 20 4 29 23 1 22 21 27
32 5 * 3 1 2 5 7 4 7 6 3 0
37 5 11 34 1 28 6 13 5 25 21 15 27
41 6 26 15 22 39 3 31 33 9 36 7 28 32
43 28 39 17 5 7 6 40 16 29 20 25 32 35 18
47 10 30 18 17 38 27 3 42 29 39 43 5 24 25 37
49 10 2 13 41 * 16 9 31 35 32 24 7 38 27 36 23
53 26 25 9 31 38 46 28 42 41 39 6 45 22 33 30 8
59 10 25 32 34 44 45 28 14 22 27 4 7 41 2 13 53 28
61 10 47 42 14 23 45 20 49 22 39 25 13 33 18 41 40 51 17
64 5 * 3 1 10 5 15 12 7 14 11 8 9 14 13 12 5 1 3
67 12 29 9 39 7 61 23 8 26 20 22 43 44 19 63 64 3 54 5
71 62 58 18 14 33 43 27 7 38 5 4 13 30 55 44 17 59 29 37 11
73 5 8 6 1 33 55 59 21 62 46 35 11 64 4 51 31 53 5 58 50 44
79 29 50 71 34 19 70 74 9 10 52 1 76 23 21 47 55 7 17 75 54 33 4
81 11 25 * 35 22 1 38 15 12 5 7 14 24 29 10 13 45 53 4 20 33 48 52
83 50 3 52 81 24 72 67 4 59 16 36 32 60 38 49 69 13 20 34 53 17 43 47
89 30 72 87 18 7 4 65 82 53 31 29 57 77 67 59 34 10 45 19 32 26 68 46 27
97 10 86 2 11 53 82 83 19 27 79 47 26 41 71 44 60 14 65 32 51 25 20 42 91 18
n Wurzel 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Die folgende Tabelle listet die Primitivwurzeln modulo n für n 72 auf:

n primitive Wurzeln modulo n Auftrag ( OEIS: A000010 ) n primitive Wurzeln modulo n Auftrag ( OEIS: A000010 )
1 0 1 37 2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35 36
2 1 1 38 3, 13, 15, 21, 29, 33 18
3 2 2 39 24
4 3 2 40 16
5 2, 3 4 41 6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35 40
6 5 2 42 12
7 3, 5 6 43 3, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 34 42
8 4 44 20
9 2, 5 6 45 24
10 3, 7 4 46 5, 7, 11, 15, 17, 19, 21, 33, 37, 43 22
11 2, 6, 7, 8 10 47 5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45 46
12 4 48 16
13 2, 6, 7, 11 12 49 3, 5, 10, 12, 17, 24, 26, 33, 38, 40, 45, 47 42
14 3, 5 6 50 3, 13, 17, 23, 27, 33, 37, 47 20
15 8 51 32
16 8 52 24
17 3, 5, 6, 7, 10, 11, 12, 14 16 53 2, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 51 52
18 5, 11 6 54 5, 11, 23, 29, 41, 47 18
19 2, 3, 10, 13, 14, 15 18 55 40
20 8 56 24
21 12 57 36
22 7, 13, 17, 19 10 58 3, 11, 15, 19, 21, 27, 31, 37, 39, 43, 47, 55 28
23 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 22 59 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 58
24 8 60 16
25 2, 3, 8, 12, 13, 17, 22, 23 20 61 2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59 60
26 7, 11, 15, 19 12 62 3, 11, 13, 17, 21, 43, 53, 55 30
27 2, 5, 11, 14, 20, 23 18 63 36
28 12 64 32
29 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27 28 65 48
30 8 66 20
31 3, 11, 12, 13, 17, 21, 22, 24 30 67 2, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63 66
32 16 68 32
33 20 69 44
34 3, 5, 7, 11, 23, 27, 29, 31 16 70 24
35 24 71 7, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 69 70
36 12 72 24

Artins Vermutung über primitive Wurzeln besagt, dass eine gegebene ganze Zahl a, die weder ein perfektes Quadrat noch −1 ist, eine primitive Wurzel modulo unendlich viele Primzahlen ist.

Die Folge der kleinsten primitiven Wurzeln modulo n (die nicht mit der Folge der primitiven Wurzeln in der Gaußschen Tabelle übereinstimmt) sind

0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, . (Sequenz A046145 im OEIS)

1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 5, 2, 6, 3, 3, 2, 3, 2, 2, 6, 5, 2, 5, 2, 2, 2, 19, 5, 2, 3, 2, 3, 2, 6, 3, 7, 7, 6, 3, 5, 2, 6, 5, 3, 3, 2, 5, 17, 10, 2, 3, 10, 2, 2, 3, 7, 6, 2, 2, . (Sequenz A001918 im OEIS)

Die größten primitiven Wurzeln modulo n sind

0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, 5, 0, 0, 14, 11, 15, 0, 0, 19, 21, 0, 23, 19, 23, 0, 27, 0, 24, 0, 0, 31, 0, 0, 35, 33, 0, 0, 35, 0, 34, 0, 0, 43, 45, 0, 47, 47, 0, 0, 51, 47, 0, 0, 0, 55, 56, 0, 59, 55, 0, 0, 0, 0, 63, 0, 0, 0, 69, 0, 68, 69, 0, . (Sequenz A046146 im OEIS)

1, 2, 3, 5, 8, 11, 14, 15, 21, 27, 24, 35, 35, 34, 45, 51, 56, 59, 63, 69, 68, 77, 80, 86, 92, 99, 101, 104, 103, 110, 118, 128, 134, 135, 147, 146, 152, 159, 165, 171, 176, 179, 189, 188, 195, 197, 207, 214, 224, 223, . (Sequenz A071894 im OEIS)

Anzahl der primitiven Wurzeln modulo n are

1, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, 2, 0, 0, 8, 2, 6, 0, 0, 4, 10, 0, 8, 4, 6, 0, 12, 0, 8, 0, 0, 8, 0, 0, 12, 6, 0, 0, 16, 0, 12, 0, 0, 10, 22, 0, 12, 8, 0, 0, 24, 6, 0, 0, 0, 12, 28, 0, 16, 8, 0, 0, 0, 0, 20, 0, 0, 0, 24, 0, 24, 12, 0, . (Sequenz A046144 im OEIS)

1, 1, 2, 2, 4, 4, 8, 6, 10, 12, 8, 12, 16, 12, 22, 24, 28, 16, 20, 24, 24, 24, 40, 40, 32, 40, 32, 52, 36, 48, 36, 48, 64, 44, 72, 40, 48, 54, 82, 84, 88, 48, 72, 64, 84, 60, 48, 72, 112, 72, 112, 96, 64, 100, 128, 130, 132, 72, 88, 96, . (Sequenz A008330 im OEIS)

Kleinste Primzahl > n mit Primitivwurzel n sind

2, 3, 5, 0, 7, 11, 11, 11, 0, 17, 13, 17, 19, 17, 19, 0, 23, 29, 23, 23, 23, 31, 47, 31, 0, 29, 29, 41, 41, 41, 47, 37, 43, 41, 37, 0, 59, 47, 47, 47, 47, 59, 47, 47, 47, 67, 59, 53, 0, 53, . (Sequenz A023049 im OEIS)

Kleinste Primzahl (nicht notwendigerweise größer als n ) mit Primitivwurzel n sind

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, 2, 3, 2, . (Sequenz A056619 im OEIS)

Arithmetische Fakten Bearbeiten

Gauss bewies [6], dass für jede Primzahl p (mit Ausnahme von p = 3 ) das Produkt ihrer primitiven Wurzeln kongruent zu 1 modulo p ist.

Er bewies auch [7], dass für jede Primzahl p die Summe ihrer primitiven Wurzeln kongruent zu μ ( p − 1) modulo p ist, wobei μ die Möbius-Funktion ist.

Beispielsweise,

p = 3, μ(2) = −1. Die primitive Wurzel ist 2. p = 5, μ (4) = 0. Die primitiven Wurzeln sind 2 und 3. p = 7, μ (6) = 1. Die primitiven Wurzeln sind 3 und 5. p = 31, μ ( 30) = −1. Die primitiven Wurzeln sind 3, 11, 12, 13, 17, 21, 22 und 24. Ihr Produkt 970377408 ≡ 1 (mod 31) und ihre Summe 123 ≡ −1 (mod 31). 3 × 11 = 33 ≡ 2 12 × 13 = 156 ≡ 1 (−14) × (−10) = 140 ≡ 16 (−9) × (−7) = 63 ≡ 1 und 2 × 1 × 16 × 1 = 32 ≡ 1 (Mod 31).

Es ist keine einfache allgemeine Formel zur Berechnung von Primitivwurzeln modulo n bekannt. [a] [b] Es gibt jedoch Methoden, um eine primitive Wurzel zu lokalisieren, die schneller sind, als einfach alle Kandidaten auszuprobieren. Wenn die multiplikative Ordnung einer Zahl m modulo n gleich φ ( n ) ist (die Ordnung von Z > ×
n ), dann ist es eine primitive Wurzel. Tatsächlich gilt das Umgekehrte: Wenn m eine primitive Wurzel modulo n ist, dann ist die multiplikative Ordnung von m φ ( n ). Damit können wir einen Kandidaten m testen, um zu sehen, ob er primitiv ist.

Verwenden eines schnellen Algorithmus für die modulare Exponentiation, wie beispielsweise die Exponentiation durch Quadrieren. Eine Zahl m, für die diese k-Ergebnisse alle von 1 verschieden sind, ist eine primitive Wurzel.

Die Anzahl der primitiven Wurzeln modulo n , falls vorhanden, ist gleich [8]

Wenn g eine primitive Wurzel modulo p ist, dann ist g auch eine primitive Wurzel modulo alle Potenzen p k, es sei denn, g p −1 1 (mod p 2 ) in diesem Fall ist g + p. [10]

Wenn g eine Primitivwurzel modulo p k ist, dann ist entweder g oder g + p k (je nachdem, was ungerade ist) eine Primitivwurzel modulo 2 p k . [10]

Das Finden primitiver Wurzeln modulo p ist auch äquivalent zum Finden der Wurzeln des ( p − 1)sten zyklotomischen Polynoms modulo p .

Die am wenigsten primitive Wurzel gP modulo p (im Bereich 1, 2, . p − 1 ) ist im Allgemeinen klein.

Obergrenzen Bearbeiten

Burgess (1962) bewies [11], dass für jeden ε > 0 gibt es ein C mit g p ≤ C p 1 4 + ϵ . leq C,p^<<4>>+epsilon >

Untere Schranken Bearbeiten

Fridlander (1949) und Salié (1950) bewiesen [11], dass es eine positive Konstante C gibt, so dass für unendlich viele Primzahlen gP > C log p .

Man kann elementar [11] beweisen, dass es für jede positive ganze Zahl M unendlich viele Primzahlen gibt mit M < gP <p - M .

Eine primitive Wurzel modulo n wird häufig in der Kryptographie verwendet, einschließlich des Diffie-Hellman-Schlüsselaustauschschemas. Schalldiffusoren basieren auf zahlentheoretischen Konzepten wie primitiven Wurzeln und quadratischen Resten. [13] [14]

  1. ^ „Eines der wichtigsten ungelösten Probleme in der Theorie endlicher Körper ist der Entwurf eines schnellen Algorithmus zur Konstruktion primitiver Wurzeln.“ von zur Gathen & Shparlinski 1998, S. 15–24
  2. ^ "Es gibt keine bequeme Formel für die Berechnung [der am wenigsten primitiven Wurzel]." Robbins 2006, S. 159
  1. ^ Stromquist, Walter. "Was sind primitive Wurzeln?". Mathematik. Bryn Mawr College. Archiviert vom Original am 2017-07-03 . Abgerufen 2017-07-03 .
  2. ^
  3. Weisstein, Eric W. "Modulo Multiplication Group". MathWorld.
  4. ^Primitive Wurzel, Enzyklopädie der Mathematik.
  5. ^Vinogradov 2003, S. 105–121, § VI Primitive Wurzeln und Indizes.
  6. ^Vinogradov 2003, S. 106.
  7. ^Gauß & Clarke 1986, Kunst. 80 harvnb-Fehler: kein Ziel: CITEREFGaussClarke1986 (Hilfe) .
  8. ^Gauss & Clarke 1986, Art 81 Harvnb-Fehler: kein Ziel: CITEREFGaussClarke1986 (Hilfe) .
  9. ^ (Sequenz A010554 im OEIS)
  10. ^
  11. Knuth, Donald E. (1998). Seminumerische Algorithmen. Die Kunst der Computerprogrammierung. 2 (3. Aufl.). Addison-Wesley. Abschnitt 4.5.4, Seite 391.
  12. ^ einB
  13. Cohen, Henri (1993). Ein Kurs in computergestützter algebraischer Zahlentheorie. Berlin: Springer. P. 26. ISBN978-3-540-55640-4 .
  14. ^ einBCD
  15. Ribenboim, Paulo (1996). Das neue Buch der Primzahlrekorde. New York, NY: Springer. P. 24. ISBN978-0-387-94457-9 .
  16. ^Bach & Shallit 1996, S. 254.
  17. ^
  18. Walker, R. (1990). Der Entwurf und die Anwendung von modularen akustischen Diffusorelementen (PDF) . BBC-Forschungsabteilung (Bericht). British Broadcasting Corporation . Abgerufen am 25. März 2019.
  19. ^
  20. Feldman, Eliot (Juli 1995). "Ein Reflexionsgitter, das die Spiegelreflexion aufhebt: Ein Kegel der Stille". J. Acoust. Soz. Bin. 98 (1): 623–634. Bibcode:1995ASAJ. 98..623F. doi:10.1121/1.413656.

Zitierfehler: Eine listendefinierte Referenz namens "Carella-2015" wird im Inhalt nicht verwendet (siehe Hilfeseite).

  • Bach, Eric Shallit, Jeffrey (1996). Effiziente Algorithmen. Algorithmische Zahlentheorie. ich. Cambridge, MA: Die MIT-Presse. ISBN978-0-262-02405-1 .
  • Carella, N.A. (2015). "Least Prime Primitive Roots". Internationale Zeitschrift für Mathematik und Informatik. 10 (2): 185–194. arXiv: 1709.01172 .

Das Disquisitiones Arithmeticae wurde aus dem Ciceronischen Latein von Gauß ins Englische und Deutsche übersetzt. Die deutsche Ausgabe enthält alle seine Aufsätze zur Zahlentheorie: alle Beweise der quadratischen Reziprozität, die Vorzeichenbestimmung der Gaußsumme, die Untersuchungen zur biquadratischen Reziprozität und unveröffentlichte Notizen.


2 Antworten 2

Möglicherweise kennen Sie das Ergebnis, das besagt, dass $n$, wenn $n$ eine primitive Wurzel hat, $varphi(varphi(n))$ primitive Wurzeln hat.

Im Fall $q=2p+1$ ist die Anzahl der primitiven Wurzeln von $q$ daher $varphi(2p)$, also $p-1$. Aber $p-1=frac<2>-1$. Da es $frac<2>$ quadratische Nicht-Reste von $q$ und jede primitive Wurzel eine Nicht-Reste ist, folgt daraus, dass alle Nicht-Reste bis auf einen eine primitive Wurzel sind.

Da $q$ die Form $4k+3$ hat, wissen wir, dass $-1$ ein Nicht-Rest ist. Aber $-1$ ist keine primitive Wurzel von $q$, da $qgt 3$. $-1$ ist also der einzige Nicht-Rest, der keine primitive Wurzel ist.


5: Primitive Wurzeln und quadratische Reste

YALE UNIVERSITÄT
ABTEILUNG FÜR COMPUTERWISSENSCHAFTEN

CPSC 467a: Kryptographie und Computersicherheit Anmerkungen 15  (Rev. ਂ)
Professor M. J. Fischer 29. Oktober 2008

61 Quadratische Reste, Quadrate und Quadratwurzeln

Eine ganze Zahl a heißt quadratischer Rest (oder perfektes Quadrat) modulo n, wenn a ≡ b 2 ( mod n ) für eine ganze Zahl b . Ein solches b heißt eine Quadratwurzel von a modulo n . Wir lassen

sei die Menge der quadratischen Reste in Z * n , und wir bezeichnen die Menge der nichtquadratischen Reste in Z * n von QNR n = Z * n - QR n .

62 Quadratwurzeln Modulo a Prime

Behauptung ਁ Für eine ungerade Primzahl p ist jedes a QR P hat genau zwei Quadratwurzeln in Z * P , und genau 1/2 der Elemente von Z * P sind quadratische Reste.

Nehmen wir zum Beispiel p = 11 . Die folgende Tabelle zeigt alle Elemente von Z * 11 und ihre Quadrate.

Beweis: Wir beweisen nun Behauptungਁ . Betrachten Sie die Abbildung sq : Z * P → QR P definiert durch b b 2 mod p . Wir zeigen, dass dies eine 2-zu-1-Abbildung von Z * P auf QR P .

Lass a QR P , und sei b 2 ≡ a ( mod p ) eine Quadratwurzel von a . Dann ist - b auch eine Quadratwurzel von a und b ⁄≡- b (mod p) da p

∣ 2b . Daher hat a mindestens zwei verschiedene Quadratwurzeln (mod n). Nun sei c eine beliebige Quadratwurzel von a.

Dann p ∣ c 2 - b 2 , also p ∣ (c - b)(c + b). Da p eine Primzahl ist, dann ist entweder p ∣ ( c - b ) , in diesem Fall c ≡ b ( mod p ) oder p ∣ ( c + b ) , in diesem Fall c ≡ - b (modp). Daher c ≡ b (mod p). Da c eine beliebige Quadratwurzel von a war, folgt daraus, dass b die einzigen beiden Quadratwurzeln von a sind. Daher ist sq() eine 2-zu-1-Funktion und | QR P | = | Z * P | wie gewünscht. __

63 Quadratwurzeln Modulo das Produkt zweier Primzahlen

Behauptung ਂ Sei n = pq für p , q verschiedene ungerade Primzahlen. Dann jedes a QR n hat genau vier Quadratwurzeln in Z * n , und genau 1/4 der Elemente von Z * n sind quadratische Reste.

Beweis: Betrachten Sie die Abbildung sq : Z * n → QR n definiert durch b b 2 mod n . Wir zeigen, dass dies eine 4-zu-1-Abbildung von Z * n auf QR n .

Lass a QR n und sei b 2 ≡ a (mod n) eine Quadratwurzel von a. Dann auch b 2 ≡ a (mod p) und b 2 ≡ a (mod q), also ist b eine Quadratwurzel von a (mod p) und b ist eine Quadratwurzel von a (mod q). Umgekehrt, wenn b P ist eine Quadratwurzel von a ( mod p ) und b Q eine Quadratwurzel von a ( mod q ) ist, dann ist nach dem chinesischen Restsatz die eindeutige Zahl b Z * n so dass b ≡ b P ( mod p ) und b ≡ b Q (mod q) ist eine Quadratwurzel von a (mod n). Da a zwei Quadratwurzeln mod p und zwei Quadratwurzeln mod q hat, folgt, dass a vier Quadratwurzeln mod n hat. Somit ist sq() eine 4-zu-1-Funktion und | QR n | = | Z * n | wie gewünscht. __

64 Euler-Kriterium

Es gibt einen einfachen Test dank Euler, ob eine Zahl in QR ist P für p prim.

Behauptung ਃ (Euler-Kriterium): Eine ganze Zahl a ist ein nicht-trivialer 1 quadratischer Rest modulo p iff

Beweis: Sei a ≡ b 2 ( mod p ) für ein b ⁄≡ 0 ( mod p ). Dann

nach dem Satz von Euler, wie gewünscht.

Für die andere Richtung sei a ( p - 1) ∕ 2 ≡ 1 (mod p) angenommen. Ganz klar ein ⁄≡ 0 (mod p). Wir zeigen, dass a ein quadratischer Rest ist, indem wir eine Quadratwurzel b modulo p finden.

Sei g eine primitive Wurzel von p. Wähle k so, dass a ≡ g k (mod p) und sei ℓ = (p - 1) k∕ 2 . Dann

Da g eine primitive Wurzel ist, impliziert g ℓ ≡ 1 ( mod p ), dass ℓ ein Vielfaches von p - 1 ist. Daher ( p - 1) ∣ ( p - 1) k∕ 2 , woraus wir schließen, dass 2 | k und k∕ 2 ist eine ganze Zahl. Sei b = g k∕ 2 . Dann ist b 2 ≡ g k ≡ a ( mod p ) , also ist b wie gewünscht eine Quadratwurzel von a modulo p . __

65 Finden von Quadratwurzeln Modulo Special Primes

Mit dem Euler-Kriterium können wir die Mitgliedschaft in QR . testen P für Primzahl p , aber es sagt uns nicht, wie man Quadratwurzeln findet. Im Fall p ≡ 3 ( mod 4) gibt es einen einfachen Algorithmus zum Ermitteln der Quadratwurzeln eines beliebigen Mitglieds von QR P .

Behauptung ਄ Sei p ≡ 3 ( mod 4) , a QR P . Dann ist b = a ( p +1) ∕ 4 eine Quadratwurzel von a ( mod p ).

Beweis: Unter den Annahmen der Behauptung ist p + 1 durch 4 teilbar, also ist ( p + 1) ∕ 4 eine ganze Zahl. Dann

nach dem Euler-Kriterium (Anspruchਃ). __

66 Shank’s Algorithmus zum Finden von Quadratwurzeln Modulo ungerade Primzahlen

Sei p eine ungerade Primzahl. Seien s und t eindeutige ganze Zahlen, so dass p - 1 = 2 s t und t ungerade ist. (Beachten Sie, dass s einfach die Anzahl der nachgestellten Nullen in der binären Entwicklung von p - 1 ist, und t ist das, was übrig bleibt, wenn p - 1 um s Stellen nach rechts verschoben wird.) Da p ungerade ist, ist p - 1 gerade, also ≥ 1 .

Im Sonderfall s = 1 ist p - 1 = 2 t , also p = 2 t + 1 . Schreibt man die ungerade Zahl t als 2 ℓ + 1 für eine ganze Zahl ℓ , haben wir p = 2(2 ℓ + 1) + 1 = 4 ℓ + 3 , also p ≡ 3 ( mod 4) . Aber genau das ist das Besondere, das wir in Abschnittꁥ betrachtet haben.

Wir präsentieren nun einen Algorithmus, der Quadratwurzeln quadratischer Reste modulo jeder ungeraden Primzahl p findet. Der Algorithmusꁦ.1 weist aufgrund von D. Shanks 2 eine starke Ähnlichkeit mit dem Algorithmusꁖ.1 zum Faktorisieren des RSA-Moduls auf, wenn sowohl der Verschlüsselungs- als auch der Entschlüsselungsexponenten gegeben sind.

Sei p,s,t wie oben. Angenommen ein />QR P ein quadratischer Rest ist und u />QNR P ist ein quadratischer Nicht-Rest. (Wir können u leicht finden, indem wir zufällige Elemente von Z auswählen * P und Anwenden des Euler-Kriteriums.) Das Ziel ist es, x mit x 2 ≡ a (mod p) zu finden.

Eingabe: Ungerade Primzahl p , quadratischer Rest a QR P .

Ausgabe: Eine Quadratwurzel von a (mod p).

1. Seien s , t p = 2 s t und t ungerade.

2. Lass dich QNR P .

8. sei m die kleinste ganze Zahl mit b 2 m ≡ 1 ( mod p )


Abbildungꁦ.1: Shanks Algorithmus zum Finden einer Quadratwurzel von a (mod n).

Die Kongruenz x 2 ≡ ab ( mod p ) lässt sich leicht als Schleifeninvariante zeigen. Es ist anfangs eindeutig wahr, da x 2 ≡ a t +1 und b ≡ a t (mod p) ist. Jedes Mal, wenn die Schleife durchlaufen wird, bleibt a unverändert, b wird mit t 2 multipliziert (Zeilenꀐ undꀑ) und x wird mit t (Zeileꀒ) multipliziert, daher bleibt die Invariante unabhängig vom Wert von t wahr. Wenn das Programm endet, haben wir b ≡ 1 (mod p), also x 2 ≡ a und x ist eine Quadratwurzel von a (mod p).

Um zu sehen, warum sie nach höchstens s Iterationen der Schleife endet, betrachten wir die Ordnungen 3 von b und z ( mod p ) am Anfang jeder Schleifeniteration (vor Zeileਈ) und zeigen, dass ord ( b ) &# x003C ord(z) = 2k.

Bei der ersten Iteration ist k = s und z ≡ u t (mod p). Wir argumentieren, dass ord(z) = 2 s ist. Deutlich

so ord ( z ) ∣ 2 s . Da u ein Nicht-Rest ist, gilt nach dem Euler-Kriterium

Daher ist ord(z) = 2s. Unter Verwendung einer ähnlichen Argumentation, da a ein quadratischer Rest ist, b 2 s – 1 ≡ 1 (mod p), also ord (b) ∣ 2 s – 1 . Daraus folgt, dass ord ( b ) < ord ( z ) = 2 s = 2 k .

Nun setzt lineਈ bei jeder Iteration m = ord ( b ) und lineਉ setzt t = z 2 k - m - 1 mod p , also

Zeileꀐ setzt z = t 2 , also ord ( z ) = ord ( t ) ∕ 2 = 2 m . Nach Zeileꀑ ord ( b ) < 2 m . Dies liegt daran, dass der alte Wert von b und der neue Wert von z beide die Ordnung 2 m haben. Daher sind diese beiden Zahlen potenziert mit 2 m – 1 – 1 (mod p), also ist ihr Produkt (der neue Wert von b ) mit derselben Potenz ( – 1) 2 ≡ 1 . Zeileꀓ setzt k = m in Vorbereitung auf die nächste Iteration, und die Schleifeninvariante ord ( b ) < ord ( z ) = 2 k wird beibehalten. Darüber hinaus wird ord ( b ) bei jeder Iteration reduziert, sodass die Schleife nach höchstens s Iterationen enden muss.

67 QR probabilistisches Kryptosystem

Sei n = pq , p , q verschiedene ungerade Primzahlen. Wir können die Zahlen in Z teilen * n in vier Klassen, abhängig von ihrer Mitgliedschaft in QR P und QR Q . 4 Sei Q n 11 seien die Zahlen, die quadratische Reste sind, mod sowohl p als auch q seien Q n 10 seien jene Zahlen, die quadratische Reste mod p sind, aber nicht mod q sei Q n 01 seien die Zahlen, die quadratische Reste mod q aber nicht mod p sind und sei Q n 00 diejenigen Zahlen sein, die weder quadratische Reste mod p noch mod q sind. Unter diesen Definitionen ist Q n 11 = QR n und Q n 00 ∪ Q n 01 ∪ Q n 10 = QNR n . Tatsache Gegeben a />Q n 00 ∪ Q n 11 gibt es keinen bekannten praktikablen Algorithmus, um zu bestimmen, ob ein />QR n das gibt die richtige Antwort deutlich mehr als die Hälfte der Zeit.

Auf dieser Tatsache basiert das Goldwasser-Micali-Kryptosystem. Der öffentliche Schlüssel besteht aus einem Paar e = ( n,y ) , wobei n = pq für verschiedene ungerade Primzahlen p , q und y Q n 00. Der private Schlüssel besteht aus p . Der Nachrichtenraum ist = < 0 , 1 >.

m . verschlüsseln , Alice wählt ein zufälliges a QR n . Sie tut dies, indem sie ein zufälliges Mitglied von Z auswählt * n und quadrieren es. Wenn m = 0 ist, dann ist c = a mod n . Wenn m = 1 ist, dann ist c = ay mod n . Der Geheimtext ist c .

Es ist leicht zu zeigen, dass wenn m = 0 ist, dann c Q n 11 , und wenn m = 1 , dann c Q n 00. Man kann auch zeigen, dass jedes Element von Q n 11 wird mit gleicher Wahrscheinlichkeit als Geheimtext c gewählt, falls m = 0 und jedes Element von Q n 00 wird mit gleicher Wahrscheinlichkeit als Geheimtext c im Fall m = 1 gewählt. Eves Problem, zu bestimmen, ob c 0 oder 1 verschlüsselt, ist dasselbe wie das Problem der Unterscheidung zwischen der Zugehörigkeit zu Q n 00 und Q n 11, was aufgrund der obigen Tatsache als schwierig angesehen wird. Jeder, der den privaten Schlüssel p kennt, kann jedoch anhand des Euler-Kriteriums schnell feststellen, ob c ein quadratischer Rest mod p ist und damit c Q n 11 oder c Q n 00, wodurch m bestimmt wird.


Unterabschnitt 10.5.1 Finden einer höheren Wurzel

Hier ist eine Möglichkeit, die erste zu lösen. Zuerst finden wir eine primitive Wurzel modulo (19). Natürlich könnten wir einfach Sage fragen, oder das Kriterium vom letzten Mal mit Versuch und Irrtum in nicht allzu ferner Vergangenheit verwenden, die Rückseite jedes Zahlentheorietextes hatte eine Tabelle mit primitiven Wurzeln!

Jetzt werden wir versuchen zu repräsentieren beide Seiten von [x^4equiv 13 ext< mod >(19)] als Potenzen dieser primitiven Wurzel!

Der einfache Teil ist die Darstellung von (x^4) wir sagen nur, dass (xequiv 2^i) für einige (noch unbekannte) (i) gilt, also [x^4equiv left( 2^i ight)^4equiv 2^<4i> .] Der schwierigere Teil ist herauszufinden, welche Potenz von (2) (13) ergibt. Auch hier gibt es keine Abkürzung, obwohl Bücher in der Vergangenheit riesige Tabellen mit diesen Dingen hatten.

Wenn wir also (x^4) und (13) durch die primitiven Wurzeln ersetzen, können wir sagen, dass [x^4equiv 13 ext< mod >(19)] zu [2 ^<4i>equiv 2^<5> ext< mod >(19) .]

Wie hätten wir das in der Vorkalkulation gelöst? Sie würden es so lösen, mit Gleichungen (nicht Kongruenzen): [2^<4i>=2^<5>Rightarrow 4i=5 Rightarrow i=5/4 .] Wir werden versuchen, etwas sehr hier ähnlich.

Ganz wichtig ist, dass diese Kongruenz in gewissem Sinne wirklich keine Kongruenz mehr in (mathbb_<19>). Um genau zu sein, ist alles in Sichtweite wirklich in (U_<19>), einer zyklischen Gruppe der Ordnung (phi(19)=18). Aber eine zyklische Gruppe der Ordnung (18) wäre genauso wie das Denken modulo achtzehn! Wir können also die Exponenten herausnehmen, genau wie in der Vorberechnung, aber tun Sie die Dinge mod ((18)): [4iequiv 5 ext< mod >(18) .]

Das hat leider keine Lösung. Aber wir haben es herausgefunden, ohne jede vierte Macht da draußen zu nehmen! Tatsächlich bestätigt dies unser Ergebnis:

Versuchen wir stattdessen die gleiche Kongruenz modulo (17) – das heißt, können wir [x^4equiv 13 ext< mod >(17) ?] lösen? , und es stellt sich heraus, dass (3^4equiv 13) ist, also können wir es versuchen. Dies ergibt [3^<4i>equiv 3^4 ext< mod >(17)Rightarrow 4iequiv 4 ext< mod >(16), ,] was definitiv Lösungen hat – tatsächlich gibt es vier Lösungen ((1,5,9,13)) für die reduzierte Kongruenz [iequiv 1 ext< mod >(4)] also gibt es vier Lösungen ((3^1,3 ^5,3^9,3^<13>)) zur ursprünglichen Kongruenz. Lassen Sie uns dies überprüfen:

Sie können es sogar bei komplizierteren Dingen bei der Arbeit sehen. Wenn wir versuchen, (x^6equiv 8) mod (49) zu lösen, brauchen wir eine primitive Wurzel von 49 3 works. Ich kann herausfinden, welche Potenz (3^i) von (3) (8) ergibt:

Wir schreiben also (x=3^i) für einige noch unbekannte (i) und erhalten [3^<6i>equiv 3^<36> ext< mod >(49) , ] was uns [6iequiv 36 ext< mod >(phi(49)=42)] ergibt und dies reduziert sich auf [iequiv 6 ext< mod >(7) .] Also (i=6,13,20,27,34,41) alle funktionieren, was bedeutet (aus unserer kleinen Info oben), dass (x=3^equiv 43,10,16,6,39,33) sollte alles funktionieren.


Zahlentheorie: Im Kontext und interaktiv

Was die Theorie der quadratischen Reste/Quadratwurzeln am Ende am besten aufgehen ließ, waren einige Schlüsselinnovationen, die insbesondere der französische Mathematiker Adrien-Marie Legendre Gauss intensiv genutzt hat.

Historische Anmerkung 16.4.1. Adrien-Marie Legendre.

Legendre war Lagranges Nachfolger in Paris. Wie viele Mathematiker des 18. Jahrhunderts arbeitete Legendre auf vielen Gebieten, einschließlich der Funktionstheorie und der mathematischen Physik. Als eine zunehmende Professionalisierung des Studiums der höheren Mathematik in den postrevolutionären französischen Ingenieurwissenschaften eintrat (eine Entwicklungshistorikerin der Mathematik Judith Grabiner argumentiert, dass sie zu einer Rigorisierung der Infinitesimalrechnung führte), schrieb er ein weit verbreitetes Lehrbuch für Geometrie.

Eine historische Annäherung an das Thema kann von Vorteil sein, da wir den Vorteil haben, die Grundlagen von Gruppen und primitiven Wurzeln entwickelt zu haben, aber wir werden die Darstellung quadratischer Reste durch die (etwas anachronistische) Verwendung dieser Konzepte sehr vereinfachen können.

Unterabschnitt 16.4.1 Quadratische Reste bilden eine Gruppe

Definition 16.4.2 .

Betrachten Sie die Menge aller von Null verschiedenen quadratischen Reste modulo einer Primzahl (p ext<.>) Wir nennen dies die (Q_p ext<.>)

Diese Terminologie legt nahe, dass ich einen Beweis für den folgenden Satz in meiner Tasche habe.

Satz 16.4.3 .

Die Menge der von Null verschiedenen quadratischen Reste (Q_p) modulo a Primzahl (p) ist wirklich eine Gruppe und ist sogar eine Untergruppe der Gruppe von Einheiten (U_p ext<.>)

Nachweisen .

Wir fahren fort, indem wir zeigen, dass die Gruppenaxiome unter Multiplikation gelten. Da wir Null ausschließen und (p) eine Primzahl ist, ist (Q_p) im Wesentlichen per Definition eine Teilmenge von (U_p), was bedeutet, dass es auch eine Untergruppe von (U_p) ist.

Schauen wir uns die drei wichtigsten Axiome an.

Es ist klar, dass (1in Q_p ext<,>) seit (1equiv 1^2 ext<.>) also eine Identität gibt.

Als nächstes, wenn (a) und (b) beide in (Q_p) sind (mit (aequiv s^2) und (bequiv t^2)), dann gilt ( ab) ist auch ein quadratischer Rest (da ((st)^2equiv s^2 t^2equiv ab)).

Es bleibt nur noch zu prüfen, ob diese Menge unter Multiplikation Inverse hat.

Um diesen letzten Punkt zu zeigen, nehmen wir an, dass (aequiv s^2in Q_p ext<,>) und betrachte (s^<-1>) als ein Element von (U_p ext<.> ) Dann

So per Definition von inversen

was bedeutet, dass wenn (ain Q_p) dann auch (a^<-1>in Q_p) ist.

Bemerkung 16.4.4 .

Für diejenigen mit zusätzlichem algebraischen Hintergrund stellt sich heraus, dass (Q_p) tatsächlich auch ein von (U_p) ist, aber wir werden hier nicht weiter darauf eingehen.

Unterabschnitt 16.4.2 Quadratische Reste verbinden sich mit primitiven Wurzeln

Sie fragen sich vielleicht, wie dieser Teil von (U_p) mit dem Wichtigsten zusammenhängt, das wir bisher über (U_p ext<.>) gesehen haben. Denken Sie daran, dass (U_p) . war zyklisch, dass es einen Generator hatte, dessen Potenzen uns alle Einheiten modulo (p ext<.>) gaben. Wir nannten ein solches Element a von (p) (erinnern Sie sich an Kapitel 10).

Vergleichen wir also die Potenzen der primitiven Wurzel und die quadratischen Reste. Sollte nicht allzu schwer sein … wenn Sie das nicht mit Sage berechnen, versuchen Sie es einfach von Hand mit einem noch kleineren Modul, wie sieben oder elf.

Beachten Sie das Muster, bei dem Elemente von (U_<19>) (als Potenzen der primitiven Wurzel) quadratische Reste sind! Dies ist ein Beispiel für eine wichtige Tatsache.

Tatsache 16.4.5 .

Für ungerade Primzahlen (p ext<,>) sind die quadratischen Reste genau die auch Potenzen einer primitiven Wurzel (g ext<.>)

Nachweisen .

Certainly (g^<2n>=left(g^n ight)^2 ext<,>) so the even powers of (g) are QRs.

Now we need the other set inclusion. Suppose that (ain Q_p) and (a=s^2 ext<.>) Then first note that (s) and (a) are themselves still powers of (g) (by definition of (g)). So let (s=g^n) and (a=g^m) for some (n,m ext<.>) Then we have the implication

This is only possible if (m) is even since (p-1) and (2n) are even.

Example 16.4.6 .

This is a very strong statement, because it does not depend upon the primitive root! For example, if (p=11 ext<,>) one can verify both (2) and (8) are primitive roots modulo eleven then they are clearly nonresidues, and moreover are odd powers of each other:

This fact will turn out to be a fantastically useful theoretical way to find (Q_p ext<.>) It will show up in lots of proofy settings. Here is a first example, a very nice result about when a composite number is a QR.

Proposition 16.4.7 .

If (n=ab) is a factorization (not necessarily nontrivial) of (n ext<,>) then (n) is a QR of (p) precisely when either both (a) and (b) are QRs of (p) or both (a) and (b) are nicht QRs of (p ext<.>)

Proof .

Modulo (p ext<,>) write (aequiv g^i) and (bequiv g^j) for some (i,j ext<.>) Then (n=abequiv g^ ext<,>) and (i+j) is even when (i) and (j) have the same parity. Because of Fact 16.4.5, this is exactly the same thing as the conclusion of the proposition.

Hence if one of (a,b) is a QR and the other one isn't, neither is (n=ab ext<.>)

Example 16.4.8 .

Let's assume that we have the pattern observed in Question 16.3.4 and try to decide whether (21) is a QR (mod (23)).

Our first step is to try to make (21) a product of two numbers we already know something about. Since (21equiv -2) (mod (23)), we can look at (-1) and (2) separately. Then recall that (-1) is not a QR (since (23equiv 3) (mod (4))) but (2) is, from our explorations. So we would conjecture (21) is not a QR either.

We can use the same trick for other numbers congruent to (-2) modulo (p ext<.>) For instance, I can immediately decide that (-2equiv 9) ist a QR (mod (11)) by the fact that neither (-1) nor (2) is a QR modulo (11 ext<.>)

We will soon revisit this idea in Proposition 17.1.1.

There is yet another way to view the tension between primitive roots and quadratic residues. Before moving on to the next interactive graphic, try to answer the following question.

Question 16.4.9 .

Do you see why a quadratic residue automatically can't be a primitive root? (This follows from results earlier in this chapter see Exercise 16.8.10.)

Now try our familiar graphic again, this time concentrating on which rows correspond to primitive roots and which ones to quadratic residues.

The second column (labeled 1) contains all the residues, and by definition the quadratic residues are the colors located in the third column (labeled 2 as they are squares). See how that column is symmetric about the middle of the rows, with two of each of the QR colors appearing. Further, these are the same colors as the ones appearing in every other column in rows with a primitive root (the rows with every color represented) naturally, the order may be quite different. Finally, the second column's color in each row that has every color (including black) never shows up in the third column (the one for squares) this corresponds to the fact that a primitive root can't be a quadratic residue.

Try it out interactively until the connection between the known facts and the graphical pattern seems plausible.

These observations may not seem as interesting, but they will pay off in the next section we will obtain a crucial criterion for computing quadratic residues by observing a similar pattern!


Beispiel 2

Does the quadratic congruence $x^2 equiv 341 pmod <17>$ have solutions?

We can determine if this quadratic congruence has solutions by evaluating the Legendre symbol $(341/17)$ . Von (EIN), we know this Legendre symbol is defined since 17 is an odd prime and $17 mid 341$ . For evaluating this Legendre symbol, we are going to first use (B) to reduce 341. Note that we could have used this in example 1 too! $341 equiv 1 pmod <17>$ . Hence it follows that:

And since 1 is a square, then $left ( frac<1> <7> ight ) = 1$ . Hence it follows that the Legendre symbol $(341/17) = 1$ . So the quadratic congruence $x^2 equiv 341 pmod <17>$ has solutions. In fact, we can find them rather easily:

So x is 1 (mod 17) or -1 (mod 17). -1 is not in least residue, so instead our other solution is 16 (mod 17). Hence our solutions are x = 1 and x = 16.


2 Bound for large ω ( p − 1 )

For brevity, we merely state some necessary results from [4] . For k a positive integer, let

The last displayed equation in [4, p. 5] implies the following criterion, the satisfaction of which guarantees the existence of two consecutive QNRNPs modulo p :

As in [4] we bound the sums in ( 2 ) by noting that for ω ( p − 1 ) ≥ 2 we have ∑ 2 k ν = 1 ( ω ( p − 1 ) ν ) ≤ ω ( p − 1 ) 2 k . We now seek to bound θ k ( p ) . We have 3 3 3 We have corrected a slight misprint in [4] : their sum is over ν ≥ 2 k instead of ν ≥ 2 k + 1 .

θ k ( p ) = − 1 / 2 + ∑ ν ≥ 2 k + 1 ∑ d | p − 1 ω ( d ) = ν μ ( d ) d − ∑ d | p − 1 d > 1 μ ( d ) d = 1 2 − ϕ ( p − 1 ) p − 1 + ∑ ν ≥ 2 k + 1 ∑ d | p − 1 ω ( d ) = ν μ ( d ) d . (3)
∣ ∣ ∣ ∑ ν ≥ 2 k + 1 ∑ d | p − 1 ω ( d ) = ν μ ( d ) d ∣ ∣ ∣ ≤ ∑ ν ≥ 2 k + 1 ∑ d | p − 1 ω ( d ) = ν d squarefree 1 d ≤ ∑ ν ≥ 2 k + 1 1 ν ! P ν , (4)

since for ω ( p − 1 ) = n we have that p ≥ 2 ⋅ 3 ⋅ 5 ⋯ q ω ( p − 1 ) + 1 . To estimate ( 5 ) we use the following results

ω ( n ) ≤ 1.385 log n log log n ( n ≥ 3 ) , ∑ p ≤ x 1 p ≤ log log x + 0.262 + 1 log 2 x ( x ≥ 2 ) , p n ≤ n ( log n + log log n ) ( n ≥ 6 ) , (6)

which are respectively [6, Thm 10] and [7, (3.20) and (3.13)] . We also use the inequality ν ! ≥ ( ν / e ) ν , which is valid for all ν ≥ 1 . Although sharper versions of these inequalities are available, the present ones are sufficient for our purposes. For any k ≥ e P we have

Therefore taking k = max < [ e P ] + 1 , log ( 2 / ϵ ) / ( 2 log 2 ) >we ensure that the sum in ( 7 ) is at most ϵ / 2 . This shows, from ( 3 ), and from the assumption that ϕ ( p − 1 ) / ( p − 1 ) ≤ 1 2 − ϵ that ϵ 2 ≤ θ k ( p ) ≤ 1 . Therefore, our criterion in ( 2 ) becomes

We now insert our bounds for ( 6 ). These bound ω ( p − 1 ) , P , and hence k . For ϵ = 1 / 4 , a quick computer check verifies Theorem 1 for all p with ω ( p − 1 ) ≥ 48 . Before considering these cases in the next section, we briefly dispense with the case ω ( p − 1 ) = 1 .

When ω ( p − 1 ) = 1 the bound for θ k ( p ) in ( 3 ) reduces to θ k ( p ) = 1 2 − ϕ ( p − 1 ) / ( p − 1 ) ≥ ϵ . Taking ϵ = 1 4 and inserting this into ( 2 ) proves the existence of two consecutive QNRNPs provided that p > 1600 . It is easy to check that there are no p < 1600 satisfying both ϕ ( p − 1 ) ≤ ( p − 1 ) / 4 and ω ( p − 1 ) = 1 .


Quadratic Residues

Let (a in mathbb_n). We say (a) is a quadratic residue if there exists some (x) such that (x^2 = a). Otherwise (a) is a quadratic nonresidue.

Efficiently distinguishing a quadratic residue from a nonresidue modulo (N = p q) for primes (p, q) is an open problem. This is exploited by several cryptosystems, such as Goldwassser-Micali encryption, or Cocks identity-based encryption. More general variants of this problem underlie other cryptosystems such as Paillier encryption.

Let (p) be an odd prime, as the case (p = 2) is trivial. Let (g) be a generator of (mathbb_p^*). Any (a in mathbb_p^*) can be written as (g^k) for some (k in [0..p-2]).

Say (k) is even. Write (k = 2m). Then ((g^m)^2 = a), so (a) is a quadratic residue. Exactly half of ([0..p-2]) is even (since (p) is odd), hence at least half of the elements of (mathbb_p^*) are quadratic residues.

Suppose we have (b^2 = a). Then ((-b)^2 = a) as well, and since (b e -b) (since (p > 2)) every quadratic residue has at least two square roots (in fact, we know from studying polynomials there can be at most two), thus at most half the elements of (mathbb_p^*) are quadratic residues. (Otherwise there are more square roots than elements!)

Thus exactly half of (mathbb_p^*) are quadratic residues, and they are the even powers of (g).

Given (a = g^k), consider the effect of exponentiating by ((p-1)/2). If (k) is odd, say (k = 2m + 1), we get

The square of (g^<(p-1)/2>) is (g^ = 1), so (g^<(p-1)/2>) is (1) or (-1). But (g) has order (p-1) ((g) is a generator) thus we must have (g^ <(p-1)/2>= -1).

If (k) is even, say (k = 2m), then (a^ <(p-1)/2>= g^ <(p-1)m>= 1).

In other words, we have proved Euler’s Criterion, which states (a) is a quadratic residue if and only if (a^ <(p-1)/2>= 1), and (a) is a quadratic nonresidue if and only if (a^ <(p-1)/2>= -1).

Beispiel: We have (-1) is a quadratic residue in (mathbb_p) if and only if (p = 1 pmod <4>).


Schau das Video: The Howling Mines. Critical Role: THE MIGHTY NEIN. Episode 6 (Januar 2022).