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 have a nice factorisation of the 617
digits one, but it is too big to fit in this post...
Cut and paste the big number into windows calculator and watch the number pad go nuts.
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.
All the numbers are divisible by 1!!! Gimme the cash!
From the FAQ:
I don't think distributed.net will make much progress based on current algorythms. Most people just do'nt have that much memory to donate to the cause. Might be time to invest in memory makers if you think they will buy it.
Accually for 5 you only need to check for a last didget of 5. If the last didget was 0 it would be even, and we already have determined that it isn't even. Further we know that there are exactly TWO primes involved, so if it ended in 0 the only possibility is 2 and 5, which means the number is 10.
I don't know how to help you with 7, but I did just save you a millisecond with 5.
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)
http://www.rsasecurity.com/rsalabs/faq/2-3-4.html
:)
Hmm...
All the Challenge numbers are the product of two primes, so there's only 2 factors. If we had a list of al the primes of length n, where n is the length of the longest Challenge number, this would be trivial. But since we don't...
Well, read the FAQ for yourseves.
Want to learn about race cars? Read my Book
the 'arbitrary precision calculator' that *nix people (usually) have it right at their fingertips. Don't know what Windows users have to accomplish the task.
try { do() || do_not(); } catch (JediException err) { yoda(err); }
All those numbers are odd. I had an idea about dividing by 2 :)
Nyah nyah!
Yes, someone could luck out. But do you realize what you are saying?
As an example, radioactive decay is, at the atomic level, a fairly random process, and the atoms are basically isolated. Any given atom could just pop at any moment, and at any given moment some of them are.
Realize now that, with some "luck", it would be very possible for a whole bunch of atoms to decay at once. There's nothing keeping them going at any certain rate other than probability; it's incredibly unlikely that any large number of atoms will do the same relatively unlikely thing at around the same time.
In this case, I would say that if you use your computer to try some random prime numbers, it's far more likely that you'll explode than find the correct numbers "on accident". Not a good risk, I say.
I have seen the future, and it is inconvenient.
Hah, amen. I used to know a guy who would always tell people that various government agencies were after him for his uber-hacking. He'd even pretend, like if he was driving his car there was a good chance he'd start skidding down side streets because someone was "tailing him".
Then again, he wasn't anything I'd call a "hacker", in any sense of the word. The best one-word description of him would be "wannabe".
I have seen the future, and it is inconvenient.
RSA is offering this money to show that the RSA public key method IS secure, because we can't factor these numbers.
Someone coming out tommorow with the solution for *all* of these. For everyone. And having it verified.
I've thought about this before, but more from the perspective of "what if by some freak accident I was to stumble on the algorithm that makes factoring trivial? what would I do?"
Now, I don't believe everything I see in movies, but I also don't feel like putting my welfare or my sanity on the line by exposing something so momentous and dangerous. A lot of powerful people depend on the difficulty of factoring to keep their stuff secret.
Here's what I think I would do: Send an encrypted e-mail to Bruce Schneier describing the algorithm (he must have a public key posted somewhere), and forward it through a dozen anonymous remailers. Preface the explanation with this: The existence of the algorithm I am about to describe is terrifying to me, and I am not fit nor willing to take responsibility for it. I trust your judgement in how you feel is the best way to proceed.
--
Bruce Schneier wrote in Applied Cryptography (p. 258): "If you could store one gigabyte of information on a drive weighing one gram, then a list of just the 512-bit primes would weigh so much that it would exceed the Chandrasekhar limit and collapse into a black hole..."
(Reality reasserts itself sooner or later.)
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."
Hmmm, I have the original edition. I don't see a question 47. Question 16, the last one, is the only one rated 50 that I see: 'Are there infinitely many Mersenne primes?'
Intuitively, I would say yes. I can't prove it. I don't know that anyone has.
Knuth does say, in the 'Notes on the Exercises', that a 50 is a research problem that hasn't been solved yet. As his example he uses Fermat's last theorem. Of course, the book is copyright 1969. Don't know if he's corrected that in the latest edition. No reason to buy the new one, I'm not finished with this one yet!
--
Alex Johns
An interview on CNet radio yesterday with the chief research guy @ RSA said that RSA expects to pay the first sum ($10,000) within a year.
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
I'm giving up. Maybe I should have stayed in grad school.
Distributed computing power has become so abundant and easily reachable (seti, dist.net, etc), that the entities with interests in preserving and justifying there existance (seti folk, protein structure folk, encryption folk)have to survive by distracting us with a limitless abundance of distributable contests.
Try google:
http://www.eff.org/Misc/Graphics/nsa_1984.gif
Now go to cafepress, and have one printed.
But there is no way for you to factor any of these numbers while you're still alive. Last year the RSA 512 bit number was factored. It required about 9 months on ~400 Alphas and Pentium IIs, plus (and this is the kicker), about 4 weeks on a really huge supercomputer (I think about 2 weeks at the start, and 2 and at the end). You need like 4 gigs of RAM (at least, more as the numbers get longer) to do this.
The supercomputer steps cannot be done in parrallel - it's a huge linear algebra problem. You would have to find a new factoring algorithm if you wanted to make it a distributed.net-style problem.
Create a internet worm that uses your idle clock cycles to find the number, and sends it back to me once it's found it. I would use anonymous Usenet for communication: requesting jobs, posting jobs and (hopefully) posting the current solution.
The reason for not making a large (voluntary) distributed project is because you'll probably have to split the money with the lucky dope that found the number, this way you get to keep the money.
-Jon
this is my sig.
While I am without the ability to actually check the number you've just provided, I know it should at least be odd, which your number isn't. The max # generated by 576 bits would be 2^576 -1.
2 times itself 576 times would be even. Subtracting 1 would then make it odd.
You are the weakest link, goodbye!
24733040147310453406050252101964719003513134910
so, say you wanted to solve it in a lunar month.You would need to try something on the order of
88332286240394476450179471792731139298261196107
factors per day or
36805159266831031854241446580304641374275498378
per hour or
61341865444718386423735744300507735623792497296
per minute or
10223644240786397737289290716751289270632082882
per second....
now distributed.net is getting 127Gkeys per second... or about 127000000000 keys per second... look at the difference in the number of digits... RSA won't have to pay on that for a LONG time about8 41 91243355002259457438595524172029124979552458558672 34341034133758742263188689327699355242471411637798 00504
61754295921048244341300860763463725504842696735
years at that rate if my calculations are right....
---
42 of course. :)
The Economics of Website Security
lets not forget that computers do this many times a second
Maybe they should have based the prize ammount on one of the factors, moving the decimal to a reasonable position of course.
So, if you just randomly pick factors what are your odds, and how does it compare to the lottery when computed on an average PC? Of course unlike lotto, you don't have to pay to play unless you really decide to go all out and purchase additional hardware, which would probably not be justified.
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
Wouldn't it be quicker to stop once n is greater than or equal to the square root of the number to be factored?
Only in an abstract kind of sense. Given that the numbers are composite (and the RSA could be lying here) - the alogrithm will be sure to have finished before your optimization comes into play. Hence the calculation as to what the square root was will slightly slow down the overall run time.
Special Relativity: The person in the other queue thinks yours is moving faster.
Didn't the mathematician guy (who got killed) use his solution of "factoring large primes" to break encryption?
Please explain how that is possible.
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.
RSA have several different levels of prizes.
Here is the list:
Good luck on getting those anytime soon.
Just make sure you don't rig up all the computers at your workplace to win the prize.
"A door is what a dog is perpetually on the wrong side of" - Ogden Nash
CWI has several source code license agreements with companies in The Netherlands, USA, Germany and France which allow them to use the Number Field Sieve factorization code as this was and is being developed by P.L. Montgomery, A.K. Lenstra, M. Elkenbracht-Huizing, S. Cavallar and B. Dodson. On a non-commercial basis, the NFS source code has also been made available for research purposes to other cooperating groups. A group of the Royal Institute of Technology in Stockholm (Hastad) has used this code as a basis for factoring a hard 512-bit challenge number in October 2000.
See the RSA Crypto FAQ.
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.
laughably easy?
For those who want some money but don't know how can start here.
GNU MP is a library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. It has a rich set of functions, and the functions have a regular interface.
home page for GNU MP
Make It Secret . Free JavaScript implementation of AES for your browser
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.
...someone (think rich, dumb and unethical) used (or even intended to use) those factorable numbers to encrypt some original content, then called the DOJ and screamed "DMCA" and that evil software pirates were trying to crack their encryption?
Stupid scenario? Really? In the context of the DMCA, nothing's beyond the pale. Remember the SDMI cracking challenge?
If you were blocking sigs, you wouldn't have to read this.
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? :-)
With 1,000,000,000,000,000 or so of my closest friends, everybody take a chunk of integers, give out some factoring code, and start grinding away every night. It all in the organization, think seti@home.
spacefem.com