分解2^2147484239-1需要多长时间

qianyb · 发表于 2010-1-28 10:42:11

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

如题
CPU、内存和硬盘和分解时间大概各需要多少，还有说明用什么方法分解

mathe · 发表于 2010-1-28 11:01:51

现在应该还没有这样的计算能力

qianyb · 发表于 2010-1-28 11:07:47

那能否判定是不是合数呢，大概要多少时间

gxqcn · 发表于 2010-1-28 11:17:15

形如 2^p-1 的梅森数（Mersenne number）用 Lucas-Lehmer Test 可以快速精准判定，
但楼主这个数太大，估计得几个月或数年。

KeyTo9_Fans · 发表于 2010-1-28 12:28:30

刚才试图拿$3$、$5$、$7$、$11$、$13$等奇素数试除没有成功。

后来才发觉这样做是徒劳的。

要分解$2^p-1$，当$p$是素数时，分解出来的素数肯定比$p$大，而且可以写成$2kp+1$的形式，$k=1,2,3,...$。

所以要试除的话，得从$4294968479$开始试起，然后是

$30064779347$、$231928297813$、$283467919549$、……

mathe · 发表于 2010-1-28 13:00:33

的确如此，不过这样试除还是徒劳的，$2^p-1$实在太大了，这样的候选素数实在太多了。
现在已知的最大梅森素数可以查看wiki
http://en.wikipedia.org/wiki/Mersenne_prime

wayne · 发表于 2010-1-28 13:31:06

最大的Mp才 2^43 112 609 -1 ？
那我赶紧终止程序。。。。

刚才编了一个小程序，遍历所有素数，花了十几分钟，对幂取模，运行到了第122997842个素数，发现都不是其因子。

medie2005 · 发表于 2010-1-28 13:31:26

呵呵，还是不要想靠这个数去拿奖金了吧，不现实。

无心人 · 发表于 2010-1-28 13:51:13

楼主如果有有个8CPU8核的sun服务器，可以考虑这个问题

qianyb · 发表于 2010-1-28 14:23:42

呵呵，其实这个数是合数，其中一个因子是4294968479，就是 KeyTo9_Fans 说的第一个数

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

[提问] 分解2^2147484239-1需要多长时间

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。