找回密码
 欢迎注册
楼主: 282842712474

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

[复制链接]
发表于 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个。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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)
我水平不够,看不懂这东西。

评分

参与人数 1贡献 +3 经验 +5 鲜花 +1 收起 理由
mathe + 3 + 5 + 1 精品文章

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-6 20:39:49 | 显示全部楼层
除了ECC
80年还有人提出一种方法也是确定性算法
是基于分园域或者雅克比和的一种算法

在原理上比较复杂
但算法的参数选择和操作都比ECC要简单
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 00:12 , Processed in 0.044352 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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