A more tractable question would be to verify that the given number is
not itself a prime, esp. in light of the price offered.
The world record for (general purpose algorithm) prime factoring as of
May, 2005 was RSA-200, a 200 decimal digit number, in which the
initial sieving required 55 CPU years but less than two calendar years
thanks to the magic of parallel computing:
http://en.wikinews.org/wiki/200_digit_number_factored
If I counted correctly, the number matt911-ga inquires about here has 232 digits.
In broad terms the strategy is to find two unequal nonzero integers
X,Y such that X^2 is congruent to Y^2 mod N, where N is the value
given by matt911-ga. Sieving refers to going through a lot of large
numbers X to see what values X^2 mod N can be factored completely (or
mostly so) into manageably small primes (the prime base).
After a significant number of such factorizations are available, one
can set up a homogeneous linear system over the simple field Z/2Z,
essentially trying to produce a handful of nontrivial solutions that
correspond to perfect squares.
With a certain positive probability, N will not divide either (X+Y) or
(X-Y), only their product, which implies the prime factors of N split
between these (easily known) factors of X^2 - Y^2. So with enough
sieving at the front end, one gets a factorization of N will chance as
close to 1 as you please.
regards, mathtalk-ga |
