Miller test算法——验证 一个数是否为质数

是由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}是非质数')