不知道HugeCalc 的判断素数的算法是什么？能够公开下

282842712474 · 发表于 2008-2-1 14:19:39

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

×

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

猜测应该整合了已经发现的43个梅森素数

mathe · 发表于 2008-2-1 15:45:37

判断素数算法有很多现成的资料，可以查看网站:
http://mathworld.wolfram.com/PrimalityTest.html

282842712474 · 发表于 2008-2-1 16:18:37

我不是不懂判断,我看过很多判断方法,准备写一篇关于素数判别的,因此想找HugeCalc的方法看看

mathe · 发表于 2008-2-1 17:31:30

只查看一种方法意义不是很大。
郭老大提供的HugeCalc已经提供了关于大整数运算非常丰富的接口。
如果真要写一篇比较好的文章，不如自己动手利用郭老大的接口自己实现一下各种判断方法，然后测试一下各种方法的速度。

282842712474 · 发表于 2008-2-1 19:32:27

目前对于大整数,没有一个100%准确的通用的素数判定方法(梅森素数除外) ,目前用的都是证明这个整数是素数的概率为99.999......%的方法，一般都是费马小定理推广的，真正可以准确判别的方法运算量过于大

因此想了解郭老大在判断素数的时候用了什么算法，又做了什么优化？

gxqcn · 发表于 2008-2-1 19:58:50

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

关于素性检测学问很深，如果不是亲自去实现，还是别淌这个混水为好，不是那么简单滴。

282842712474 · 发表于 2008-2-1 20:41:39

关于梅森素数:
HugeCalc判断2^1257787-1可以很快判断它是素数,但判断其邻近的质数所生成的书是否梅森素数就要很久,这是为什么?

282842712474 · 发表于 2008-2-1 20:46:39

不知道郭老大有没有想过有威尔逊方法?

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

这个方法是100%对的,但是运算量太大,甚至比一个个数去除还慢,有没有人想过去优化这个算法?

gxqcn · 发表于 2008-2-1 20:56:32

这个定理仅有理论价值，没有实用价值，至少在素性判定上。

比如要判定 999979 是否为素数，用最常规的方法都判定出来了，恐怕你的 999978! 还在计算中。。。

282842712474 · 发表于 2008-2-1 21:02:24

这个的确只是理论上的,实质意义目前来说还没有

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

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

可惜逆定理不成立，甚至出现了所谓的“伪素数”

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

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