The RSA Challenge Numbers - Factoring challenge

kee020041

不懂有没有人发过这个贴,
http://en.wikipedia.org/wiki/RSA_numbers
这是一个有奖的比赛，
给你一个号码，你只要找出它的FACTOR，那你就有钱拿。
比如：

http://www.rsa.com/rsalabs/challenges/factoring/RSA-704.txt
Name:         RSA-704
Prize:        $30000
Digits:       212
Digit Sum:    1009

RSA-704 = 74037563479561712828046796097429573142593188889231289084936232638972765034
          02826627689199641962511784399589433050212758537011896809828673317327310893
          0900552505116877063299072396380786710086096962537934650563796359

这个问题是一个212digit的号码， 要找出它的factor就可以得到USD $30,000。
有没有人有兴趣？？？

[ 本帖最后由 kee020041 于 24-4-2008 11:08 AM 编辑 ]

dunwan2tellu

以前好像有帖过，不过找不到。

prime number 一直以来就是人类想突破的领域，也难怪他们会悬赏大的数目来鼓励人们找出他的 factor .

~HeBe~_@

对~我想把这个游戏介绍给我的讲师，和他研究研究一下。

flash

原帖由 kee020041 于 24-4-2008 11:07 AM 发表
不懂有没有人发过这个贴,
http://en.wikipedia.org/wiki/RSA_numbers
这是一个有奖的比赛，
给你一个号码，你只要找出它的FACTOR，那你就有钱拿。
比如：


这个问题是一个212digit的号码， 要找出它的facto ...

可否用个电脑程序把它找找出来？

kee020041

我算过了，不可能用brute-force。
上面问题是, x= 212位数，
x = a . b, where a & b is a prime number, and lets a< b

a < square root (x)  < b
a < (212 / 2 位数) < b
a< 10^106 < b

如果有1000架电脑, 每架电脑每一秒可以check 10,000次,
那要找出a需要  时间 = （10^106 / 1000 架电脑） /  10,000次/秒 = 10^ 99 秒
                                = 10^ 99 / （60 * 60 * 24 *365 ）年
                                = 3.71 x 10 ^ 91 年

3.71 x 10 ^ 91 年 还长过宇宙的时间。

tensaix2j

有个什么 Shor's algorithm 有帮助吗？
不大记得了。。。。

多普勒效应

原题要求分解的数目是一个 212 位数的号码, 而非 212 本身.

~HeBe~_@

我也想了一想，要是用3.71 x 10 ^ 91 年时间来找出a。
但是，那个题目是怎样形成的？不可能随便写212 位数的号码来让人家解的哦。。

[ 本帖最后由 ~HeBe~_@ 于 4-8-2008 07:48 PM 编辑 ]

kee020041

找两个116位数的prime number相乘不就可以了。

~HeBe~_@

我知道两个数字都是prime number.....只是116位数的prime number....太夸张了。。

mathlim

两个116位数相乘，会得到一个212位数吗？

kee020041

哈哈， 看错了
应该是（212 / 2）， 2个106位数相乘。

mathlim

两个106位数相乘，也未必会得到一个212位数！

例：
34×276 = 9384
二位数与三位数相乘，有可能等于四位数。

puangenlun

factor是没有位数限制得，不一定是106位数的数字相乘。

1位数乘212位数同样可以是212位数的数。

有一点值得注意，那就是最后一位。

通过观察最后一位，可以省去不少的计算量。

遗憾的是这样省去的计算量不多，但是聊胜于无。

以上纯属个人意见，如有失误，多多指教。

[ 本帖最后由 puangenlun 于 7-8-2008 11:26 AM 编辑 ]