imported>WikiMax312: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-02-06T01:55:55Z

growthexperiments-addlink-summary-summary:2|0|0

Neue Seite

'''Quadratischer Rest''' ist ein Begriff aus dem [[Teilgebiete der Mathematik|mathematischen Teilgebiet]] [[Zahlentheorie]]. Eine [[ganze Zahl]] <math>a</math> heißt quadratischer Rest bezüglich eines [[Modulo|Moduls]] <math>m</math>, wenn sie zu <math>m</math> [[Teilerfremdheit|teilerfremd]] ist und es eine Zahl <math>x</math> gibt, für die die [[Kongruenz (Zahlentheorie)|Kongruenz]]
: <math>a \equiv x^2 \pmod m</math>
gilt, das heißt, <math>a</math> und <math>x^2</math> liegen in der gleichen [[Restklasse]] modulo <math>m</math>.
Existiert für eine zu <math>m</math> [[teilerfremd]]e 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.

{| class="wikitable"
! <math>x</math>
! <math>x^2</math>
! <math>x^2 \bmod 6</math>
|-
| 0 || {{0}}0 || 0
|-
| 1 || {{0}}1 || 1
|-
| 2 || {{0}}4 || 4
|-
| 3 || {{0}}9 || 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 quadratischen Reste ==

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 des Moduls <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 <math>(0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1)</math> 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 Modul <math>m=11</math> rasch auch im Kopf berechnen.

Dadurch ergibt sich mit den nachfolgenden Zyklen ein (symmetrisches) Muster:
mod 2: (0, 1)
mod 3: (0, 1, 1)
mod 4: (0, 1)
mod 5: (0, 1, 4, 4, 1)
mod 6: (0, 1, 4, 3, 4, 1)
mod 7: (0, 1, 4, 2, 2, 4, 1)
mod 8: (0, 1, 4, 1)
mod 9: (0, 1, 4, 0, 7, 7, 0, 4, 1)
mod 10: (0, 1, 4, 9, 6, 5, 6, 9, 4, 1)
mod 11: (0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1)
mod 12: (0, 1, 4, 9, 4, 1)
mod 13: (0, 1, 4, 9, 3, 12, 10, 10, 12, 3, 9, 4, 1)
mod 14: (0, 1, 4, 9, 2, 11, 8, 7, 8, 11, 2, 9, 4, 1)
mod 15: (0, 1, 4, 9, 1, 10, 6, 4, 4, 6, 10, 1, 9, 4, 1)
mod 16: (0, 1, 4, 9)
mod 17: (0, 1, 4, 9, 16, 8, 2, 15, 13, 13, 15, 2, 8, 16, 9, 4, 1)
mod 18: (0, 1, 4, 9, 16, 7, 0, 13, 10, 9, 10, 13, 0, 7, 16, 9, 4, 1)
mod 19: (0, 1, 4, 9, 16, 6, 17, 11, 7, 5, 5, 7, 11, 17, 6, 16, 9, 4, 1)
mod 20: (0, 1, 4, 9, 16, 5, 16, 9, 4, 1)
…
Die Zyklen der durch 4 teilbaren Moduln treten im Muster mehrfach auf.

== 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

: <math>ab \equiv (xy)^2 \pmod m</math>

sodass auch das Produkt <math>ab</math> quadratischer Rest ist.

Dank der Teilerfremdheit zu <math>m</math> hat <math>a</math> ein Inverses. Dieses ist auch ein quadratischer Rest, denn <math>a^{-1} \equiv (x^2)^{-1} \equiv (x^{-1})^2 \pmod m</math>. Das Inverse von <math>x</math> existiert, denn <math>x\cdot (xa^{-1}) \equiv 1 \pmod m</math>.

Da <math>1 \equiv 1^2 \pmod m</math> trivialerweise ein Rest ist, erfüllen die quadratischen Reste somit alle Eigenschaften einer [[Gruppe (Mathematik)|Gruppe]].

== Legendre- und 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} \quad 1, & \mbox{wenn } a \mbox{ quadratischer Rest modulo } p \mbox{ ist} \\ -1, & \mbox{wenn } a \mbox{ quadratischer Nichtrest modulo } p \mbox{ ist} \\ \quad 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} \cdot \ldots \cdot 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} \cdot \ldots \cdot \left(\frac{a}{p_k}\right)^{\nu_k}</math>
Da das Jacobi-Symbol für Primzahlmoduln dieselben Werte wie das Legendre-Symbol liefert, ist die Verwendung der gleichen Kurzschreibweise nicht von Nachteil. Als wichtiges Hilfsmittel zur Berechnung des Legendre-Symbols steht das [[Quadratisches Reziprozitätsgesetz|quadratische Reziprozitätsgesetz mit dem ersten und zweiten Ergänzungssatz]] zur Verfügung. Zu beachten ist aber, dass man am Jacobi-Symbol nicht eindeutig ablesen kann, ob eine Zahl ein quadratischer Rest ist, so ist zum Beispiel <math>\left(\frac{2}{15}\right)=1</math>, aber 2 kein quadratischer Rest modulo 15.

== 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 [[Eulersches Kriterium|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>\tfrac{p-1}{2}</math> quadratische Reste und ebenso viele 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:
{| class="wikitable"
|-
|
| '''''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 <math>p</math>, 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 <math>q</math>, 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.

[[Kategorie:Zahlentheorie]]

Quadratischer Rest - Versionsgeschichte

imported>WikiMax312: /* growthexperiments-addlink-summary-summary:2|0|0 */