Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Factoring contest.
Index -> Contests
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Martin




PostPosted: Tue Dec 06, 2005 10:32 am   Post subject: Factoring contest.

Factor the following number:

74037563479561712828046796097429573142593188889231
28908493623263897276503402826627689199641962511784
39958943305021275853701189680982867331732731089309
00552505116877063299072396380786710086096962537934
650563796359

212 digits, the sum of which is 1009.

Prize: $30,000 cash. I'm not joking.

http://www.rsasecurity.com/rsalabs/node.asp?id=2093#RSA704
Sponsor
Sponsor
Sponsor
sponsor
codemage




PostPosted: Tue Dec 06, 2005 1:36 pm   Post subject: (No subject)

Your first hint, unless you have supercomputer or distributed net access, is to ditch the lameass general number field sieve, and go for the fast & gritty stuff you learned from watching Sneakers. Wink

Or if you're good with math, you can use the good ol' guess & check method.
Tony




PostPosted: Tue Dec 06, 2005 1:51 pm   Post subject: (No subject)

how long to generate a list of prime numbers in the range where the answers could be found?

Then just set up a guess & check over a small distributed network.

Edit: I appear to have forgotten how to do multiplication... sorry
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
zylum




PostPosted: Tue Dec 06, 2005 3:31 pm   Post subject: (No subject)

there are only supposed to be two factors right?
Tony




PostPosted: Tue Dec 06, 2005 3:52 pm   Post subject: (No subject)

yes, only two factors.. both are near the range of target number's root.

It also appears that I don't know how to do simple multiplication, so I retract my above post
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
MysticVegeta




PostPosted: Wed Dec 07, 2005 1:28 am   Post subject: (No subject)

Tony wrote:

It also appears that I don't know how to do simple multiplication


I am shocked and disappointed at the same time. Shocked Shifty
Martin




PostPosted: Wed Dec 07, 2005 4:41 am   Post subject: (No subject)

Using a distributed system, you can bash it to death and eventually get the answer.

Using a normal computer, you have to be more creative. First, find the square root of the number, then just (educated) guessing would be key I suppose. And luck. A lot of luck.
Andy




PostPosted: Wed Dec 07, 2005 2:19 pm   Post subject: (No subject)

but matin, did you look at the number they factored before that? the 20k one? it took them 5 months of pure processing on 30 opterons... i doubt any of us can do it by ourselves, infact if u use the approximation for the number of primes primes < n = approximately n/log n, the number of primes we need to examine (ones near the root) cant even be fit it on our hard drives
Sponsor
Sponsor
Sponsor
sponsor
Tony




PostPosted: Wed Dec 07, 2005 2:35 pm   Post subject: (No subject)

Andy wrote:
infact if u use the approximation for the number of primes primes < n = approximately n/log n, the number of primes we need to examine (ones near the root) cant even be fit it on our hard drives

only 10^40 GB...

hard drive space is for suckers. Just have that much RAM.. oh wait Confused
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
md




PostPosted: Wed Dec 07, 2005 2:36 pm   Post subject: (No subject)

That obviously depends on the size of your drive... or drive array... You'd be surprised how much space some people might have Wink
codemage




PostPosted: Wed Dec 07, 2005 2:41 pm   Post subject: (No subject)

You wouldn't have to find ALL of the primes and then do ALL of the factorization, would you?

Wouldn't it be possible to find a subset of the nearby primes (find 1000 on either side of the root) and then test those as factors, then check the next 1000 primes, etc.

That'd save a few paycheques spent on hard drive space. (Or at least free up that massive storage space for more useful endeavours.)
Tony




PostPosted: Wed Dec 07, 2005 3:05 pm   Post subject: (No subject)

There could be a lot of optimization involved. As I was originally saying (before being thrown off by my own math, and retracted the statement):

We don't even need to store ALL of the primes or even in full.

The target number ends in ...6359

Therefor the 2 keys end in ether 1 and 9 or 3 and 3 (to get that last 9) Filters out about 60%. Continue on from there.

Though I guess it will ultimatly it will come down to how fast we can find out what the nth prime (of ~100 digits long) is.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
bugzpodder




PostPosted: Thu Feb 23, 2006 7:58 pm   Post subject: (No subject)

Interesting... i've just noticed this thread. These numbers didn't look that big lol... Tony, the number of primes less than n can be approximated by n/ln(n) (prime number theorem, for those of you interested, Gauss discovered it when he was only 15 -- when most of us don't even know what ln is)

in the largest number, we are looking at 10^305/ln(10^305) = 10^300 primes Wink

Good luck on guessing! I have a better chance of winning the 300 million dollar lottery (which has 1 in 300 million chance, thats 3*10^8)
chrispminis




PostPosted: Thu Feb 23, 2006 10:59 pm   Post subject: (No subject)

It's true, its not 30,000$ for nothing. Most people cannot make a living out of finding factors for very very large numbers. Extremely large prime numbers are used for many different things. (I think I heard somewhere mostly encryption) like CIA stuff. You need a lot of computer power, creativity and TIME to work it out. And in the end, putting in the hours in a job would get you more money. Although if you managed to set up an efficient network, it could make money for you while you work. But still, yeah very difficult Sad
Andy




PostPosted: Thu Feb 23, 2006 11:03 pm   Post subject: (No subject)

http://www.rsasecurity.com/rsalabs/node.asp?id=2964

it took 30 opteron years to solve the one before that, good luck guys
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 25 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: