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

无心人 · 发表于 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 ... amp;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

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

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

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

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