Miller-Rabin 算法
Abeeel51
2023-10-25 15:59:29
以下是 $\text{Miller-Rabin}$ 算法的基本步骤：
1. **选择待测试的整数 $n$**：首先选择一个大于 $1$ 的整数 $n$，以确定它是否为素数。
2. **将 $n - 1$ 分解为 $2^t * u$**：计算 $n - 1$ 的质因数分解，其中 $u$ 是一个奇数，$t$ 是非负整数，表示因子 $2$ 的个数。
3. **选择随机证据数 $a$**：从区间 $[2, n - 2]$ 中随机选择一个整数 $a$。
4. **计算 $v = a^u \mod n$**：计算 $a$ 的 $u$ 次幂对 $n$ 取模，得到 $v$。
5. **检查 $v$ 是否等于 $1$**：
- 如果 $v = 1$，那么继续下一轮测试，选择新的随机证据数 $a$。
- 如果 $v$ 不等于 $1$，转到下一步。
6. **重复平方检测 $t$ 次**：
- 对 $v$ 进行 $t$ 次平方操作 $(v = v^2 \mod n)$，同时检查 $v$ 是否等于 $n - 1$。
- 如果 $v = n - 1$，继续下一轮测试，选择新的随机证据数 $a$。
- 如果 $v$ 不等于 $n - 1，$继续平方操作并检查，最多进行 $t - 1$ 次。
7. **检查最终结果**：
- 如果在 $t$ 次平方检测后，$v$ 仍然不等于 $n - 1$，那么 $n$ 被认为不是素数，可以确定是合数。
- 如果 $v$ 在 $t$ 次检测后等于 $n - 1$，那么 $n$ 可能是素数，继续下一轮测试。
8. **重复多次测试**：重复以上步骤，选择不同的随机证据数 $a$ 进行测试。通常，重复测试足够多次可以提高算法的准确性。
总结：$\text{Miller-Rabin}$ 算法的可靠性取决于迭代次数和随机证据数的选择。通常情况下，进行多次测试（例如，$15$ 次或更多），选择随机证据数，可以使算法在实践中高度可靠，但仍然是一个随机性算法。因此，虽然它可以快速排除大多数合数，但不能提供绝对的证明。
Code:
```python
import random
def millerRabin(n):
if n<3 or n%2==0:
return n==2
u,t=n-1,0
while u%2==0:
u=u//2
t=t+1
test_time=8
for i in range(test_time):
a=random.randint(2,n-1)
v=pow(a,u,n)
if v==1:
continue
s=0
while s<t:
if v==n-1:
break
v=v*v%n
s=s+1
if s==t:
return False
return True
t=int(input())
for i in range(t):
x=int(input())
y=millerRabin(x)
if y==True:
print("YES")
if y==False:
print("NO")
```