Quadratrest-Prüfer (Legendre-/Jacobi-Symbole)

Quadratrest-Prüfer (Legendre-/Jacobi-Symbole) | Kostenloses Online-Tool | Elysia Tools

Leitfaden zur Tool-Nutzung

Erfahren Sie, wann dieses Tool passt, was es unterstützt und wie Nutzer es anwenden.

Wichtige Fakten

Kategorie: Math & Numbers
Eingabetypen: text, checkbox
Ausgabetyp: text
Sample-Abdeckung: 4
API bereit: Ja

Überblick

Der Quadratrest-Prüfer bestimmt über Legendre- und Jacobi-Symbole, ob eine Zahl modulo eines ungeraden Moduls ein quadratischer Rest ist, und ermittelt bei Primzahlen direkt die modularen Quadratwurzeln.

Wann verwenden

Wenn Sie prüfen müssen, ob die modulare Kongruenz x² ≡ a (mod n) eine ganzzahlige Lösung besitzt.
Wenn Sie modulare Quadratwurzeln modulo einer Primzahl mittels Tonelli–Shanks-Algorithmus berechnen möchten.
Wenn Sie das Legendre- oder Jacobi-Symbol (a/n) für zahlentheoretische Aufgaben oder kryptografische Prüfungen bestimmen wollen.

So funktioniert es

1Das Tool reduziert den Eingabewert a modulo des ungeraden Moduls n und prüft n mit einem deterministischen Miller-Rabin-Test auf Primalität.
2Es berechnet das Jacobi-Symbol (bzw. das Legendre-Symbol, falls n prim ist) zur Bestimmung des quadratischen Rest-Status.
3Ist n eine Primzahl und a ein Quadratrest, berechnet der Tonelli–Shanks-Algorithmus (oder die direkte Formel für n ≡ 3 mod 4) die Wurzeln ±√a mod n.
4Ist n zusammengesetzt und n ≤ 10⁵, klärt eine automatische Erschöpfungssuche (Brute Force), ob trotz eines positiven Jacobi-Symbols tatsächlich eine Wurzel existiert.

Anwendungsfälle

Lösen von quadratischen Kongruenzen in universitären Zahlentheorie- und Algebra-Übungen.
Implementierung und Verifikation kryptografischer Protokolle wie Rabin-Kryptosystemen oder Null-Wissen-Beweisen.
Schnelle Primzahl- und Residuumsanalyse bei modularen Arithmetik-Algorithmen.

Beispiele

1. Quadratische Wurzel modulo Primzahl bestimmen

Mathematikstudent

Hintergrund

In einer Zahlentheorie-Aufgabe soll die Lösbarkeit von x² ≡ 10 (mod 13) untersucht und die Wurzeln bestimmt werden.

Aufgabe

Überprüfen, ob 10 ein Quadratrest modulo 13 ist, und die exakten Werte für x finden.

Verwendung

Geben Sie '10' für a und '13' für n ein und aktivieren Sie das Häkchen für das Lösen der Wurzeln.

a = 10, n = 13, solveRoots = true

Ergebnis

Das Legendre-Symbol ergibt 1, und der Tonelli–Shanks-Algorithmus gibt die Lösungen x = 6 und x = 7 modulo 13 aus.

2. Prüfung bei zusammengesetztem Modul

Kryptografie-Entwickler

Hintergrund

Ein Entwickler untersucht das Verhalten von Pseudoresten modulo einer zusammengesetzten Zahl n = 15.

Aufgabe

Herausfinden, ob x² ≡ 2 (mod 15) lösbar ist, obwohl das Jacobi-Symbol (2/15) gleich 1 ist.

Verwendung

Geben Sie '2' für a und '15' für n ein.

FAQ

Was bedeutet ein Jacobi-Symbol von +1 bei zusammengesetzten Zahlen?

Ein Wert von +1 ist nur eine notwendige Bedingung: Die Zahl kann ein Quadratrest sein, muss es bei zusammengesetztem Modul aber nicht.

Welche Einschränkungen gelten für den Modul n?

Der Modul n muss eine ungerade Ganzzahl im Bereich von 3 bis 10¹⁸ sein.

Wie werden quadratische Reste bei Primzahlen gelöst?

Das Tool verwendet das Euler-Kriterium zur Prüfung und den Tonelli–Shanks-Algorithmus zur expliziten Wurzelberechnung.

Bis zu welcher Größe kann die Zahl a eingegeben werden?

Der Wert a kann sehr groß sein (bis 10⁵¹²) und wird vor der Auswertung automatisch modulo n reduziert.

Beweist ein Symbolwert von −1 immer, dass kein Rest vorliegt?

Ja, sowohl bei primem als auch bei zusammengesetztem Modul beweist das Symbol −1 definitiv, dass a kein Quadratrest modulo n ist.

a = 2, n = 15, solveRoots = true

Dieses Tool ausführen

Beispiele zu diesem Tool

Mit verwandten Tools und Themen fortfahren

Erfahren Sie, wann dieses Tool passt, was es unterstützt und wie Nutzer es anwenden.

Wichtige Fakten

Überblick

Wann verwenden

So funktioniert es

Anwendungsfälle

Beispiele

1. Quadratische Wurzel modulo Primzahl bestimmen

2. Prüfung bei zusammengesetztem Modul

FAQ

Web Python Bildverarbeitung Beispiele

Android Java Bildverarbeitungsbeispiele

Android Kotlin Bildverarbeitungsbeispiele

Web Rust Bildverarbeitungsbeispiele

Säure-Basen-Analyse des Blutgases (AG / ΔAG)

Primitivwurzel-Suche modulo n

Pneumonie-Schweregrad-Vergleich (CURB-65 / PSI / SMART-COP)

DNA-Konzentrationsrechner (A260-Absorption)