python - 用于 Lucas-Lehmer 素数测试的更快的按位模数

Question

Lucas-Lehmer primality test测试质数以确定它们是否也是 Mersenne primes .瓶颈之一是计算 (s**2 − 2) % (2**p - 1) 时的模运算。

使用按位运算可以大大加快速度(参见 L-L 链接)，目前为止我最好的是:

def mod(n,p):
    """ Returns the value of (s**2 - 2) % (2**p -1)"""
    Mp = (1<<p) - 1
    while n.bit_length() > p: # For Python < 2.7 use len(bin(n)) - 2 > p
        n = (n & Mp) + (n >> p)
    if n == Mp:
        return 0
    else:
        return n

一个简单的测试用例是 p 有 5-9 个数字，s 有 10,000 多个数字(或更多；它们是什么并不重要)。解决方案可以通过 mod((s**2 - 2), p) == (s**2 - 2) % (2**p -1) 进行测试。请记住，在 L-L 测试中需要此模运算的 p - 2 次迭代，每次迭代都以指数方式增加 s，因此需要优化。

有没有办法使用纯 Python(包括 Python 3)进一步加快速度？有没有更好的办法？

Answer 1

我能找到的最好的改进是删除 Mp = (1<<p) - 1完全来自模函数，并在开始 L-L 测试的迭代之前在 L-L 函数中预先计算它。使用 while n > Mp:而不是 while n.bit_length() > p:也节省了一些时间。