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

mathe · 发表于 2008-2-2 08:36:20

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

因此想了解 ...

我给出的链接里面给出的:http://mathworld.wolfram.com/EllipticCurvePrimalityProving.html
就是100%准确的呀。只是椭圆曲线理论太复杂了

风云剑 · 发表于 2008-2-2 08:55:08

有证明判定的，只是比较复杂。梅森素数可以用来创记录，不过没什么实用价值，已知的一共还不到50个。

zed · 发表于 2008-2-4 18:20:31

看了上面链接说ECPP是一种在O((lnN)^4)时间内判断一个数是否素数的判定方法，
也就是ECPP已经是一种多项式时间算法（关于大整数的位数来说是多项式时间）。

可是记得前几年印度人发表了一篇非常轰动的文章《Primes is in P》,也就是说这篇文章证明
可以在多项式时间内判断一个大数是否是素数。
难道《Primes is in P》不是第一个介绍多项式时间算法的文章？

风云剑 · 发表于 2008-2-5 08:53:19

http://members.cox.net/mathmistakes/primes.htm
Primes is in P

primality_v6.pdf (195.27 KB, 下载次数: 8)
我水平不够，看不懂这东西。

无心人 · 发表于 2008-3-6 20:39:49

除了ECC
80年还有人提出一种方法也是确定性算法
是基于分园域或者雅克比和的一种算法

在原理上比较复杂
但算法的参数选择和操作都比ECC要简单

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

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

评分