数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

[讨论] 估计下找到10^100以上的一个四生素数的工作量

[复制链接]
 楼主| 发表于 2008-2-19 22:20:48 | 显示全部楼层

速度是够快的
看了英文资料
搜索quadtuplet

100位附近的4生素数的概率是比理论估计大很多的
所以在一万亿内就能搜索到很多的

而且最新的结果都到了1300多位

不如你们搜个2000位的如何
哈哈

另外,你们找到的素数要经过测试啊
米勒-罗宾测试不是素数的证明算法!在100位附近也许出现偏差的概率是0,但
如果碰巧遇到大因子卡米切尔数,恐怕......

可以用椭圆函数方法证明是否是素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-19 22:22:17 | 显示全部楼层

2000位以现在的计算水平,不是能用随机算法得到的
需要以某些特殊多项式表示的数字简化证明和搜索的过程
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-20 07:33:51 | 显示全部楼层
原帖由 无心人 于 2008-2-19 22:20 发表
另外,你们找到的素数要经过测试啊
米勒-罗宾测试不是素数的证明算法!在100位附近也许出现偏差的概率是0,但
如果碰巧遇到大因子卡米切尔数,恐怕......


这个大家都知道,不过通过上面程序找出了候选解以后,需要的只是验证而已,这个只是算法继续实现的问题了。
由于经过高强度概率测试,上面结果不是素数的可能性已经非常小了,基本上可以验证一组就得到这一组是确切结果的结论了,
所以验证的速度即使再慢(比如算法很慢,验证一组结果是正确的需要一分钟),那么对整体的时间复杂度也没有影响。
我们这里需要说明的只是找到10^100左右的四生素数的算法可以很快,至于结果是什么又有什么关系呢,这不是我们关心的问题。
至于你说的国际最优结果,抱歉得很,我对这个题材不感兴趣。有很多因素不是算法本身就可以决定的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-20 07:53:12 | 显示全部楼层

回复 41# 的帖子

原帖由 无心人 于 2008-2-13 17:21 发表
...
计算一个100位数字是素数的时间是 < 1/200, 每组4个数字平均计算次数是< 1.5
则应该平均在4000万 * 1.5 / 200 = 6000 0000 / 200 = 3000000秒得到第一个结果

我计算的对么?


在你首帖上估计需 3000000秒=34.72天 才能得到第一个结果,而实际上 mathe 仅用了不到两分钟。

从这里及其它论坛上来看,你无法从交流中感受快乐,也无法从别人那里获取有价值的东西,整天就是个“”!

(注:在我申请收费主页空间前,无心人 曾帮我把我的软件放在他的空间里以便发布,对此我一直心怀感激,虽然最后他的主页现在也不明不白的消失了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-20 08:24:38 | 显示全部楼层

都不知道说什么了

我发表点看法而已
老当我是捣乱的

我习惯的交流也许语言激烈些
请不要认为我是故意为难你们

提出我的想法而已

我说2000位
不过说说而已

另外,找到结果和证明结果,都是重要的
当然也不能说,就让你们立刻写出证明的程序
证明一个100位数字是素数,印象里并不是很短时间就能证明的,
但也不是很长的

如果难于实现证明
可反过来,有很多现成工具能分解数字
100位的数字,一般10分钟的计算强度就能分解掉
除非具有接近50位的大因子

mathe写出这么短的运行时间的程序,我既然知道了,也就达到目的了,至于证明,能知道估计的时间就可
和mathe一样,我也不关心你的结果和程序的具体代码,我就知道可以就可以了
我初次设想没考虑筛法,抱歉,头脑蠢了
实现个2*3*5*7*11*13*17*19*k的筛,是个很好的主意
我说过,曾经我在400M机器上是1200亿/小时的速度, CSDN上有我的旧帖子
开两个缓冲,内存占用很小的

还有,并不是只有椭圆曲线才能证明素性
好多整数算法都可以的
你HugeCalc想做全,可以考虑做一个
当然也可以不做,因为毕竟是通用库,而不是数论库
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-20 08:45:12 | 显示全部楼层
要想打破当前的1300位纪录并非不可能的。
但最好是将HugeCalc新增一个导出接口,专门计算“k生素数”问题,这样内部可以避免许多重复计算,效率还将会大有提高。

关于“素性测试”,HugeCalc 采用了许多高级算法,检测强度比 Mathematica 还要大。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-20 19:20:40 | 显示全部楼层
能说是什么算法么?
据我知道
连Maple都不能证明素性的!!
只能检验素性

还有:
你累不累啊
增加这么多接口
我想
应该是扩展,把纯数学的东西独立到一个模块里
而不是扩充啊

另外
看这个问题
a=1
b=2
c=3
d=4
e=(a + b) * (c + d) / ( c - a +1)
不知道你的HugeCalc能计算这个么?
就是不拆开e直接计算e后面的四则运算式子
这个很重要
估计GMP可能不能算吧
猜测的,还没验证
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-20 19:27:52 | 显示全部楼层
打破1300位是可能的
按筛法搜索,优化后,估计双核并行达到1万亿/小时的搜索速度是可能的
但候选的数量无法估计,所以证明的速度待测

还有就是大概要搜索一亿亿才能搜索到一个
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-20 20:01:12 | 显示全部楼层
素性证明算法一般都是很复杂的
一般和模幂算法无无关的

中文的资料
在某本科普书上有一个

椭圆曲线的算法
在卢的书上有一个

算法导引上有
还一本中文的计算数论上也有

其他的少
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-20 20:30:01 | 显示全部楼层

回复 48# 的帖子

可否给出“1300位”纪录出处的链接?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-8-25 23:20 , Processed in 0.057961 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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