python – Lucas-Lehmer素性测试的快速按位模数

使用按位运算可以大大加快速度(参见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次迭代此模数运算,每次迭代都呈指数增长,因此需要进行优化.

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