穿梭时空的未来人提出的疑惑 （ Interger Factorization ）

湖俊

不好意思，Factorize Interger我不晓得怎样翻译成中文。

在国外的一个论坛，有个自称是2043年的人物（不是john titor，这次是另外一个人了），他为了要说服2006~2007年的我们，他要求随便一个会员给他一个600digits的integer，然后他能factorize出来。

http://www.timetravelinstitute.com/ttiforum/showflat.php?Cat=&Board=ttclaims&Number=39307&page=0&view=collapsed&sb=5&o=&fpart=1&vc=1

他说目前2006年最好的电脑，要解200位数整数的factor，需要数月的时间，而要解600digits的interger factorization，要用好长好长的时间。然而，以2043年的科技，数小时内就能算出答案了。在论坛内，就有人任意写了500个digits的整数给他，然后在18个小时候，他放出答案，过后经过验证，他的答案是对的。

我在wikipedia找了关于integer factorization的文章
http://en.wikipedia.org/wiki/Integer_factorization

Current state of the artA team at the German Federal Agency for Information Technology Security (BSI) holds the record for factorization of semiprimes in the series proposed by the RSA Factoring Challenge sponsored by RSA Security. On May 9, 2005, this team announced factorization of RSA-200, a 663-bit number (200 decimal digits), using the general number field sieve.
The same team later announced factorization of RSA-640, a smaller number containing 193 decimal digits (640 bits), on November 4, 2005.
Both factorizations required several months of computer time using the combined power of 80 AMD Opteron CPUs.

RSA Factoring Challenge是一种挑战人们能否factorize超大整数，他们会提供一个整数，先答到的队伍就能赢取数十万美金。

193digits的integer，要factorize，要好几个月，而且是将80台电脑parallel连接起来集合运算。


那个自称未来人的，轻松算出500digits的factor，目的是要让大家相信他是未来人。
有人相信，有人不信，有人抱着观望态度。

要明白，算是100digits整数的factor可能花不了多少时间，但，200digits的整数，factorize需要的时间可能是exponential 100digits需要的时间的。。而200digits的，RSA用了18个月来算。600digits的，可能要用百万年。

希望各位数学爱好者来看看，到底有什么办法做到？

dunwan2tellu

据我所知，prime factorisation 这东西需要用一个一个 prime 来test . 600 digit 的号码，他的 prime 最大可能是 300 digit 的 prime ，整除起来很费时间的。

湖俊

原帖由 dunwan2tellu 于 1-1-2007 08:58 PM 发表
据我所知，prime factorisation 这东西需要用一个一个 prime 来test . 600 digit 的号码，他的 prime 最大可能是 300 digit 的 prime ，整除起来很费时间的。

我平时是没想过这点的，直到我看到那论坛的文章后，马上开ＭＡＴＨＥＭＡＴＩＣＡ来测试。。
数十个位数的号码（我选奇数），苦等了十多分钟后仍看不到答案。
ＣＰＵ　Ｕｓａｇｅ一直保持在６０％左右，温度从５１飙升至７５，相信电脑在很努力的运算。

我爱发问

我不太会数学啦...Factorize Interger是什么咚咚我也不懂，路过 来说一点题外话

那个人目的是要炫耀他的数学能力 还是要证明他是从2043年来的，呵呵...这故事有点搞笑
如果他要证明他是从2043年来应该还有很多办法，干嘛找这种办法来证明啊...例如他应该先向全世界宣布他是未来人，然后拿一些2043年的科技产品出来展示给大家，又或者预言几个月后会发生的大事，也可以说出他2043年的父母是谁，然后在这2006年找出他的父母，用DNA验证,再简单一点可以拿2006年之后才发行的钱币，验该纸币的质量和验证码就行了...还有很多方法啦...干嘛用Factorize Interger这种不是很多人懂的东西来证明啊...可能这个是比较笨的未来人...哇咔咔...

[ 本帖最后由 我爱发问 于 3-1-2007 01:08 AM 编辑 ]

湖俊

原帖由 我爱发问 于 2-1-2007 03:53 AM 发表
我不太会数学啦...Factorize Interger是什么咚咚我也不懂，路过 来说一点题外话

那个人目的是要炫耀他的数学能力 还是要证明他是从2043年来的，呵呵...这故事有点搞笑
如果他要证明他是从2043年来应该还有 ...

factorize integer，这个好像是国中一就学的东西来的哦，很简单的啊。

其实，要你预言一个时代发生的东西应该很难。比如说，我问你1973年发生了什么大事，不晓得你能不能告诉我？你是现代人，难道不晓得1973发生什么大事？或者问回你出生年代前后发生的什么大事，不晓得你又能否回答？

以上的疑问是这些所谓的未来人用来反驳我们现代人提出的疑惑，我引用而已。

湖俊

原帖由 dunwan2tellu 于 1-1-2007 08:58 PM 发表
据我所知，prime factorisation 这东西需要用一个一个 prime 来test . 600 digit 的号码，他的 prime 最大可能是 300 digit 的 prime ，整除起来很费时间的。

600 digit的号码，prime最大可能也是600 digit。

比如说
个位数，prime最大可能也是个位数。
十位数，prime最大也可能是十位数。

那么那个600位数的号码，这么巧给他是个偶数，那么直接得到2为factor，然后 最少 都还有599个号码的奇数。这样就难算了。

dunwan2tellu

原帖由 湖俊 于 2-1-2007 03:34 PM 发表


600 digit的号码，prime最大可能也是600 digit。

比如说
个位数，prime最大可能也是个位数。
十位数，prime最大也可能是十位数。

那么那个600位数的号码，这么巧给他是个偶数，那么直接得到2为fact ...

有理由！可能它本身就是 prime number .

湖俊

原帖由 dunwan2tellu 于 2-1-2007 05:54 PM 发表


有理由！可能它本身就是 prime number .

哈哈，其实这个未来人，究竟会不会有可能真的是未来人？若他真有办法计算这些数目的factor，那么RSA的数十万美金奖都被他扫了咯。。

我爱发问

原帖由 湖俊 于 2-1-2007 02:41 PM 发表


factorize integer，这个好像是国中一就学的东西来的哦，很简单的啊。

其实，要你预言一个时代发生的东西应该很难。比如说，我问你1973年发生了什么大事，不晓得你能不能告诉我？你是现代人，难道不晓得 ...

什么！？ 国一就学到了
看来我的数学不是普通的差，可是我敢肯定，去大街上随便找些人来问什么是factorize integer，肯定有一半以上不知道。

预言很难吗？那个未来人虽然不一定可以说得出，但只要回去他的时代查一下不就知道了吗？难道2043年的人都把历史资料都销毁掉了？还是因为那个未来人的时光机坏掉了，不能回去2043年了...呵呵...
就算他真的无法预言，应还有很多方法可以证明他是未来人，竟然搞 在论坛发表factor integer 的方法，无法了解未来人的头脑...呵呵

管他是不是未来人，继续你们的factorize integer讨论吧...

湖俊

原帖由 我爱发问 于 3-1-2007 01:37 AM 发表


什么！？ 国一就学到了
看来我的数学不是普通的差，可是我敢肯定，去大街上随便找些人来问什么是factorize integer，肯定有一半以上不知道。

预言很难吗？那个未来人虽然不一定可以说得出，但只 ...

他的解释是，现在来到了这个年份，他没法子特地回去再找历史资料来给大家看，因为储存的能源只能回去一次。就比如说现在，你一个普通市民，能不能找出1988年7月在马来西亚发生过什么事情？历史资料是有的，但，我突然发出这样一个问题，你能怎样回答？

我不晓得街上的人有多少会factorize，但，我在大学的时候，要问多少人会相信并不难。

还记得当年我国中一的时候，老师第一课就教 FSTB (faktor sepunya terbesar), GSTK (gandaan sepunya terkecil), faktor perdana。。我没特地翻书，只是这些是数学基础，不会忘记而已。不过这是很久了的事情，不晓得现在的课程是否还一样？

faktor perdana (prime factor)，是说一个数目的质数因数
我不大会解释，质数是prime number，是一种不能被其他号码除整的，比如
2，3，5，7，11，13，17...

factor则是我们能从一个数目factorize出来的号码
比如2就是4, 6, 8, 10...的factor  
4 = 2(2)
6 = 2(3)
:
:
factorize integer是对一个数目factorize，只取prime factor。

呵呵，现在我们都对数学有兴趣，而这个未来人只是一个前提，真正要带出讨论的是这个factorization吧。

~Lucifer~

现在的还一样啊，只是国中一这样东西的内容介绍不多，也难怪大部份人会忘记掉。我也是过后看了一些书都有提到prime number才记得的。

[ 本帖最后由 ~Lucifer~ 于 3-1-2007 07:50 AM 编辑 ]

湖俊

原帖由 ~Lucifer~ 于 3-1-2007 07:47 AM 发表
现在的还一样啊，只是国中一这样东西的内容介绍不多，也难怪大部份人会忘记掉。我也是过后看了一些书都有提到prime number才记得的。

哈哈，这些prime number在calculus和analysis有用到的哦。。

~Lucifer~

calculus有用到？呵呵，酱迟些我应该会学到，这个sem的没有教。

jinqwem

是不是未来人不是重点，　重点是他怎么办到的．．．
六百位数的号码，　最大的质数值是三百位数，　
我不懂电脑是怎么开始运算的，　我转一下原贴．．．
after giving me the number
18538766351361919312845678191705085440094873207093838284252181683439010952372238950386370395683427684760
72187829984104923976114969862707837362090997412787155779727521934418433488551822946641365665019698834649
81573140595471911058421463974110864258747441444968128720742848635632424123114434423935996345018247787022
39082758978461729599649072671810993691226347438579420302556873337476181466375497597012276040286600591941
92998744867183022492857573544028071545502589738694701681236830046542691006146858361641615658083641630588
8759021239753678553107122

it should be easy for you to confirm that we can factor it:
2*11*109*563*787*811*26249*26740187*297977633*2576609840821073*
35201546659608842026088328007565866231962578784643756647773109869245232364730066609837018108561065242031153677*
3*13*17*47383219405128844982535569*
745213698191737003631319694753125429293968166002970537936165661845575001172678049743806549549977234670072449443569701103*
10513733234846849736873637829838635104309714688896631127438692162131857778044158273164093838937083421380041997*
10966824629*420145406901811857791227072284165226561693483222287527567496017033892563342686752247587935117119306171161848593337649107=
从数字来看，　他不可能用手工或计算机计算，　应该是用电脑方程去找．．．
８０　个ＡＭＤ处理器办不到的东西，　８千万个呢？　
抑或在找到最小数值，　如二后，　立即把有关数字除二在输入，　会不会比较快呢？　

ruud

原帖由 湖俊 于 2-1-2007 02:41 PM 发表


factorize integer，这个好像是国中一就学的东西来的哦，很简单的啊。

其实，要你预言一个时代发生的东西应该很难。比如说，我问你1973年发生了什么大事，不晓得你能不能告诉我？你是现代人，难道不晓得 ...

其实问他中国在2008olympic拿几面金牌就行，这不会很难找的。。。