Legendre Symbol
Das Legendre-Symbol (a/p) entscheidet, ob a ein quadratischer Rest modulo einer Primzahl p ist: 1 (ja), -1 (nein) oder 0 (p|a).
Zweck
Entscheidung der Lösbarkeit quadratischer Gleichungen modulo einer Primzahl; Grundlage des Tonelli-Shanks-Algorithmus.
Mechanismus
(a/p) = a^((p-1)/2) mod p (Euler-Kriterium). Eigenschaften: (ab/p)=(a/p)(b/p), und (a/p)*(a/q) unterliegt dem quadratischen Reziprozitätsgesetz. Es entscheidet, ob x^2≡a (mod p) eine Lösung besitzt.
Anwendungsfälle
- Prüfung quadratischer Reste
- Zahlentheoretische Algorithmen
- Kryptografie
Verwandte Tools
Modulare Exponentiation
Modular Exponentiation — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG
Legendre-Symbol
Legendre Symbol — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG
Jacobi-Symbol
Jacobi Symbol — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG
Kronecker-Symbol
Kronecker Symbol — reines Client-seitiges Tool. Datenschutz zuerst, kein Server-Roundtrip. WERKZEUG