Computer Science Canada Factoring contest. |
| Author: | Martin [ 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 |
|
| Author: | codemage [ Tue Dec 06, 2005 1:36 pm ] |
| Post 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. 
Or if you're good with math, you can use the good ol' guess & check method. |
|
| Author: | Tony [ Tue Dec 06, 2005 1:51 pm ] |
| Post 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 |
|
| Author: | zylum [ Tue Dec 06, 2005 3:31 pm ] |
| Post subject: | |
there are only supposed to be two factors right? |
|
| Author: | Tony [ Tue Dec 06, 2005 3:52 pm ] |
| Post 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 |
|
| Author: | MysticVegeta [ Wed Dec 07, 2005 1:28 am ] |
| Post 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.   |
|
| Author: | Martin [ Wed Dec 07, 2005 4:41 am ] |
| Post 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. |
|
| Author: | Andy [ Wed Dec 07, 2005 2:19 pm ] |
| Post 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 |
|
| Author: | Tony [ Wed Dec 07, 2005 2:35 pm ] |
| Post 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  |
|
| Author: | md [ Wed Dec 07, 2005 2:36 pm ] |
| Post subject: | |
That obviously depends on the size of your drive... or drive array... You'd be surprised how much space some people might have |
|
| Author: | codemage [ Wed Dec 07, 2005 2:41 pm ] |
| Post 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.) |
|
| Author: | Tony [ Wed Dec 07, 2005 3:05 pm ] |
| Post 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. |
|
| Author: | bugzpodder [ Thu Feb 23, 2006 7:58 pm ] |
| Post 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
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) |
|
| Author: | chrispminis [ Thu Feb 23, 2006 10:59 pm ] |
| Post 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  |
|
| Author: | Andy [ Thu Feb 23, 2006 11:03 pm ] |
| Post subject: | |
http://www.rsasecurity.com/rsalabs/node.asp?id=2964 it took 30 opteron years to solve the one before that, good luck guys |
|
| Author: | bugzpodder [ Thu Feb 23, 2006 11:09 pm ] |
| Post subject: | |
who said anything about making a living off factoring? you'll need to know most current advanced algorithms in order to just attempt this problem. factoring is harder than np hard |
|
| Author: | md [ Fri Feb 24, 2006 5:18 am ] |
| Post subject: | |
The hardest part about this problem: dividing (or multiplying) two numbers that may be up to 212 digits each. Once you got that down all you need is CPU time. Lots and lots of CPU time... |
|
| Author: | Andy [ Fri Feb 24, 2006 8:30 am ] |
| Post subject: | |
30 opeteron years of cpu time |
|
| Author: | codemage [ Fri Feb 24, 2006 10:10 am ] |
| Post subject: | |
Cornflake wrote: The hardest part about this problem: dividing (or multiplying) two numbers that may be up to 212 digits each.
That's news to anyone who thought the hardest part was fitting the number into an int type with Turing. |
|
| Author: | md [ Fri Feb 24, 2006 5:52 pm ] |
| Post subject: | |
codemage wrote: Cornflake wrote: The hardest part about this problem: dividing (or multiplying) two numbers that may be up to 212 digits each.
That's news to anyone who thought the hardest part was fitting the number into an int type with Turing. You could do it with turing... not with ints... but it's still doable... /me shudders at the thought. |
|
| Author: | Andy [ Fri Feb 24, 2006 6:54 pm ] |
| Post subject: | |
yea that would be uber painful since a turing string can only stolre 255 characters... |
|
| Author: | md [ Fri Feb 24, 2006 7:02 pm ] |
| Post subject: | |
Andy wrote: yea that would be uber painful since a turing string can only stolre 255 characters...
There is another solution... one that actually does involve ints... but it's rather convoluted and quite challenging to implement. |
|
| Author: | Andy [ Fri Feb 24, 2006 7:11 pm ] |
| Post subject: | |
ints in an array? |
|
| Author: | md [ Fri Feb 24, 2006 8:23 pm ] |
| Post subject: | |
kinda; basically it involves stringing them together. The hard part is what happens when one number rolls over and how you pass that information on to the next. |
|
| Author: | bugzpodder [ Fri Feb 24, 2006 9:42 pm ] |
| Post subject: | |
Cornflake wrote: The hardest part about this problem: dividing (or multiplying) two numbers that may be up to 212 digits each. Once you got that down all you need is CPU time. Lots and lots of CPU time...
thats trivial... simple paper and pen methods run for O(n^2)... (trivial part) or Fourier transform takes O(n^1.4) time (not so trivial) for 212 digits, paper and pen is more than enough if you choose ur base intelligently (Base 10 is stupid. base 2^32 is smart) |
|