下载了个VirtualBox

无心人 · 发表于 2010-9-4 11:16:45

没天理了编译了个PARI/GP 进程序，瞬间完成分解个2^256 + 1 也就几十秒

wayne · 发表于 2010-9-4 16:00:22

171# 无心人 试试分解 2^293+1 ，

无心人 · 发表于 2010-9-4 20:09:52

呃，90位以下的问题都不大吧好像以前测试过95位的几个小时 100的肯定长的多

wayne · 发表于 2010-9-4 20:17:16

2^256+1 不到1秒钟就能搞定， 2^293+1 即便是十分钟，都还没分解出来

chyanog · 发表于 2010-9-5 13:22:12

2^293+1=3*587*26371*33403*13453890779540632945331892129844577* 762551893101410166019390283047520363896913

wayne · 发表于 2010-9-5 13:41:09

175# chyanog

花了多少时间？

chyanog · 发表于 2010-9-5 13:53:17

4202 s

chyanog · 发表于 2010-9-5 13:57:44

本帖最后由 chyanog 于 2010-9-5 13:59 编辑 我也没有料到花费时间居然以小时计，这就是典型的NP问题吧，最近不是有新闻说有人证明了P!=NP吗

wayne · 发表于 2010-9-5 14:02:25

178# chyanog 不知道是不是NP

wayne · 发表于 2010-9-5 14:11:41

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的因子这个问题要简单的许多。有文章[1]指出前者这个问题可以在多项式时间中解决（其中n为N的位数）。若允许微小的失误，更有许多的随机化算法可以非常快速的测试出一个数是否为质数。测试一个数是否质数不难，这是RSA算法中非常重要的一环，因为它在一开始的时后需要找很大的质数。（参见素性测试）。

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

[原创] 下载了个VirtualBox

评分