问题与长划分，然后在Python中正确修改

我想实现一个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工作。

在此先感谢。

来源

2013-04-24 Dr. Dudley Eigenvalue D.D.S.

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

使用模运算来代替：

>>> (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-24 02:12:03 Blender

我推荐使用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-24 03:06:19 dstromberg

问题与长划分，然后在Python中正确修改

回答

相关问题