第45和第46个梅森素数被发现！

fwjmath

HugeCalc和GMP都在这个领域上久负盛名，你可以两个都试一下，HugeCalc的作者是中国人，比较容易联系，GMP的话就只有英文材料了。

bardo

谢谢！再请教，Stein 最大公约数算法，是不是真的要比辗转相除法（欧几时得算法）要快？
GMP中是不是也是用的Stein 算法？
HugeCalc是作者是郭先强，以前下载过。
GMP以前也下载过。还有GNFS。

我觉得，无论HugeCalc，还是GMP，对付梅森素数的话，还是要有算法的吧？一个参数不可能支持几百兆字节长度吧？

[ 本帖最后由 fwjmath 于 2008-9-29 01:53 编辑 ]

fwjmath

在对付大数的时候的确是Stein比Euclid要快。
我不清楚，你可以去问问，不过不管怎么样它的速度都是一流的。
GNFS是一个整数分解的算法，不是数学类库，不能与GMP并列。
对付梅森素数当然要有算法，现今最快的算法就是Lucas-Lehmer测试。Prime95程序用的是经过仔细调整的汇编代码写成的Lucas-Lehmer测试，在同类软件中算是相当快的。
大整数在Prime95中不是直接表示的，是通过它的傅立叶系数表示的，这与快速傅立叶变换（FFT）相关。大整数相乘在每个快速高精度类库中都是用FFT实现的，因为它的时间复杂度是O(nlogn)，在大整数时远优于传统算法。可以查阅相关资料。

bardo

非常感谢！看来，人们应当感激RSA，感激梅森素数搜索。正因为有这些，真正促进了计算机中数据学算法的改进与加快。
如果没有这些，可能现在计算程序中还没有像：2^32进制，FFT变换乘法，Stein最大公约数算法等。
但是，仍有一些遗憾，那就是，所有这些，还没有更好的促进数学本身，或数论本身的发展。

[ 本帖最后由 fwjmath 于 2008-9-29 13:51 编辑 ]