Jacobi Symbol
El símbolo de Jacobi extiende el símbolo de Legendre a módulos compuestos: para n=∏p_i, (a/n)=∏(a/p_i).
Propósito
Extender la prueba de residuo cuadrático a módulos compuestos, usada en pruebas de primalidad y algoritmos teórico-numéricos.
Mecanismo
Se calcula eficientemente mediante reciprocidad cuadrática y propiedades de Jacobi, sin factorizar n. (a/n)=1 no garantiza que a sea residuo cuadrático módulo n (pero -1 demuestra que no lo es). La prueba de primalidad Solovay-Strassen usa el símbolo de Jacobi.
Casos de uso
- Pruebas de primalidad
- Residuos cuadráticos
- Algoritmos teórico-numéricos