普遍意义下的素性概率测试的基序列选择问题
考虑通常大小的整数的素性概率测试，整数范围小于10^1000使用Miller-Rabin测试
我们是否有理由相信
基于$2^n-+ 1$的素数序列能给出比通常的素数序列更好的测试效果
既速度快，又测试次数少？
序列2, 3, 5, 7, 17, 31, 127, 257, 8191, 65537 , 131071, 524287, 2147483647......
如果结论不是
那是否存在一个整数链，在相同范围内，比其他序列，能得到较少的测试次数 实践证实，单纯用Miller-Rabin测试并不高效，也不保险，
最好同时结合其它素性检测算法，
此时Miller-Rabin仅需用2（及3）为基检测即可。 好像其他算法也不多
就一个多项式算法
至于那个确定性的
则时间复杂度有点大哦 那个AKS算法，据说如果可以证明一条相关的数论猜想，就可以改进到O(log^{3}(n)). $O(log^{3}(n))$.
不见得时间就少啊 Bailli-PSW测试
* Process all N < 3 and all even N.
* Check N for any small prime divisors p < 1000.
* Perform a Miller-Rabin (strong probable prime) test, base 2, on N.
* Perform a (standard or strong) Lucas-Selfridge test on N, using Lucas sequences with the parameters suggested by Selfridge. http://epub.cnki.net/GRID2008/docdown/pubdownload.aspx?dk=U_WEEvREdiSUtucElBV1RWb0xxUGFhOEFBWC9sR0xjaDdpbDlHaXc9PQ_F_2005102117.nh_P_D_nhdown
单参数二次基伪素数的初步研究
全文共 32 页
每页 0.5 元(RMB)
产品为 无折扣
共：32 页 * 0.5 元(RMB) = 16 元(RMB)
您的帐户现余额 0 元(RMB)
券余额 0 元(RMB)
您的帐户余额不足，请充值！ 知网能申请 个人馆， 一天下载10篇
一共能下载15天
赶快上去下载有用的论文
www.cnki.com 超强伪素数及素性检验加速算法
http://epub.cnki.net/grid2008/detail.aspx?filename=ZSDZ200402007&dbname=CJFQ2004
嵌入式系统中大素数的快速生成
http://epub.cnki.net/grid2008/detail.aspx?filename=JSJC200305009&dbname=CJFQ2003
Selfridge猜想与伪素数的判别
http://epub.cnki.net/grid2008/detail.aspx?filename=FMSB200003003&dbname=CJFQ2000 拿一堆素数乘到一块，搞一把完活
页:
[1]