模p平方剩余判断

• METHOD1: 定理

  设$p$为奇素数

  • $\left(\frac{2}{p}\right)={\left(-1\right)}^{\frac{p^2-1}{8}}$

  • 若$\left(a,2p\right)=1$，则$\left(\frac{a}{p}\right)={\left(-1\right)}^{T_{\left(a,p\right)}}$，其中T_{\left(a,p\right)}=\sum_\limits{k=1}^{\frac{p-1}{2}}{\left[\frac{a\cdot k}{p}\right]}

• METHOD2: 二次互反律

  若$p,q$为互素奇素数，则$\left(\frac{p}{q}\right)={\left(-1\right)}^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\left(\frac{p}{q}\right)$