Quadratisches-Rest-Prüfer

Eine ganze Zahl a ist ein quadratischer Rest modulo m, wenn eine ganze Zahl x erfüllt, dass x zum Quadrat kongruent zu a modulo m ist — mit anderen Worten, a hat eine modulare Quadratwurzel. Diese Ja-oder-Nein-Frage taucht in Kryptographie-Hausaufgaben, Wettbewerb-Zahlentheorie und jedem Workflow auf, der wissen muss, ob eine Kongruenz ein perfektes Quadrat ist, bevor Aufwand in einen größeren Löser fließt. Diese Fähigkeit nimmt a und einen Modul m (mindestens zwei), reduziert a in den kanonischen Bereich null bis m minus eins, sucht jede Wurzel in diesem Bereich und kann optional die vollständige Liste der quadratischen Restklassen modulo m zurückgeben.

Was ein quadratischer Rest ist

Eine Zahl a ist ein quadratischer Rest modulo m, wenn es eine ganze Zahl x gibt, deren Quadrat beim Teilen durch m denselben Rest wie a lässt. Anders gesagt: a hat modulo m eine Quadratwurzel. Modulo 7 ergibt 3 zum Quadrat 9, und 9 lässt den Rest 2, also ist 2 ein Quadrat, mit den Wurzeln 3 und 4. Die 3 dagegen erreicht kein Quadrat. Bei einer Primzahl hat jeder von null verschiedene Rest entweder zwei Wurzeln oder keine, bei zusammengesetzten Moduln können es mehr sein.

So prüft der Rechner und typische Fehler

Zuerst wird a auf seinen Rest zwischen 0 und m − 1 zurückgeführt, auch wenn a negativ oder größer als m ist. Dann probiert der Rechner jedes x in diesem Bereich genau einmal aus und sammelt alle Treffer. So beantwortet er nicht nur Ja oder Nein, sondern nennt jede Wurzel. Der Modul muss zwischen 2 und einer Million liegen. Ein häufiger Fehler ist, nur eine Wurzel zu notieren und die zweite zu vergessen; ein anderer, die 0 zu übersehen, die stets ein Quadrat ist.

Was quadratische Residualität für allgemeine Moduln bedeutet

In der elementaren Zahlentheorie bedeutet ein quadratischer Rest modulo einer Primzahl p üblicherweise eine ganze Zahl a, die nicht durch p teilbar ist und für die die Kongruenz x zum Quadrat gleich a modulo p eine Lösung hat; null wird oft gesondert als das triviale Quadrat besprochen. Für einen zusammengesetzten Modul m erweitert sich dieselbe Definition sauber: a ist ein quadratischer Rest modulo m, wenn mindestens eine ganze Zahl x existiert mit x zum Quadrat kongruent zu a modulo m, einschließlich des Falls a kongruent null.

Lösungen folgen Mustern, die von der Primzahlpotenz-Faktorisierung von m abhängen; zum Beispiel gibt es modulo einer Primzahl entweder null oder zwei von null verschiedene Wurzeln für jede von null verschiedene Restklasse, die ein Quadrat ist, während zusammengesetzte Moduln mehr Wurzeln zulassen können. Klassische Werkzeuge wie Legendre- und Jacobi-Symbole liefern schnelle Tests, wenn m eine ungerade Primzahl ist oder wenn Sie nur einen multiplikativen Charakter brauchen, listen aber nicht von selbst jede Wurzel für beliebiges m auf.

Ein direkter Scan von x von null bis m minus eins wertet jede Quadratklasse genau einmal aus und beantwortet daher sowohl Existenz als auch Aufzählung für jeden Modul innerhalb einer festen Größenschranke.

Wo modulare Quadratprüfungen in der echten Arbeit auftauchen

Wettbewerbsprogrammierer brauchen oft ein schnelles Orakel, bevor sie Tonelli–Shanks oder eine CRT-Kombination von Primzahlpotenz-Wurzeln aufrufen: ist das Restbit falsch, lohnt es nicht, eine Quadratwurzel zu konstruieren. Kryptographie-Studierende prüfen Beispiele für Rabin-artige Chiffren, Übungen zur quadratischen Reziprozität und Spielzeug-Diffie–Hellman-Varianten, die Restsymbole erwähnen. Ingenieure, die periodische Pläne oder Hash-Bucket-Experimente abgleichen, fragen manchmal, ob ein Schritt eine Quadratklasse modulo einer zusammengesetzten Periode ist.

Wenn Sie nur Ja-oder-Nein im Stil des Legendre-Symbols für eine große Primzahl jenseits der Scan-Grenze brauchen, faktorisieren oder reduzieren Sie zuerst; innerhalb der Obergrenze ist diese Seite die vollständige konstruktive Antwort.