数学研发论坛

 找回密码
 欢迎注册
查看: 12312|回复: 73

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

[复制链接]
发表于 2010-7-3 08:45:04 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

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

也有成熟的算法可以采用
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-3 08:46:21 | 显示全部楼层
另外,今天在高德纳的书上看到,
假设有$n$,已经排除$root{3}{n}$内素因子
且通过麦森测试,则,肯定是素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-3 08:59:19 | 显示全部楼层
无心人,麦森测试是指什么,能说说详细内容吗
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-3 14:33:59 | 显示全部楼层
我想郭没兴趣,我觉得也没有必要,现在的概率测试办法应该说已经接近完美了,比如pari/gp的ispseudoprime函数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-3 15:10:28 | 显示全部楼层
呃,确定性素性检测算法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-5 08:15:51 | 显示全部楼层
我现在仅有原始论文可参考,可有更优化的代码或详细的文档供参考?
因为我看到不同的实现可对算法复杂度略有降低,而这个过程是非常耗精力的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-5 09:33:20 | 显示全部楼层
主要有四个算法
一个是椭圆曲线ECPP算法
一个是基于费马测试的,需要分解整数
一个是雅克比和算法
一个就是有名的AKS了

我倾向于实现第三个算法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-5 09:39:38 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 08:29:06 | 显示全部楼层
Miller-Robin测试,我建议,你用3做底,似乎比2的例外比例低
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 08:49:10 | 显示全部楼层
用2的优点是快。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-11-14 04:07 , Processed in 0.083240 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表