Legendre Symbol
Legendre 符号 (a/p) 判断 a 是否为模素数 p 的二次剩余：1（是）、-1（否）、0（p|a）。
用途
判断模素数下二次方程可解性，Tonelli-Shanks 算法基础。
机制
(a/p) = a^((p-1)/2) mod p（欧拉判别法）。性质：(ab/p)=(a/p)(b/p)，(a/p)*(a/q) = 二次互反律。用于判断 x^2≡a (mod p) 是否有解。
用例
- 二次剩余判断
- 数论算法
- 密码学
Legendre 符号 (a/p) 判断 a 是否为模素数 p 的二次剩余：1（是）、-1（否）、0（p|a）。
判断模素数下二次方程可解性，Tonelli-Shanks 算法基础。
(a/p) = a^((p-1)/2) mod p（欧拉判别法）。性质：(ab/p)=(a/p)(b/p)，(a/p)*(a/q) = 二次互反律。用于判断 x^2≡a (mod p) 是否有解。