gpt4 book ai didi

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

转载 作者:太空宇宙 更新时间:2023-11-03 11:57:06 27 4
gpt4 key购买 nike

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)进一步加快速度?有没有更好的办法?

最佳答案

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

关于python - 用于 Lucas-Lehmer 素数测试的更快的按位模数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5393420/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com