Jacobi Symbol
Le symbole de Jacobi étend le symbole de Legendre aux modules composés : pour n=∏p_i, (a/n)=∏(a/p_i).
Objectif
Étendre le test de résidu quadratique aux modules composés, utilisé en test de primalité et algorithmes arithmétiques.
Mécanisme
Il se calcule efficacement via la réciprocité quadratique et les propriétés de Jacobi, sans factoriser n. (a/n)=1 ne garantit pas que a soit un résidu quadratique modulo n (mais -1 prouve que non). Le test de primalité de Solovay-Strassen utilise le symbole de Jacobi.
Cas d’usage
- Tests de primalité
- Résidus quadratiques
- Algorithmes arithmétiques