Jacobi Symbol
Das Jacobi-Symbol erweitert das Legendre-Symbol auf zusammengesetzte Moduln: für n=∏p_i gilt (a/n)=∏(a/p_i).
Zweck
Die Quadratrest-Prüfung auf zusammengesetzte Moduln ausdehnen, genutzt in Primalitätstests und zahlentheoretischen Algorithmen.
Mechanismus
Es wird effizient über quadratische Reziprozität und Jacobi-Eigenschaften berechnet, ohne n zu faktorisieren. (a/n)=1 garantiert nicht, dass a ein Quadratrest mod n ist (aber -1 beweist das Gegenteil). Der Solovay-Strassen-Primalitätstest nutzt das Jacobi-Symbol.
Anwendungsfälle
- Primalitätstests
- Quadratische Reste
- Zahlentheoretische Algorithmen