3
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ alpertron.com.ar/ECM.HTM can factor integers in this range. $\endgroup$ – Dave Radcliffe Mar 18 '11 at 8:36
  • 1
    $\begingroup$ @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. $\endgroup$ – Henry Mar 18 '11 at 9:20
2
$\begingroup$

Charles's nice answer to this question might be of interest. Briefly: look into ECM, or GNFS if ECM chokes.

$\endgroup$
2
$\begingroup$

The comment left by Dave R gives the best answer: ECM is outdone by SIQS for the semiprimes of interest and there are several freely-available implementations of SIQS. The one Dave R gives at http://www.alpertron.com.ar/ECM.HTM factors numbers of 256-bits in about 4 mins on my Dual-Core 2.8GHz Windows XP: set number of processors to 2 and set "New Curve" to zero in order to force SIQS (ECM will generally not help for semiprimes of this size).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.