素性检验 - 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$一定是素数吗? ...
由费马小定理可以知道,如果$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$一定是素数吗? ...