Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
alpertron.com.ar/ECM.HTM can factor integers in this range. –  Dave Radcliffe Mar 18 '11 at 8:36
1  
@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

2 Answers 2

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

share|improve this answer
up vote 1 down vote accepted

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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