勒让德符号

Legendre 符号

函数 Legendre(a,p)

返回 $\bigl(\frac{a}{p}\bigr)$,

定义:  $p$ 是一奇素数, $a$ 不能被 $p$ 除尽. 当 $a$ 是数 $p$ 的平方剩余时, 符号 $\bigl(\frac{a}{p}\bigr)$ 表示 $+1$; 当 $a$ 是数 $p$ 的平方非剩余时, 符号 $\bigl(\frac{a}{p}\bigr)$ 表示 $-1$. 

这个符号是勒让德引入的.

勒让德符号的性质

Claim 1.  若 $a\equiv b\pmod p$, 则 $\bigl(\frac{a}{p}\bigr)=\bigl(\frac{b}{p}\bigr)$.

算法:

1.  若 $a > p$, 则计算 $b=a \mod p$.  利用 Claim 1.

关于 Legendre 符号的性质, 见问题2855, 1802, 1751