Quadratischer Rest - LinkFang.de





Quadratischer Rest


„Quadratischer Rest“ ist ein Begriff aus dem mathematischen Teilgebiet Zahlentheorie. Eine Zahl [math]a[/math] heißt quadratischer Rest bezüglich eines Moduls [math]m[/math], wenn sie zu [math]m[/math] teilerfremd ist und es eine Zahl [math]x[/math] gibt, für die die Kongruenz

[math]a \equiv x^2 \pmod m[/math]

gilt, die gleichwertig ist mit der Existenz einer ganzen Zahl [math]t[/math], für die gilt:

[math]a = x^2 + t\cdot m[/math]

Existiert für eine zu [math]m[/math] teilerfremde Zahl [math]a[/math] keine Lösung [math]x[/math] der obigen Kongruenz, dann nennt man [math]a[/math] quadratischen Nichtrest modulo [math]m[/math]. Zu [math]m[/math] nicht teilerfremde Zahlen werden nicht klassifiziert, sind also weder quadratische Reste noch quadratische Nichtreste.

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.

[math]x[/math] [math]x^2[/math] [math]x^2 \bmod 6[/math]
0 00 0
1 01 1
2 04 4
3 09 3
4 16 4
5 25 1

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

Vereinfachte Berechnung der Quadratzahlen

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

Die Berechnung wird hier am Beispiel der Zahl [math]m=11[/math] 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; 121 mod 11 = 0

Wenn man so weitermacht, wiederholt sich der Zyklus (0,1,4,9,5,3,3,5,9,4,1) immer wieder. Wegen der Symmetriebeziehung [math](m-x)^2 \equiv x^2 \pmod m[/math] kann man sich auf die Reduktion der Quadratzahlen beschränken, die nicht größer als [math]\lfloor m/2 \rfloor^2=25[/math] sind.

Zur Berechnung der Quadratzahlen kann die Beziehung

[math]\left({n+1}\right)^2 = n^2 + 2 \cdot n +1 [/math]

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

Multiplikative Eigenschaften

Sind [math]a[/math] und [math]b[/math] quadratische Reste modulo [math]m[/math], dann ist auch [math]ab[/math] quadratischer Rest. Dies lässt sich einfach zeigen, indem man beide Zahlen multipliziert: Aus

[math]a \equiv x^2 \pmod m[/math]
[math]b \equiv y^2 \pmod m[/math]

folgt zunächst

[math]a = x^2 + t\cdot m[/math]
[math]b = y^2 + u\cdot m[/math]

mit zwei ganzen Zahlen [math]t[/math] und [math]u[/math]. Nun liefert eine Multiplikation

[math]a\cdot b = (xy)^2 + v\cdot m[/math]

mit der ganzen Zahl [math]v=ux^2+ty^2+tum[/math], woraus

[math]ab \equiv (xy)^2 \pmod m[/math]

folgt, sodass mit [math]a[/math] und [math]b[/math] auch das Produkt [math]ab[/math] quadratischer Rest ist.

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:

[math]\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}[/math]

Dieses wird zum Jacobi-Symbol verallgemeinert, das die Berechnung für beliebige Moduln auf deren Primfaktorzerlegung [math]m=p_1^{\nu_1} \cdot p_2^{\nu_2} \dotsm p_k^{\nu_k}[/math] zurückführt:

[math]\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}[/math]

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 Modul zu entscheiden, ob diese Zahl für den Modul 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 Moduln praktisch nicht möglich ist, diese Frage zu entscheiden.

Quadratische Reste bei Primzahlmoduln

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

[math]a^{\frac {p-1}{2}} \equiv 1 \pmod p[/math]

Daraus lässt sich herleiten, dass es für einen ungeraden Primzahlmodul [math]p[/math] genau [math]\frac{p-1}{2}[/math] quadratische Reste und ebensoviele quadratische Nichtreste gibt.

Der Fall von Primzahlen und das Legendre-Symbol

Im Folgenden sei [math]m=p[/math] eine Primzahl. Ist weder [math]a[/math] noch [math]b[/math] durch [math]p[/math] teilbar, so gibt die folgende Tabelle in Abhängigkeit von [math]a[/math] und [math]b[/math] an, ob das Produkt [math]ab[/math] quadratischer Rest (R) oder Nichtrest (NR) ist:

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

Dies lässt sich auch so formulieren: Für das Legendre-Symbol gilt stets

[math]\left(\frac{ab}p\right)=\left(\frac ap\right)\left(\frac bp\right).[/math]

Für ungerade Primzahlen gilt

[math]\left(\frac ap\right)\equiv a^{\frac{p-1}{2}}\pmod p.[/math]

Aus dieser Beziehung lässt sich auch unmittelbar die folgende Aussage ablesen:

[math]-1[/math] ist quadratischer Rest modulo Primzahlen der Form [math]4k+1[/math] und Nichtrest modulo Primzahlen der Form [math]4k+3[/math].

Die Besonderheit der 4

Modulo 4 gibt es nur einen quadratischen Rest, nämlich 1. Denn sowohl für [math]n \equiv 1 \pmod 4[/math] als auch für [math]n \equiv 3 \pmod 4[/math] ergibt sich [math]n^2 \equiv 1 \pmod 4[/math] und für gerade Zahlen [math]n[/math] gilt [math]n^2 \equiv 0 \pmod 4[/math]. 3 ist demzufolge quadratischer Nichtrest, was bedeutet, dass keine Quadratzahl modulo 4 den Rest 3 lässt. Die ungeraden Primzahlen (also alle außer 2) lassen sich daher in zwei Gruppen einteilen:

  • Primzahlen p, für die [math]p \equiv 1 \pmod 4[/math] gilt: Für sie existieren Quadratzahlen [math]n^2[/math] mit [math]n^2 \equiv (p-1) \pmod p[/math]. Für die Primzahlen dieser Gruppe gilt:
[math](p-1)^{\frac{p-1}{2}} \equiv 1 \pmod p[/math]
Mit dem Legendre-Symbol kann man dafür auch
[math]\left(\frac{p-1}{p}\right) = 1[/math]
schreiben oder kürzer:
[math]\left(\frac{-1}{p}\right) = 1[/math]
  • Primzahlen q, für die [math]q \equiv 3 \pmod 4[/math] gilt: Für sie existieren keine Quadratzahlen [math]n^2[/math] mit [math]n^2 \equiv (q-1) \pmod q[/math]. Für die Primzahlen dieser Gruppe gilt:
[math](q-1)^{\frac{q-1}{2}} \equiv (q-1) \pmod q[/math]
[math]\left(\frac{q-1}{q}\right) = -1[/math]
[math]\left(\frac{-1}{q}\right) = -1[/math]

Literatur

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

Kategorien: Zahlentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Quadratischer Rest (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.