Quadratischer Rest

Quadratischer Rest ist ein Begriff aus dem mathematischen Teilgebiet Zahlentheorie. Eine ganze Zahl heißt quadratischer Rest bezüglich eines Moduls , wenn sie zu teilerfremd ist und es eine Zahl gibt, für die die Kongruenz

gilt, das heißt, und liegen in der gleichen Restklasse modulo . Existiert für eine zu teilerfremde Zahl keine Lösung der obigen Kongruenz, dann nennt man quadratischen Nichtrest modulo . Zu nicht teilerfremde Zahlen werden nicht klassifiziert, sind also weder quadratische Reste noch quadratische Nichtreste.

BeispielBearbeiten

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.

     
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 quadratischen ResteBearbeiten

Für kleinere Zahlen   können die quadratischen Reste relativ rasch berechnet werden: Es genügt, die Zahlen   zu betrachten, denn   und   haben denselben Rest, ebenso   und  , also auch   und  .

Die Berechnung wird hier am Beispiel des Moduls   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   kann man sich auf die Reduktion der Quadratzahlen beschränken, die nicht größer als   sind.

Zur Berechnung der Quadratzahlen kann die Beziehung

 

verwendet werden. Die nächste Quadratzahl kann also durch Addition von   ganz ohne Multiplikation berechnet werden. Damit lassen sich die quadratischen Reste für Modul   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.

Multiplikative EigenschaftenBearbeiten

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

 
 

folgt zunächst

 
 

mit zwei ganzen Zahlen   und  . Nun liefert eine Multiplikation

 

mit der ganzen Zahl  , woraus

 

folgt, sodass mit   und   auch das Produkt   quadratischer Rest ist.

Legendre- und Jacobi-SymbolBearbeiten

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:

 

Dieses wird zum Jacobi-Symbol verallgemeinert, das die Berechnung für beliebige Moduln auf deren Primfaktorzerlegung   zurückführt:

 

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 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  , aber 2 kein quadratischer Rest modulo 15.

Anwendung in der KryptologieBearbeiten

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 PrimzahlmodulnBearbeiten

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

 

Daraus lässt sich herleiten, dass es für einen ungeraden Primzahlmodul   genau   quadratische Reste und ebenso viele quadratische Nichtreste gibt.

Der Fall von Primzahlen und das Legendre-SymbolBearbeiten

Im Folgenden sei   eine Primzahl. Ist weder   noch   durch   teilbar, so gibt die folgende Tabelle in Abhängigkeit von   und   an, ob das Produkt   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

 

Für ungerade Primzahlen gilt

 

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

  ist quadratischer Rest modulo Primzahlen der Form   und Nichtrest modulo Primzahlen der Form  .

Die Besonderheit der 4Bearbeiten

Modulo 4 gibt es nur einen quadratischen Rest, nämlich 1. Denn sowohl für   als auch für   ergibt sich   und für gerade Zahlen   gilt  . 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  , für die   gilt: Für sie existieren Quadratzahlen   mit  . Für die Primzahlen dieser Gruppe gilt:
 
Mit dem Legendre-Symbol kann man dafür auch
 
schreiben oder kürzer:
 
  • Primzahlen  , für die   gilt: Für sie existieren keine Quadratzahlen   mit  . Für die Primzahlen dieser Gruppe gilt:
 
 
 

LiteraturBearbeiten