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

无心人

晕 速度是够快的 看了英文资料 搜索quadtuplet 100位附近的4生素数的概率是比理论估计大很多的 所以在一万亿内就能搜索到很多的 而且最新的结果都到了1300多位 不如你们搜个2000位的如何 哈哈 另外，你们找到的素数要经过测试啊 米勒-罗宾测试不是素数的证明算法！在100位附近也许出现偏差的概率是0，但 如果碰巧遇到大因子卡米切尔数，恐怕...... 可以用椭圆函数方法证明是否是素数

无心人

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

mathe

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

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

gxqcn

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

在你首帖上估计需 3000000秒=34.72天 才能得到第一个结果，而实际上 mathe 仅用了不到两分钟。 从这里及其它论坛上来看，你无法从交流中感受快乐，也无法从别人那里获取有价值的东西，整天就是个“晕”！ （注：在我申请收费主页空间前，无心人 曾帮我把我的软件放在他的空间里以便发布，对此我一直心怀感激，虽然最后他的主页现在也不明不白的消失了 ）

无心人

哎 都不知道说什么了 我发表点看法而已 老当我是捣乱的 我习惯的交流也许语言激烈些 请不要认为我是故意为难你们 提出我的想法而已 我说2000位 不过说说而已 另外，找到结果和证明结果，都是重要的 当然也不能说，就让你们立刻写出证明的程序 证明一个100位数字是素数，印象里并不是很短时间就能证明的， 但也不是很长的 如果难于实现证明 可反过来，有很多现成工具能分解数字 100位的数字，一般10分钟的计算强度就能分解掉 除非具有接近50位的大因子 mathe写出这么短的运行时间的程序，我既然知道了，也就达到目的了，至于证明，能知道估计的时间就可 和mathe一样，我也不关心你的结果和程序的具体代码，我就知道可以就可以了 我初次设想没考虑筛法，抱歉，头脑蠢了 实现个2*3*5*7*11*13*17*19*k的筛，是个很好的主意 我说过，曾经我在400M机器上是1200亿/小时的速度， CSDN上有我的旧帖子 开两个缓冲，内存占用很小的 还有，并不是只有椭圆曲线才能证明素性 好多整数算法都可以的 你HugeCalc想做全，可以考虑做一个 当然也可以不做，因为毕竟是通用库，而不是数论库

gxqcn

要想打破当前的1300位纪录并非不可能的。 但最好是将HugeCalc新增一个导出接口，专门计算“k生素数”问题，这样内部可以避免许多重复计算，效率还将会大有提高。 关于“素性测试”，HugeCalc 采用了许多高级算法，检测强度比 Mathematica 还要大。

无心人

能说是什么算法么？ 据我知道 连Maple都不能证明素性的！！ 只能检验素性 还有： 你累不累啊 增加这么多接口 我想 应该是扩展，把纯数学的东西独立到一个模块里 而不是扩充啊 另外 看这个问题 a=1 b=2 c=3 d=4 e=(a + b) * (c + d) / ( c - a +1) 不知道你的HugeCalc能计算这个么？ 就是不拆开e直接计算e后面的四则运算式子 这个很重要 估计GMP可能不能算吧 猜测的，还没验证

无心人

打破1300位是可能的 按筛法搜索，优化后，估计双核并行达到1万亿/小时的搜索速度是可能的 但候选的数量无法估计，所以证明的速度待测 还有就是大概要搜索一亿亿才能搜索到一个

无心人

素性证明算法一般都是很复杂的 一般和模幂算法无无关的 中文的资料 在某本科普书上有一个 椭圆曲线的算法 在卢的书上有一个 算法导引上有 还一本中文的计算数论上也有 其他的少

gxqcn

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