素性检验 - Miller-Rabin Test

由费马小定理可以知道,如果$p$是一个素数,且$(x, p)=1$,我们可以得到: $$\begin{aligned} x^{p-1} \equiv 1 \pmod{p} \end{aligned}$$ 那么反之,如果有$x$满足$\forall a>1,(a,x)=1,s.t. a^x \equiv 1 \pmod{x}$,这样的$x$一定是素数吗? ...

July 4, 2021 · 4 min · Kenshin2438