Quadratischer Rest

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Der quadratische Rest ist ein Begriff aus dem mathematischen Teilgebiet Zahlentheorie. Eine Zahl $a$ ist ein quadratischer Rest bezüglich eines Moduls $m$ , wenn sie zu $m$ teilerfremd ist und es eine Zahl $x$ gibt, für die die Kongruenz

$x^2 \equiv a \pmod m$

gilt. Dies ist gleichbedeutend damit, dass $a$ der Rest bei der Division einer Quadratzahl durch $m$ ist:

x 2 : m = ? Rest a

Existiert für eine zu $m$ teilerfremden Zahl $a$ keine Lösung $x$ der obigen Kongruenz, dann nennt man $a$ quadratischen Nichtrest modulo $m$ . Zu $m$ nicht teilerfremde Zahlen werden nicht klassifiziert.

Betrachtet man beispielsweise den Modul 6, so ist 1 quadratischer Rest und 5 quadratischer Nichtrest. Dies ist sofort ersichtlich, wenn man $x 2 mod 6$ für die Zahlen von 0 bis 5 ausrechnet:

$x$	$x 2$	$x 2 mod 6$
0	0	0
1	1	1
2	4	4
3	9	3
4	16	4
5	25	1

Die Zahlen 0, 2, 3 und 4 sind nicht teilerfremd zu 6 und werden deshalb nicht klassifiziert.

Vor allem in der Kryptologie stellt sich vielfach die Aufgabe für eine vorgegebene Zahl und einen bekannten Modul zu entscheiden, ob diese Zahl ein Quadratischer Rest ist. Diese Fragestellung wird als Quadratische-Reste-Problem bezeichnet. Ist der Modul eine Primzahl, so kann dies recht einfach entschieden werden. Andernfalls stellt es sich teilweise recht schwierig dar. Insbesondere besagt die Quadratische-Reste-Annahme, dass es für bestimmte Module praktisch nicht möglich ist, diese Frage zu entscheiden.

Für Rechnungen, bei denen man nachweisen will, ob eine Zahl quadratischer Rest ist, stehen zwei Kurzschreibweisen zur Verfügung. Das Legendre-Symbol gibt an, ob eine Zahl quadratischer Rest für einen Primzahlmodul ist:

$\left(\frac{a}{p}\right) = \begin{cases} 1 & \mbox{wenn } a \mbox{ Quadratischer Rest modulo } p \mbox{ ist} \\ -1 & \mbox{wenn } a \mbox{ Quadratischer Nichtrest modulo } p \mbox{ ist} \end{cases}$

Dieses wird zum Jacobi-Symbol verallgemeinert, das die Berechnung für beliebige Module auf deren Primfaktorzerlegung $m=p_1^{\nu_1} \cdot p_2^{\nu_2} \cdot \ldots \cdot p_k^{\nu_k}$ zurückführt:

$\left(\frac{a}{m}\right) = \left(\frac{a}{p_1}\right)^{\nu_1} \cdot \left(\frac{a}{p_2}\right)^{\nu_2} \cdot \ldots \cdot \left(\frac{a}{p_k}\right)^{\nu_k}$

Da das Legendre-Symbol für Primzahlmodule mit dem Jacobi-Symbol identisch ist, ist die Verwendung der gleichen Kurzschreibweise nicht von Nachteil. Als wichtiges Hilfsmittel zur Berechnung des Legendre-Symbols steht das Quadratische Reziprozitätsgesetz mit dem ersten und zweiten Ergänzungssatz zur Verfügung.

Inhaltsverzeichnis

1 Quadratische Reste bei Primzahlmodulen
2 Vereinfachte Berechnung der Quadratzahlen
3 Multiplikative Eigenschaften
- 3.1 Der Fall von Primzahlen und das Legendre-Symbol
4 Die Besonderheit der 4
5 Quellen

[Bearbeiten] Quadratische Reste bei Primzahlmodulen

Ist der Modul eine Primzahl $p$ , so liefert das Eulersche Kriterium ein wichtige Aussage über quadratische Reste. Ein zu $p$ teilerfremdes $a$ ist demnach genau dann ein quadratischer Rest, wenn die folgende Kongruenz gilt:

$a^{(p-1)/2} \equiv 1 \pmod p$

Daraus lässt sich herleiten, dass es bei einem Primzahlmodul genau $\frac{p-1}{2}$ quadratische Reste und ebensoviele quadratische Nichtreste gibt.

[Bearbeiten] Vereinfachte Berechnung der Quadratzahlen

Für kleinere Zahlen $m$ können die quadratischen Reste relativ rasch berechnet werden: Es genügt, die Zahlen $0\leq x\leq m/2$ zu betrachten, denn $x 2$ und $(x+k\cdot m)^2$ haben denselben Rest, ebenso $x 2$ und $( - x) 2$ , also auch $x 2$ und $(m - x) 2$ .

Die Berechnung wird hier am Beispiel der Zahl 11 demonstriert.

 0 Mod 11 = 0 ;  1 Mod 11 = 1 ;   4 Mod 11 = 4 ;     9 Mod 11 = 9 
16 Mod 11 = 5 ; 25 Mod 11 = 3 ;  36 Mod 11 = 3 ;    49 Mod 11 = 5 
64 Mod 11 = 9 ; 81 Mod 11 = 4 ; 100 Mod 11 = 1 und 121 Mod 11 = 0.

Man könnte jetzt weitermachen, aber der 0,1,4,9,5,3,3,5,9,4,1-Zyklus wiederholt sich immer wieder. Wegen der Symmetriebeziehung ist nur die Berechnung der Quadratzahlen kleiner 36 erforderlich.

Zur Berechnung der Quadratzahlen kann die Beziehung

$\left({n+1}\right)^2 = n^2 + 2 \cdot n +1$

verwendet werden. Die nächste Quadratzahl kann also durch Addition von $2 n + 1$ ganz ohne Multiplikation berechnet werden. Damit sind die quadratischen Reste für 11 ganz rasch auch im Kopf zu berechnen.

[Bearbeiten] Multiplikative Eigenschaften

Sind $a$ und $b$ quadratische Reste modulo $m$ , dann ist auch $a b$ ein quadratischer Rest. Dies lässt sich einfach zeigen , indem man beide Zahlen multipliziert:

$a \equiv x^2 \pmod m$

$b\equiv y^2 \pmod m$

$ab \equiv (xy)^2 \pmod m$

[Bearbeiten] Der Fall von Primzahlen und das Legendre-Symbol

Im folgenden sei $m = p$ eine Primzahl. Sind $a$ und $b$ nicht durch $p$ teilbar, so gibt die folgende Tabelle in Abhängigkeit von $a$ und $b$ an, ob das Produkt $a b$ quadratischer Rest (R) oder Nichtrest (NR) ist:

	a R	a NR
b R	ab R	ab NR
b NR	ab NR	ab R

Eine andere Formulierung dieser Aussage ist die folgende: Das Legendre-Symbol erfüllt die Beziehung

$\left(\frac{ab}p\right)=\left(\frac ap\right)\left(\frac bp\right)$

Für Primzahlen $p > 2$ gilt

$\left(\frac ap\right)\equiv a^{(p-1)/2}\mod p.$

Aus dieser Beziehung lässt sich auch unmittelbar die folgende Aussage ablesen: $- 1$ ist quadratischer Rest modulo Primzahlen der Form $4 k + 1$ und Nichtrest modulo Primzahlen der Form $4 k + 3$ .

[Bearbeiten] Die Besonderheit der 4

Zur Basis der 4 gibt es für die ungeraden Quadratzahlen nur einen quadratischen Rest, nämlich die 1 (für $n \equiv 1 \bmod 4$ oder $n \equiv 3 \bmod 4$ ergibt sich in beiden Fällen $n^2 \equiv 1 \bmod 4$ ; gerade Zahlen ergeben $n^2 \equiv 0 \bmod 4$ ). Die andere ungerade Zahl, die 3, ist demzufolge der nicht-quadratische Rest, was bedeutet, dass keine Zahl zum Quadrat in Bezug auf Modulo 4 die Zahl 3 zurückliefert. Insbesondere die ungeraden Primzahlen (also p>2) lassen sich nun in zwei Gruppen einteilen:

In solche Primzahlen p, für die gilt $p \equiv 1 \bmod 4$ , woraus folgt, dass Quadratzahlen n² existieren, für die gilt: $n^2 \equiv (p-1) \bmod p$ . Für die Primzahlen dieser Gruppe gilt:

$(p-1)^{\frac{p-1}{2}} \equiv 1 \bmod p$

welches der Schreibweise mit dem Legendre-Symbol

$\left(\frac{p-1}{p}\right) = 1$ oder kürzer: $\left(\frac{-1}{p}\right) = 1$ entspricht (nicht mit einem Bruch zu verwechseln!).

In solche Primzahlen p, für die gilt $p \equiv 3 \bmod 4$ , woraus folgt, das keine Quadratzahlen n² existieren, für die gilt: $n^2 \equiv (p-1) \bmod p$ . Für die Primzahlen dieser Gruppe gilt:

$(p-1)^{\frac{p-1}{2}} \equiv (p-1) \bmod p$ .

Mit dem Legendre-Symbol ausgedrückt:

$\left(\frac{p-1}{p}\right) = (p-1)$ oder kürzer: $\left(\frac{-1}{p}\right) = -1$

Alle geraden Quadrat-Zahlen besitzen die 4 als Faktor, was sich einfach zeigen lässt: n = 2*m => n² = 4*m². Daraus folgt, das für jede gerade Quadratzahl n² gilt: $n^2 \equiv 0 \bmod 4$ .