tsk*_*zzy 5 algorithm math primes
我知道在实践中使用了许多素性测试算法(Eratosthenes的Sieve,Fermat的测试,Miller-Rabin,AKS等).然而,它们要么是缓慢的(例如筛子),要么是概率的(Fermat和Miller-Rabin),要么是相对难以实施的(AKS).
确定数字是否为素数的最佳确定性解决方案是什么？
请注意,我主要(双关语)有兴趣测试大约32位(也许是64位)的数字.因此,不需要强大的解决方案(适用于更大的数字).
Mys*_*ial 11
最多~2^30你可以用暴力破解审判分力量.
最多3.4*10^14,拉宾-米勒第7个素数已被证明是确定性的.
在此之上,你是独立的.没有已知的亚立方确定性算法.
编辑:我记得这个,但直到现在我才找到参考:
http://reference.wolfram.com/legacy/v5_2/book/section-A.9.4
PrimeQ首先使用小素数测试可分性,然后使用Miller-Rabin强伪测试基2和基3,然后使用Lucas测试.
截至1997年,已知该程序仅对于正确的程序是正确的
n < 10^16,并且可以想象,对于更大的程序,n它可以声称复合数是素数.
因此,如果你实施Rabin-Miller和Lucas,你的身高可达10 ^ 16.
| 归档时间： |
|
| 查看次数： |
1255 次 |
| 最近记录： |