# What's the best way to factor a 256-bit number?

Suppose $N$ is an RSA modulus (ie, it's the product of two distinct primes), 256 bits long. What is the best method to factor it?

Trial division is out of the question, Pollard's Rho is probably out as well (without significant parallelization). I doubt there are any online tools or math libraries that can handle this number (I think Wolfram Alpha uses Pollard's Rho algorithm).

Moduli up to 768 bits have been factored, and RSA Corp's (now defunct) challenge list doesn't even address numbers as small as 256 bits, so it must be pretty easy... but how?

-
alpertron.com.ar/ECM.HTM can factor integers in this range. –  Dave Radcliffe Mar 18 '11 at 8:36
@Dave R: Indeed, though it takes time. For me it spotted that 96919417854840572406751013870468351781780314562929621348544292575164020533599 was composite immediately but, after giving up on ECM, it used SIQS (Self Initializing Quadratic Sieve) and took 21 minutes to factor it. With a multicore processor it would have been faster. –  Henry Mar 18 '11 at 9:20