经过很长一段时间的休息后，我又回到了编程领域，所以请原谅任何愚蠢的错误/低效的代码。我正在创建一个使用 RSA 加密方法的加密程序，该方法涉及查找数字的互质来生成密钥。我使用欧几里得算法生成最大公因数，然后如果 HCF == 1，则将互质添加到列表中。我为不同的数字生成两个互质列表，然后进行比较以找到两个集合中的互质。基本代码如下：def gcd(a, b): while b: a,b=b,a%b return adef coprimes(n): cp = [] for i in range(1,n): if gcd(i, n) == 1: cp.append(i) print(cp)def compare(n,m): a = coprimes(n) b = coprimes(m) c = [] for i in a: if i in b: c.append(i) print(c)该代码非常适合小数字，并为我提供了我想要的东西，但执行需要很长时间，并且最终Killed在计算数十亿范围内的极大数字时，这对于中等级别的安全性也是必要的。我认为这是一个内存问题，但我无法弄清楚如何以非内存密集型方式执行此操作。我尝试了多处理，但这只是使我的计算机由于运行的进程数量而无法使用。如何计算大数的互质，然后以有效且可行的方式比较两组互质？
2 回答
慕后森
TA贡献1802条经验 获得超5个赞
如果您唯一担心的是内存不足，您可以使用生成器。
def coprimes(n):
for i in range(1,n):
if gcd(i, n) == 1:
yield i
这样您就可以使用互质值，然后在不需要时将其丢弃。然而，没有什么可以改变你的代码是 O(N^2) 并且对于大素数总是执行缓慢的事实。这假设欧几里得算法是恒定时间的，但事实并非如此。
小怪兽爱吃肉
TA贡献1852条经验 获得超1个赞
您可以改变策略并从共同素因数的角度来解决这个问题。n 和 m 之间的公共互质将是不能被任何公共质因数整除的所有数字。
def primeFactors(N):
p = 2
while p*p<=N:
count = 0
while N%p == 0:
count += 1
N //= p
if count: yield p
p += 1 + (p&1)
if N>1: yield N
import math
def compare2(n,m):
# skip list for multiples of common prime factors
skip = { p:p for p in primeFactors(math.gcd(n,m)) }
for x in range(1,min(m,n)):
if x in skip:
p = skip[x] # skip multiple of common prime
m = x + p # determine next multiple to skip
while m in skip: m += p # for that prime
skip[m] = p
else:
yield x # comon coprime of n and m
性能比匹配互质列表要好得多，尤其是在较大的数字上：
from timeit import timeit
timeit(lambda:list(compare2(10**5,2*10**5)),number=1)
# 0.025 second
timeit(lambda:list(compare2(10**6,2*10**6)),number=1)
# 0.196 second
timeit(lambda:list(compare2(10**7,2*10**7)),number=1)
# 2.18 seconds
timeit(lambda:list(compare2(10**8,2*10**8)),number=1)
# 20.3 seconds
timeit(lambda:list(compare2(10**9,2*10**9)),number=1)
# 504 seconds
在某些时候，构建所有互质列表会成为瓶颈，您应该在它们从生成器中出来时使用/处理它们（例如计算有多少个）：
timeit(lambda:sum(1 for _ in compare2(10**9,2*10**9)),number=1)
# 341 seconds
解决这个问题的另一种方法是列出 n 和 m 之间的 gcd 的互质数，该方法比质因数方法慢一些，但编码更简单：
import math
def compare3(n,m):
d = math.gcd(n,m)
for c in range(1,min(n,m)):
if math.gcd(c,d) == 1:
yield c
timeit(lambda:list(compare3(10**6,2*10**6)),number=1)
# 0.28 second
timeit(lambda:list(compare3(10**7,2*10**7)),number=1)
# 2.84 seconds
timeit(lambda:list(compare3(10**8,2*10**8)),number=1)
# 30.8 seconds
鉴于它不使用内存资源，因此在某些情况下可能是有利的：
timeit(lambda:sum(1 for _ in compare3(10**9,2*10**9)),number=1)
# 326 seconds
添加回答
举报
0/150
提交
取消