@[GI录像机](/user/142969) 因为如果存在 $a ^ 2\equiv 1\pmod p$ 满足 $a\neq \pm 1$，那么 $p$ 是合数。
by Alex_Wei @ 2022-06-23 09:14:27
当出现 $a ^ c \equiv -1$ 的情况，说明 $a ^ {2c} \equiv 1$ 由 $-1$ 平方得到。
相反，如果 $a ^ c$ 不是 $\pm 1$，说明 $a ^ {2c} \equiv 1$ 不由 $\pm 1$ 平方得到， $n$ 必然是合数。
by Alex_Wei @ 2022-06-23 09:18:47
@[Alex_Wei](/user/123294) 是不是因为一旦出现 $a^2\equiv n-1(\bmod p)$ 就不满足二次探测定理的前提也就是 $a^2\equiv 1(\bmod p)$，无法继续探测？
by GI录像机 @ 2022-06-23 09:19:33
@[GI录像机](/user/142969) 感觉可以这么理解
by Alex_Wei @ 2022-06-23 09:20:11
$n$ 改成 $p$
by GI录像机 @ 2022-06-23 09:20:32
@[Alex_Wei](/user/123294) 谢谢大佬，懂了
by GI录像机 @ 2022-06-23 09:20:53
@[GI录像机](/user/142969) 你考虑 $d$ 不断除以 $2$ 的过程，$a ^ d$ 只有两种情况：
- $1, 1, \cdots, 1, -1, \cdots$。
- $1, 1, \cdots, 1, x, \cdots$ 其中 $x\neq \pm 1$。
后者一定是合数。
by Alex_Wei @ 2022-06-23 09:21:17
还有这种写法有点劣，多了一个 $\log$。
by Alex_Wei @ 2022-06-23 09:21:43
一种比较好看的且少个log的 Miller_Rabin
```cpp
bool test(int n,int a,int d)
{
if(n==2)return true;
if(n==a || n%2==0)return false;
while(d%2==0)d>>=1;
int t=bin_pow(a,d,n);
while(d!=n-1 && t!=n-1 && t!=1)
{
t=(__int128)t*t%n;
d*=2;
}
return t==n-1 || d%2==1;
}
bool is_prime(int n)
{
const int a[]={2,3,5,7};
for(int i=0;i<=3;i++)
{
if(n==a[i])return true;
if(n%a[i]==0)return false;
if(!test(n,a[i],n-1))return false;
}
return true;
}
```
by Smile_Cindy @ 2022-06-23 09:46:44