:dizzy:
没天理了
编译了个PARI/GP
进程序，瞬间完成
分解个2^256 + 1
也就几十秒
171# 无心人
试试分解 2^293+1，:lol
呃，90位以下的问题都不大吧
好像以前测试过95位的
几个小时
100的肯定长的多
2^256+1 不到1秒钟就能搞定，
2^293+1 即便是十分钟，都还没分解出来
2^293+1=3*587*26371*33403*13453890779540632945331892129844577*
762551893101410166019390283047520363896913
175# chyanog
:b:
花了多少时间？
:D 4202 s
本帖最后由 chyanog 于 2010-9-5 13:59 编辑
我也没有料到花费时间居然以小时计，这就是典型的NP问题吧，最近不是有新闻说有人证明了P!=NP吗
178# chyanog
不知道是不是NP
http://zh.wikipedia.org/zh-cn/整数分解
现在还不确切知道整数分解属于那个复杂性等级。
我们知道这个问题的判定问题形式（“请问N是否有一个比M小的因子?”）是在NP与co-NP之中。因为不管是答案为是或不是，我们都可以用一个质因子以及该质因子的质数证明来验证这个答案。由 肖 的算法，我们得知这个问题在BQP中。大部份的人则怀疑这个问题不在P、NP-Complete、以及co-NP-Complete这三个复杂性类别中。如果这个问题可以被证明为NP-Complete或co-NP-Complete，则我们便可推得NP=co-NP。这将会是个很震憾的结果，也因此大多数人猜想整数分解这个问题不在上述的复杂性类别中。也有许多人尝试去找出多项式时间的算法来解决这个问题，但是都尚未成功，因此这个问题也被多数人怀疑不在P中。
有趣的是，当判定问题为“N是否为一合数？”则比要找出N的因子这个问题要简单的许多。有文章指出前者这个问题可以在多项式时间中解决（其中n为N的位数）。若允许微小的失误，更有许多的随机化算法可以非常快速的测试出一个数是否为质数。测试一个数是否质数不难，这是RSA算法中非常重要的一环，因为它在一开始的时后需要找很大的质数。（参见素性测试）。