----------------------------------- Martin Tue Dec 06, 2005 10:32 am 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 ----------------------------------- codemage Tue Dec 06, 2005 1:36 pm ----------------------------------- 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 Tue Dec 06, 2005 1:51 pm ----------------------------------- 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 ----------------------------------- zylum Tue Dec 06, 2005 3:31 pm ----------------------------------- there are only supposed to be two factors right? ----------------------------------- Tony Tue Dec 06, 2005 3:52 pm ----------------------------------- 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 ----------------------------------- MysticVegeta Wed Dec 07, 2005 1:28 am ----------------------------------- It also appears that I don't know how to do simple multiplication I am shocked and disappointed at the same time. :shock: :shifty: ----------------------------------- Martin Wed Dec 07, 2005 4:41 am ----------------------------------- 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 Wed Dec 07, 2005 2:19 pm ----------------------------------- 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 ----------------------------------- Tony Wed Dec 07, 2005 2:35 pm ----------------------------------- 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 :? ----------------------------------- md Wed Dec 07, 2005 2:36 pm ----------------------------------- That obviously depends on the size of your drive... or drive array... You'd be surprised how much space some people might have ;) ----------------------------------- codemage Wed Dec 07, 2005 2:41 pm ----------------------------------- 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 Wed Dec 07, 2005 3:05 pm ----------------------------------- 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. ----------------------------------- bugzpodder Thu Feb 23, 2006 7:58 pm ----------------------------------- 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) ----------------------------------- chrispminis Thu Feb 23, 2006 10:59 pm ----------------------------------- 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 :( ----------------------------------- Andy Thu Feb 23, 2006 11:03 pm ----------------------------------- http://www.rsasecurity.com/rsalabs/node.asp?id=2964 it took 30 opteron years to solve the one before that, good luck guys ----------------------------------- bugzpodder Thu Feb 23, 2006 11:09 pm ----------------------------------- 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 ----------------------------------- md Fri Feb 24, 2006 5:18 am ----------------------------------- 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... ----------------------------------- Andy Fri Feb 24, 2006 8:30 am ----------------------------------- 30 opeteron years of cpu time ----------------------------------- codemage Fri Feb 24, 2006 10:10 am ----------------------------------- 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. ----------------------------------- md Fri Feb 24, 2006 5:52 pm ----------------------------------- 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. ----------------------------------- Andy Fri Feb 24, 2006 6:54 pm ----------------------------------- yea that would be uber painful since a turing string can only stolre 255 characters... ----------------------------------- md Fri Feb 24, 2006 7:02 pm ----------------------------------- 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. ----------------------------------- Andy Fri Feb 24, 2006 7:11 pm ----------------------------------- ints in an array? ----------------------------------- md Fri Feb 24, 2006 8:23 pm ----------------------------------- 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. ----------------------------------- bugzpodder Fri Feb 24, 2006 9:42 pm ----------------------------------- 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)