Slashdot Mirror
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.
i've decided i'm going to spend any free time i have at work on this project.
i've just requisitioned 8,000 reams of paper and 5000 number 2 pencils. wish me luck.
Right. Pick two (presumably large, though there is no reason it has it couldn't be 1 very large and one laughably small prime number) prime numbers. Multiplu them togather. If the answer is that number, you have the solution.
The only problem is it is easy (as in I once did this when I was taking a class, but since have forgotten how) to prove that there are a lot of prime numbers to chose from. We also know of good ways to find out if a number is prime, but no good way to find the factors if it isn't.
Still, have fun. It isn't that hard to find two prime numbers with a paper an pencil. Of course arthmitic mistakes are likely, and it takes a lot of time)
RSA is offering this money to show that the RSA public key method IS secure, because we can't factor these numbers.
The first gradstudent to develop a serious quantum computer is gonna pick up a lot of cash.
Given one hour to live, the student replied: "I'd spend it with professor FP who can make an hour seem like a lifetime."
Someone coming out tommorow with the solution for *all* of these. For everyone. And having it verified.
While cool, and prestigious, and definitely worth money, the government would SURELY seek to either supress his findings, or acquire them.
If someone came up with an entirely new number theory solution that allowed easy factoring of huge numbers (ala Sneakers), the government would indeed be something to fear.
Not to mention, very few secrets would be safe.
Just an interesting thought for a boring day..
GPL'd web-based tradewars themed space game
Well let's see ...
... None are even ... nope.
... None of the digit sums is divisible by 3 ... nope.
... None end in 5 or 0 ... nope.
... Well, I'm out of ideas.
2
3
5
7
Please define "trivial", 'cause I don't think we're using the same definition of it.
I don't know how many primes there are below 10^617, but here's a hint: it's a LOT. A lot a lot. I don't know what the ratio of primes to nonprimes if, but let's just assume that 1 in 1 trillion numbers up to that level is prime (and I imagine that's conservative). 1 trillion is 1,000,000,000,000, or 10^12. So that reduces our number of primes down to 10^605. That's still a 605-digit number of them. Say it's only 1 in 100 quadrillion numbers -- still 10^600 primes.
So in order to solve the problem, you just attempt to divide the big number by each of the primes, and when you get an integral result, you stop. In fact, you only have use primes up to the square root of the number. The square root of 10^600 is 10^300. Assume you have a super-duper fast machine which can divide such an insanely huge number in just, say, 10 clock cycles, and it runs at 10GHz. That's a billion checks per second (10^9) -- really fast, huh?
So let's figure out how long our super-fast machine would take to crack this code using your method. 10^300 checks, divided by 10^9 checks per second, gives you 10^291 seconds. There are approximately 31,557,600 seconds in a year, or 3.15 * 10^7. 10^291 / (3.15 * 10^7) = 3.17 * 10^283. That's 31.7 million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million million years.
I'm glad to know, however, that I can now file this problem away in my "trivial" category.
ZFS: because love is never having to say fsck
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.
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:
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.
LOL.... no this is a cool joke!! I presume you are referring to Fermat's comment in the margin on his notebook about having the solution to his own theorem.
I just read Fermat's Last Theorem by Simon Singh a month ago and I loved it.
-Kraft
-Kraft
Live and let live
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.
Two Towers-Two Worlds.One seeks triumphs and freedom for man.The other deems man unworthy and wrecks them.
For those of you who are not donating your clock cycles to seti@home, you might want to try distributed.net. Right now, they are working on cracking a 64bit encryption key, which is also a contest from RSA securities. They are also working on finding more Optimal Golomb Rulers, so it seems that trying to factor this really huge number would be a nice fit. Take a look at the RC5 stats here. They are nifty.
It may be problematic insomuch as they are already working on three projects, and spliting off into another project would be troublesome. But, there are no other serious efforts going on towards these types of projects, so I suppose us d.net fans will just have to wait and see.
Lawrence Lessig is my personal hero.
Can you imagine that? :-)
m00.