Win $200,000 In RSA's Factoring Challenge

BetaRelease writes: "All ye with excess CPU cycles to spare. Here's a chance to win as much as $200,000. Join RSA's Factoring Challenge." That means you can get $10,000 for figuring out the factors for this laughably easy, completely trivial number, or twenty times that if you can figure out a slightly nastier one. While it would probably take more horsepower to win any of the prizes than the prize money could pay for, admit it would be cool to trade a 98-digit number for a few years' salary.

Comments

Just to get us started ...

[James Ezick]

Well let's see ...
2 ... None are even ... nope.
3 ... None of the digit sums is divisible by 3 ... nope.
5 ... None end in 5 or 0 ... nope.
7 ... Well, I'm out of ideas.

Warning to Slashdot users workin on this!

[dstone]

Just for the hell of it, I tried hitting "Submit" with a blank submission of factors. Mostly, I was curious to see if they were using SSL for submissions because what if someone was snooping and intercepted my submission and then submitted it themself. Hey, it could happen!

Anyways, no they don't use SSL, but more surprisingly, they care who your referrer was. And they say "slashdot not found in list of allowed referrers". Not sure if this would actually prevent a legitimate submission, but maybe you don't want to risk clicking thru Slashdot to RSA when you find the real factors. (Especially considering the lack of SSL.)

Error Message:
slashdot not found in list of allowed referrers.
Required Field: email has not been completed.
Required Field: Submitters has not been completed.
Required Field: challnum has not been completed.
Required Field: p has not been completed.
Required Field: q has not been completed.
Required Field: description has not been completed.
Please use your 'back' button to return to the Web form.

techniques to factor big numbers

[plcurechax]

If you want to actually try this, there are several things to realise, first you need a lot of computing power, including at least one very large multiprocessor machine with several (>4) GB of RAM. Think high-end Alphas, slightly dusty Crays, think big.

The current record factorings were done with the GNFS (General Number Field Sieve).

GNFS consists of a sieving phase that searches a fixed set of prime numbers for candidates that have a particular algebraic relationship, modulo the number to be factored. This is followed by a matrix solving phase that creates a large matrix from the candidate values, then solves it to determine the factors.

The sieving phase may be done in distributed fashion, on a large number of processors simultaneously. The matrix solving phase requires massive amounts of storage and is typically performed on a large supercomputer.

Some pointers:

• Integer factorization
• RSA-155 English press release
• Description of the task, from Singh's The Codebook Challenge
• RSA-129 factoring
• What are the best factoring methods in use today? (RSA Security FAQ)
• A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths by Bob Silverman

In case you haven't noticed...It isn't easy, and cannot be fully solved using a distributed.net technique.

to factor a 760-bit number in one year would require 215,000 Pentium-class machines, each with 4 Gigabytes of physical RAM.

to factor a 1620-bit number in one year would require 1.6 x 10^15 Pentium-class machines, each with 120 Terrabytes of physical RAM.

Good luck.

Raise the Prize amount please.

[egommer]

Yes I am planning on using all my school labs computers to win this one. But I only ask one favor.

Can you raise the prized to $415,000 instead. I might need it.