Jacobi Symbol
Jacobi 符号推广 Legendre 符号至合数模：对 n=∏p_i，(a/n)=∏(a/p_i)。
用途
推广二次剩余判断至合数模，用于素性测试与数论算法。
机制
用二次互反律与 Jacobi 性质高效计算，无需分解 n。(a/n)=1 不保证 a 是模 n 二次剩余（但 -1 则确定不是）。Solovay-Strassen 素性测试用 Jacobi。
用例
- 素性测试
- 二次剩余
- 数论算法
Jacobi 符号推广 Legendre 符号至合数模：对 n=∏p_i，(a/n)=∏(a/p_i)。
推广二次剩余判断至合数模，用于素性测试与数论算法。
用二次互反律与 Jacobi 性质高效计算，无需分解 n。(a/n)=1 不保证 a 是模 n 二次剩余（但 -1 则确定不是）。Solovay-Strassen 素性测试用 Jacobi。