普遍意义下的素性概率测试的基序列选择问题

无心人 · 发表于 2008-11-4 08:13:29

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

考虑通常大小的整数的素性概率测试，整数范围小于10^1000 使用Miller-Rabin测试我们是否有理由相信基于$2^n -+ 1$的素数序列能给出比通常的素数序列更好的测试效果既速度快，又测试次数少？序列2, 3, 5, 7, 17, 31, 127, 257, 8191, 65537 , 131071, 524287, 2147483647...... 如果结论不是那是否存在一个整数链，在相同范围内，比其他序列，能得到较少的测试次数

gxqcn · 发表于 2008-11-4 21:21:01

实践证实，单纯用Miller-Rabin测试并不高效，也不保险，最好同时结合其它素性检测算法，此时Miller-Rabin仅需用2（及3）为基检测即可。

无心人 · 发表于 2008-11-5 08:30:43

好像其他算法也不多就一个多项式算法至于那个确定性的则时间复杂度有点大哦

medie2005 · 发表于 2008-11-5 08:39:42

那个AKS算法，据说如果可以证明一条相关的数论猜想，就可以改进到$O(log^{3}(n))$.

无心人 · 发表于 2008-11-5 10:14:14

$O(log^{3}(n))$. 不见得时间就少啊

无心人 · 发表于 2008-11-5 11:39:31

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.

无心人 · 发表于 2008-11-5 15:16:04

http://epub.cnki.net/GRID2008/do ... 02117.nh_P_D_nhdown 单参数二次基伪素数的初步研究全文共 32 页每页 0.5 元(RMB) 产品为无折扣共：32 页 * 0.5 元(RMB) = 16 元(RMB) 您的帐户现余额 0 元(RMB) 　　　　券余额 0 元(RMB) 您的帐户余额不足，请充值！

无心人 · 发表于 2008-11-5 15:23:32

知网能申请个人馆，一天下载10篇一共能下载15天赶快上去下载有用的论文 www.cnki.com

无心人 · 发表于 2008-11-5 15:32:35

超强伪素数及素性检验加速算法 http://epub.cnki.net/grid2008/de ... 007&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

neypal · 发表于 2010-8-7 11:01:32

拿一堆素数乘到一块，搞一把完活

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 普遍意义下的素性概率测试的基序列选择问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。