数学研发论坛

 找回密码
 欢迎注册
查看: 11668|回复: 14

[讨论] 不知道HugeCalc 的判断素数的算法是什么?能够公开下

[复制链接]
发表于 2008-2-1 14:19:39 | 显示全部楼层 |阅读模式

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

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

x
请问是采用哪种算法判断素数的?

猜测应该整合了已经发现的43个梅森素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-1 15:45:37 | 显示全部楼层
判断素数算法有很多现成的资料,可以查看网站:
http://mathworld.wolfram.com/PrimalityTest.html
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-1 16:18:37 | 显示全部楼层
我不是不懂判断,我看过很多判断方法,准备写一篇关于素数判别的,因此想找HugeCalc的方法看看
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-1 17:31:30 | 显示全部楼层
只查看一种方法意义不是很大。
郭老大提供的HugeCalc已经提供了关于大整数运算非常丰富的接口。
如果真要写一篇比较好的文章,不如自己动手利用郭老大的接口自己实现一下各种判断方法,然后测试一下各种方法的速度。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-1 19:32:27 | 显示全部楼层
目前对于大整数,没有一个100%准确的通用的素数判定方法(梅森素数除外) ,目前用的都是证明这个整数是素数的概率为99.999......%的方法,一般都是费马小定理推广的,真正可以准确判别的方法运算量过于大

因此想了解郭老大在判断素数的时候用了什么算法,又做了什么优化?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-1 19:58:50 | 显示全部楼层

请见帮助 HugeCalc.chm 相关页面吧

HugeCalc.chm::HugeCalc 算法库/算法库调用手册/超大整数素性快速检测,里面已经讲得非常透彻详细了,
更具体的则涉及到一些独创部分,暂不打算公开,请见谅。

关于素性检测学问很深,如果不是亲自去实现,还是别淌这个混水为好,不是那么简单滴。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-1 20:41:39 | 显示全部楼层
关于梅森素数:
HugeCalc判断2^1257787-1可以很快判断它是素数,但判断其邻近的质数所生成的书是否梅森素数就要很久,这是为什么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-1 20:46:39 | 显示全部楼层
不知道郭老大有没有想过有威尔逊方法?

一个整数N,如果满足
(N-1)! Mod N=1
这个数肯定是素数

这个方法是100%对的,但是运算量太大,甚至比一个个数去除还慢,有没有人想过去优化这个算法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-1 20:56:32 | 显示全部楼层
这个定理仅有理论价值,没有实用价值,至少在素性判定上。

比如要判定 999979 是否为素数,用最常规的方法都判定出来了,恐怕你的 999978! 还在计算中。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-1 21:02:24 | 显示全部楼层
这个的确只是理论上的,实质意义目前来说还没有

目前的判断素数的方法一般都是根据费马小定理来发展出来的吧

如果N是素数,则:
A^(N-1) Mod N =1
(A是大于2的任何整数)

可惜逆定理不成立,甚至出现了所谓的“伪素数”
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-5-17 07:50 , Processed in 0.052374 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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