Quadratischer Rest

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. Für den Spezialfall $0 < a < m$ ist Letzteres gleichbedeutend damit, dass $a$ der Rest bei der Division einer Quadratzahl durch $m$ ist:

$x^2 : m = ? \mbox{ Rest } a$

Existiert für eine zu $m$ teilerfremde 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.

Beispiel

In diesem Beispiel werden die quadratischen Reste und Nichtreste des Moduls 6 ermittelt. Da die Zahlen 0, 2, 3 und 4 nicht teilerfremd zu 6 sind, werden sie nicht klassifiziert. Zur Klassifikation der Zahlen 1 und 5 ist die folgende Tabelle der Quadrate aller Zahlen von 0 bis 5 hilfreich.

$x$	$x^2$	$x^2 \bmod 6$
0	0	0
1	1	1
2	4	4
3	9	3
4	16	4
5	25	1

Die Zahl 1 findet sich in der rechten Spalte und ist deshalb ein quadratischer Rest. Die Zahl 5 hingegen ist ein quadratischer Nichtrest, da sie in der rechten Spalte fehlt.

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 $2n+1$ ganz ohne Multiplikation berechnet werden. Damit sind die quadratischen Reste für 11 ganz rasch auch im Kopf zu berechnen.

Multiplikative Eigenschaften

Sind $a$ und $b$ quadratische Reste modulo $m$, dann ist auch $ab$ 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$

Jacobi-Symbol

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} \\ 0 & \mbox{wenn } a \mbox{ ein Vielfaches von } p \mbox{ ist} \end{cases}$

Dieses wird zum Jacobi-Symbol verallgemeinert, das die Berechnung für beliebige Moduln auf deren Primfaktorzerlegung $m=p_1^{\nu_1} \cdot p_2^{\nu_2} \dotsm 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} \dotsm \left(\frac{a}{p_k}\right)^{\nu_k}$

Da das Legendre-Symbol für Primzahlmoduln 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.

Anwendung in der Kryptologie

Vor allem in der Kryptologie stellt sich vielfach die Aufgabe, für eine vorgegebene Zahl und einen bekannten Modulus zu entscheiden, ob diese Zahl ein quadratischer Rest ist. Diese Fragestellung wird als Quadratische-Reste-Problem bezeichnet. Ist der Modulus 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 Moduli praktisch nicht möglich ist, diese Frage zu entscheiden.

Quadratische Reste bei Primzahlmoduln

Ist der Modul eine ungerade Primzahl $p$, so liefert das Eulersche Kriterium eine 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.

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 $ab$ 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 $4k+1$ und Nichtrest modulo Primzahlen der Form $4k+3$.

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 quadratische Nichtrest, was bedeutet, dass keine Zahl, nachdem sie quadriert wurde, modulo 4 den Rest 3 lässt. 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, dass 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) = -1$ oder kürzer: $\left(\frac{-1}{p}\right) = -1$

Alle geraden Quadratzahlen besitzen die 4 als Faktor, was sich einfach zeigen lässt: $n = 2 \cdot m \Rightarrow n^2 = 4\cdot m^2$. Daraus folgt, dass für jede gerade Quadratzahl $n^2$ gilt: $n^2 \equiv 0 \bmod 4$.

Quellen

• Peter Bundschuh: Einführung in die Zahlentheorie. 5. Auflage. Springer, 2002, ISBN 3-540-43579-4, S. 124 und 127–147