欧拉准则（Euler's Criterion）又称欧拉判别准则，主要用途是判断一个数 n 是否是另一个奇质数 p 的二次剩余。
对任意整数 aa，
ap−12≡(ap)(modp)a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)\pmod p
进一步，我们有推论：
- (1p)=1 \left(\dfrac{1}{p}\right)=1
- (−1p)=(−1)p−12={1,p≡1(mod4),−1,p≡3(mod4). \begin{aligned} \left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}} =\begin{cases} 1, & p\equiv 1\pmod 4,\\ -1, & p\equiv 3\pmod 4. \end{cases} \end{aligned}
求解 -1 模 p 的二次剩余，当 p 为 4k+1 型
((p−12)!)2≡−1(modp)((\frac{p-1}{2})!)^2\equiv -1 \pmod p