0

我正在尝试为我作为练习编写的 RSA 实现实现素数测试。我主要使用 Rabin-Miller，但我确实有一个埃拉托色尼筛法，制定了一个低于 1000 个素数的列表，用于快速测试以确定候选人是否将其中一个作为素数。

相关功能是：

def comp_test(to_test, primeList):
    for i in primeList:
        if (to_test / float(i)) % 1 == 0:
            return False
    return True

其中 primeList 是 Sieve 生成​​的素数列表。这在 to_test 值为 2^55 左右的情况下非常有效，但超过了这一点

(to_test / float(i)) % 1

语句总是计算为 0.0，即使当我将它交给拉宾米勒确定为素数的 to_test 时也是如此。我不确定这可能是什么。我不太清楚 Python 如何处理非常大的数字，但据我所知 2^55 似乎不会是任何类型的溢出边界。使用 Sieve 时，该功能明显更快，并且为 2048 位实现生成密钥需要一段时间，所以即使这是一个练习，我想看看我是否可以让 Sieve 工作。

提前致谢。

4

2 回答 2

2

Python 只处理浮点数的 53 位精度（大约 16 位小数），因此使用大的浮点数不会很好。

请改用模运算符：

>>> (2**80 / float(3)) % 1  # Doesn't work
    0.0
>>> 2**80 % 3  # Works
    1L
>>> 2**80 % 2  # Works
    0L

它也比除法快很多：

>>> %timeit (2**40 / float(2)) == 0
1000000 loops, best of 3: 224 ns per loop
>>> %timeit 2**40 % 2 == 0        
10000000 loops, best of 3: 53.5 ns per loop

如果i是 的一个因数n，则n % i == 0(n与0模一致i)。

于 2013-04-24T02:12:03.320 回答
0

我建议您使用 GMP 来满足您的大量需求。

以下是我过去在 Python 中完成的一些与主要相关的项目：

http://stromberg.dnsalias.org/svn/primes-below
http://stromberg.dnsalias.org/svn/big-prime
http://stromberg.dnsalias.org/svn/huge-prime
http://stromberg.dnsalias.org/svn/sieve
于 2013-04-24T03:06:19.690 回答