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

无心人 · 发表于 2008-2-19 22:20:48

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

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

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

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

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

可以用椭圆函数方法证明是否是素数

无心人 · 发表于 2008-2-19 22:22:17

2000位以现在的计算水平，不是能用随机算法得到的
需要以某些特殊多项式表示的数字简化证明和搜索的过程

mathe · 发表于 2008-2-20 07:33:51

原帖由 无心人 于 2008-2-19 22:20 发表
另外，你们找到的素数要经过测试啊
米勒-罗宾测试不是素数的证明算法！在100位附近也许出现偏差的概率是0，但
如果碰巧遇到大因子卡米切尔数，恐怕......

这个大家都知道，不过通过上面程序找出了候选解以后，需要的只是验证而已，这个只是算法继续实现的问题了。
由于经过高强度概率测试，上面结果不是素数的可能性已经非常小了，基本上可以验证一组就得到这一组是确切结果的结论了，
所以验证的速度即使再慢（比如算法很慢，验证一组结果是正确的需要一分钟），那么对整体的时间复杂度也没有影响。
我们这里需要说明的只是找到10^100左右的四生素数的算法可以很快，至于结果是什么又有什么关系呢，这不是我们关心的问题。
至于你说的国际最优结果，抱歉得很，我对这个题材不感兴趣。有很多因素不是算法本身就可以决定的。

gxqcn · 发表于 2008-2-20 07:53:12

原帖由 无心人 于 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想做全，可以考虑做一个
当然也可以不做，因为毕竟是通用库，而不是数论库

gxqcn · 发表于 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

素性证明算法一般都是很复杂的
一般和模幂算法无无关的

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

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

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

其他的少

gxqcn · 发表于 2008-2-20 20:30:01

可否给出“1300位”纪录出处的链接？

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

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

回复 41# 的帖子

回复 48# 的帖子