费马小定理

$a^{p-1}\equiv 1 \pmod p$

Miller-Rabin

多次检验是否有 $b\in[2,n-1]$ 满足 $b^{n-1}\equiv 1 \pmod n$

然而存在卡迈尔克数,因此正确性无法保证

于是加上二次探测定理

二次探测定理

$x^2\equiv 1 \pmod p$

$(x+1)(x-1)\equiv 1 \pmod p$

得到

$x\equiv 1 ||x\equiv p-1 \pmod p$

有什么用呢,可以把 $b^{n-1}\equiv 1 \pmod n$ 两个分解一下,