我想实现一个RSA实现的素性测试,我正在写作excercise。我主要使用Rabin-Miller,但我确实有一个Eratosthenes的Sieve,它列出了一千个以下的所有素数列表,用于快速测试,以确定候选人是否有其中一个素数作为主要因素。问题与长划分,然后在Python中正确修改
相关的功能是:
def comp_test(to_test, primeList):
for i in primeList:
if (to_test/float(i)) % 1 == 0:
return False
return True
凡primeList是由筛生成素数的列表。这工作完全达到2^55左右to_test值,但除此之外点
(to_test/float(i)) % 1
语句始终计算为0.0,甚至当我把它一个to_test的拉宾 - 米勒确定为素数。我不确定这可能是什么。我并不清楚Python如何处理大量数据,但据我所知,2^55似乎并不是任何溢出边界。使用Sieve的功能要快得多,为我2048位实现生成密钥需要一段时间,所以即使这是一个练习,我想看看我是否可以使Sieve工作。
在此先感谢。