论坛 › HugeCalc › 郭有没有兴趣做出一个确定性的素性检测函数

无心人 发表于 2010-7-3 08:45:04

郭有没有兴趣做出一个确定性的素性检测函数

如果输入数字在16位内，现有的HugeCalc应该是确定性检测

郭是否有兴趣做出个小数字的确定性素性检测算法
毕竟，小数字的算法在运行时间上不是很多
（指的是100位左右的数字）

也有成熟的算法可以采用

无心人 发表于 2010-7-3 08:46:21

另外，今天在高德纳的书上看到，
假设有$n$，已经排除$root{3}{n}$内素因子
且通过麦森测试，则，肯定是素数

qianyb 发表于 2010-7-3 08:59:19

无心人，麦森测试是指什么，能说说详细内容吗

mathematica 发表于 2010-7-3 14:33:59

我想郭没兴趣，我觉得也没有必要，现在的概率测试办法应该说已经接近完美了，比如pari/gp的ispseudoprime函数

无心人 发表于 2010-7-3 15:10:28

呃，确定性素性检测算法

gxqcn 发表于 2010-7-5 08:15:51

我现在仅有原始论文可参考，可有更优化的代码或详细的文档供参考？
因为我看到不同的实现可对算法复杂度略有降低，而这个过程是非常耗精力的。

无心人 发表于 2010-7-5 09:33:20

主要有四个算法
一个是椭圆曲线ECPP算法
一个是基于费马测试的，需要分解整数
一个是雅克比和算法
一个就是有名的AKS了

我倾向于实现第三个算法

无心人 发表于 2010-7-5 09:39:38

http://wenku.baidu.com/view/0c21adeb19e8b8f67c1cb9a2.html
这个已经很有操作性了

无心人 发表于 2010-7-8 08:29:06

Miller-Robin测试，我建议，你用3做底，似乎比2的例外比例低

gxqcn 发表于 2010-7-8 08:49:10

用2的优点是快。

查看完整版本: 郭有没有兴趣做出一个确定性的素性检测函数