依据黎曼假设的Miller-Riemann素数测试

[TheMatrix]

据说是最快的：

https://www.zhihu.com/question/51236075 ... 5674802272

代码： 全选

import math
#import sympy
#import random

def is_prime_miller_riemann(n):
    if n % 2 == 0:
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for a in range(2, min(n - 2, int(2 * math.log(n)**2)) + 1):
        x = pow(a, d, n)
        for _ in range(s):
            y = pow(x, 2, n)
            if y == 1 and x != 1 and x != n - 1:
                # x是1的非平凡模n平方根，提前终止
                return False
            x = y
        if y != 1:
            # 费马测试失败，提前终止
            return False
    return True

result = is_prime_miller_riemann(10000002039473)  # True 
print(result)

[FoxMe]

不是最快的（可能是确定性算法中最快的）。有其它随机算法更快，也不需要黎曼假设。