Quadratische Nichtreste mod p

Ein quadratischer Nichtrest modulo einer ungeraden Primzahl p ist eine von null verschiedene Restklasse a, für die die Kongruenz x zum Quadrat kongruent a modulo p keine ganzzahlige Lösung besitzt. Für jede ungerade Primzahl ist genau die Hälfte der von null verschiedenen Klassen Reste und die andere Hälfte Nichtreste; die vollständige Liste der Nichtreste ist daher eine konstruktive Antwort und kein bloßes Ja oder Nein. Studierende, Wettbewerbsprogrammierer und Lernende der Kryptographie benötigen oft die gesamte Menge für Tabellen, stichprobenartige Legendre-Symbol-Prüfungen und Lehrbeispiele, bevor sie schwerere Verfahren zur modularen Quadratwurzel aufrufen. Diese Fähigkeit nimmt eine einzige ungerade Primzahl p entgegen, prüft die Primzahl-Eigenschaft, markiert jede Quadratklasse durch einen deterministischen Durchlauf und liefert die sortierte Liste der Nichtreste von eins bis p minus eins zusammen mit den theoretischen Anzahlen.

Was ein quadratischer Nichtrest ist

Rechnet man modulo einer ungeraden Primzahl p, bleiben beim Teilen nur die Reste 0 bis p − 1 übrig. Manche davon entstehen, wenn man eine ganze Zahl quadriert und durch p teilt: Das sind die quadratischen Reste. Alle übrigen von null verschiedenen Reste heißen Nichtreste, denn keine Zahl im Quadrat trifft sie. Modulo 7 ergeben die Quadrate nur 1, 2 und 4, deshalb sind 3, 5 und 6 Nichtreste. Das Legendre-Symbol beantwortet diese Frage für eine einzelne Zahl mit plus oder minus eins, diese Liste zeigt dagegen die ganze Menge auf einmal.

Wie die Liste entsteht und typische Fehler

Der Rechner prüft zuerst, ob p wirklich eine ungerade Primzahl zwischen 3 und 100.000 ist. Danach markiert er jeden Rest, der als Quadrat vorkommt, und gibt die nicht markierten aufsteigend aus. Zur Kontrolle stehen daneben die Zahl der Reste und die erwartete Anzahl (p − 1)/2. Häufige Fehler sind, die 0 mitzuzählen, eine zusammengesetzte Zahl wie 9 oder 15 zu verwenden oder die 2 einzugeben: Solche Eingaben werden abgelehnt, statt eine falsche Tabelle zu liefern.

Quadratische Nichtreste und warum die Liste die Hälfte von 1..p−1 ist

Fixieren Sie eine ungerade Primzahl p. Für jede durch p nicht teilbare ganze Zahl a hat das Polynom X zum Quadrat minus a im Körper der ganzen Zahlen modulo p entweder zwei Wurzeln oder keine. Klassen mit Wurzeln sind die von null verschiedenen quadratischen Reste; Klassen ohne Wurzeln sind die quadratischen Nichtreste.

Null ist stets ein Quadrat (Null zum Quadrat), und Lehrbücher behandeln sie üblicherweise getrennt von der Partition in von null verschiedene Reste und Nichtreste. Die multiplikative Struktur erzwingt ein perfektes Gleichgewicht: die Abbildung, die x auf x zum Quadrat in der multiplikativen Gruppe der Ordnung p minus eins sendet, ist zwei-zu-eins auf eine Untergruppe vom Index zwei, sodass es genau (p minus eins) durch zwei Reste und dieselbe Anzahl Nichtreste gibt.

Klassische kleine Tabellen bestätigen die Anzahl: modulo sieben sind die von null verschiedenen Quadrate eins, zwei und vier, also sind die Nichtreste drei, fünf und sechs; modulo elf sind die Nichtreste zwei, sechs, sieben, acht und zehn. Das Legendre-Symbol codiert dieselbe Partition als plus eins oder minus eins, aber ein einzelnes Symbol zählt die gesamte Menge nicht auf.

Wo vollständige Nichtrest-Listen in der Praxis vorkommen

Wettbewerbsprogrammierer nutzen die Menge als Orakel, wenn sie Generatoren bauen, die Nichtreste für Hash-Tests oder Gegenbeispiele zu naiven Quadratwurzel-Vermutungen ziehen. Kryptographie-Studierende prüfen Lehrbuchaussagen über die Größe der Nichtrest-Menge, bevor sie quadratische Reziprozität, das Euler-Kriterium oder Rabin-ähnliche Chiffren studieren, die von der Reststruktur abhängen. Ingenieure, die Eigenschaftstests für modulare Arithmetik-Helfer schreiben, können behaupten, dass das Komplement ihres Restfinders mit dieser Liste für jede ungerade Primzahl bis zu einer bescheidenen Schranke übereinstimmt.

Wenn Sie nur ein Legendre-Symbol oder ein Ja-oder-Nein für ein a modulo einem allgemeinen Modul brauchen, bevorzugen Sie die Geschwister-Werkzeuge für Reste und Symbole; diese Seite ist der vollständigen Nichtrest-Liste einer ungeraden Primzahl gewidmet.