目前对于大整数,没有一个100%准确的通用的素数判定方法(梅森素数除外) ,目前用的都是证明这个整数是素数的概率为99.999......%的方法，一般都是费马小定理推广的，真正可以准确判别的方法运算量过于大
因此想了解 ...
我给出的链接里面给出的:http://mathworld.wolfram.com/EllipticCurvePrimalityProving.html
就是100%准确的呀。只是椭圆曲线理论太复杂了:) 有证明判定的，只是比较复杂。梅森素数可以用来创记录，不过没什么实用价值，已知的一共还不到50个。 看了上面链接说ECPP是一种在O((lnN)^4)时间内判断一个数是否素数的判定方法，
也就是ECPP已经是一种多项式时间算法（关于大整数的位数来说是多项式时间）。
可是记得前几年印度人发表了一篇非常轰动的文章《Primes is in P》,也就是说这篇文章证明
可以在多项式时间内判断一个大数是否是素数。
难道《Primes is in P》不是第一个介绍多项式时间算法的文章？ http://members.cox.net/mathmistakes/primes.htm
Primes is in P
我水平不够，看不懂这东西。 除了ECC
80年还有人提出一种方法也是确定性算法
是基于分园域或者雅克比和的一种算法
在原理上比较复杂
但算法的参数选择和操作都比ECC要简单
页:
1
[2]