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

概述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)" 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次迭代此模数运算,每次迭代都呈指数增长,因此需要进行优化.

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

解决方法 我能找到的最好的改进是从模数函数中完全去除Mp =(1

Mp：而不是n.bit_length()> p：还节省了一些时间.

)-1,并在开始l-l测试的迭代之前在l-l函数中预先计算它.使用while> 总结

以上是内存溢出为你收集整理的python – Lucas-Lehmer素性测试的快速按位模数全部内容，希望文章能够帮你解决python – Lucas-Lehmer素性测试的快速按位模数所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。