Thread: Rsa-704

Ok as some of you know, this number:

74037563479561712828046796097429573142593188889231
28908493623263897276503402826627689199641962511784
39958943305021275853701189680982867331732731089309
00552505116877063299072396380786710086096962537934
650563796359

has two prime factors and RSA will give $30,000 to the person/team who can find them.

Who here knows some basic number theory on this problem and why it is so hard to factor?

Originally Posted by Jameson

Ok as some of you know, this number:

74037563479561712828046796097429573142593188889231
28908493623263897276503402826627689199641962511784
39958943305021275853701189680982867331732731089309
00552505116877063299072396380786710086096962537934
650563796359

has two prime factors and RSA will give $30,000 to the person/team who can find them.

Who here knows some basic number theory on this problem and why it is so hard to factor?

It's not divisible by 2, 3, or 5. Okay, I've done my part.

-Dan

It's hard because it doesn't fit in most calculators

Ummm, thanks guys. I suppose.

Obviously this number is semi-prime, and it's only factors besides 1 and itself are and . So I think it's safe to say 2,3, and 5 are out, as well as any other prime less than 100 digits.

Any ideas?

Originally Posted by Jameson

Ummm, thanks guys. I suppose.

Obviously this number is semi-prime, and it's only factors besides 1 and itself are and . So I think it's safe to say 2,3, and 5 are out, as well as any other prime less than 100 digits.

Any ideas?

At least you don't have to look farther than the sqrt of the number, which in this case is 8.60450832 × 10^105

Well I had hoped to get some serious thoughts on this, but c'est la vie. Thread closed.

Umm, I will first try Fermat's Factorization Method, find the smallest square exceeding this and keep subtracting this number. (But this is only useful when the two factors are adjacent).

You can also try the Pollard pho primality test. But I am not too familar with it, in fact, I am not familar too well with primality testing.