Legendre Symbol
El símbolo de Legendre (a/p) determina si a es un residuo cuadrático módulo un primo p: 1 (sí), -1 (no) o 0 (p|a).
Propósito
Decidir la resolubilidad de ecuaciones cuadráticas módulo un primo; la base del algoritmo Tonelli-Shanks.
Mecanismo
(a/p) = a^((p-1)/2) mod p (criterio de Euler). Propiedades: (ab/p)=(a/p)(b/p), y (a/p)*(a/q) se rige por la reciprocidad cuadrática. Decide si x^2≡a (mod p) tiene solución.
Casos de uso
- Comprobación de residuos cuadráticos
- Algoritmos de teoría de números
- Criptografía
Herramientas relacionadas
Exponenciación modular
Modular Exponentiation — herramienta 100% del lado del cliente. Privacidad primero, sin round-trip al servidor. HERRAMIENTA
Símbolo de Legendre
Legendre Symbol — herramienta 100% del lado del cliente. Privacidad primero, sin round-trip al servidor. HERRAMIENTA
Símbolo de Jacobi
Jacobi Symbol — herramienta 100% del lado del cliente. Privacidad primero, sin round-trip al servidor. HERRAMIENTA
Símbolo de Kronecker
Kronecker Symbol — herramienta 100% del lado del cliente. Privacidad primero, sin round-trip al servidor. HERRAMIENTA