Factoring contest.

[Martin]

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]

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.

[Tony]

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]

there are only supposed to be two factors right?

[Tony]

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]

Tony wrote:

It also appears that I don't know how to do simple multiplication

I am shocked and disappointed at the same time.

[Martin]

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]

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]

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

[md]

That obviously depends on the size of your drive... or drive array... You'd be surprised how much space some people might have

[codemage]

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]

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]

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]

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]

http://www.rsasecurity.com/rsalabs/node.asp?id=2964

it took 30 opteron years to solve the one before that, good luck guys