是由CMU的教授Miller在1976年依据广义黎曼猜想（GRH）提出的一个算法
如果广义黎曼猜想成立，那这就是个确定性质数验证算法
当前广义黎曼猜想还没有被证明，这个算法只能算是概率性验证
如果猜想成立，那这个算法时间复杂度是已知确定性验证算法中最低的
这儿用python具体实现下优化的Miller test
根据输入n的大小分段选择验证方法能更高效
在执行复杂度较高检验前先过个小质数序列的筛，这样大量含小因数的n就直接被判别了
还有用头几个小质数序列做基执行Miller Rabin检验，可以在出现首个伪素数范围内形成确定性验证
from itertools import takewhile
from gmpy2 import mpz, ceil, log, is_strong_prp
initial_prime_number_list = (2, 3, 5, 7, 11, 13) #Must be a continuous sequence of prime numbers starting from 2
strong_pseudoprime_list = (2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051, 3825123056546413051, 3825123056546413051, 318665857834031151167461, 3317044064679887385961981) #https://arxiv.org/pdf/1207.0063.pdf; https://oeis.org/A014233
strong_pseudoprime = strong_pseudoprime_list[len(initial_prime_number_list) - 1] #ψ6
def miller_test(n):
if n <= initial_prime_number_list[-1]:
if n in initial_prime_number_list:
return True
else:
return False
elif n <= initial_prime_number_list[-1] ** 2:
if all(map(lambda p: (n % p) != 0, takewhile(lambda x: x * x <= n, initial_prime_number_list))):
return True
else:
return False
elif any(map(lambda p: (n % p) == 0, initial_prime_number_list)):
return False
elif n < strong_pseudoprime:
if all(map(lambda a: is_strong_prp(n, a), initial_prime_number_list)):
return True
else:
return False
else:
m = mpz(ceil((log(n) ** 2) * 2))
if all(map(lambda a: is_strong_prp(n, a), range(2, m + 1))):
return True
else:
return False
n = int(input('请输入一个要检验的正整数：'))
if miller_test(n):
print(f'{n}是质数')
else:
print(f'{n}是非质数')
