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.

Schneier in 1996's Applied Cryptography says:

"Currently, a 129-decimal-digit modulus is at the edge of factoring technology"

In the intervening 15 years has anything much changed?

share|improve this question
2  
See en.wikipedia.org/wiki/… –  lhf May 10 '11 at 15:51
    
Perfect, want to submit that as an answer? –  noonand May 10 '11 at 15:56

3 Answers 3

up vote 5 down vote accepted

Please consult Wikipedia before posting a question. You can still ask about the Wikipedia article, of course.

See Integer factorization: Current state of the art.

share|improve this answer
    
I actually did but searched for the wrong thing. Finding nothing I turned to here instead and am glad I did so. By engaging with you here and following up on the links I learned so much more than I would have if I'd just found the answer myself. Awarding this the answer as it comes closest to answering my original question. Thanks! –  noonand May 12 '11 at 13:42

The same algorithm is used for factoring, the Number-Field Sieve. It's probably been optimized further. But the main difference between now and then is computing power. Since the asymptotic running-time of the NFS is "known", you can even extrapolate into the future (assuming your favorite version of Moore's law).

share|improve this answer
    
Thanks - I cannot vote up as I don't have enough rep. I hope you'll understand. –  noonand May 12 '11 at 13:44

For factoring RSA moduli (product of two large distinct primes), the Number Field Sieve is still king. It has two phases: a parallelizable sieving phase where we look for polynomials, then a non-parallelizable matrix reduction step that is usually done on a large computer.

If quantum computers ever become practical, they can factor integers via Shor's algorithm in polynomial time. In fact, this is the only known compelling application for them, but it's enough for the military to spend millions in the U.S. funding research on quantum computers.

Note: Peter Shor is a frequent contributor on this site.

share|improve this answer
    
It's Shor, not Schor. –  Brandon Carter May 11 '11 at 2:03
    
Blah, sorry. I had "Schorr" originally (probably confused with Claus Schnorr, another cryptographer) and I "fixed" the spelling from "Schorr" to "Schor". Thanks to J.M. –  Fixee May 11 '11 at 2:38
    
Thanks - I cannot vote up as I don't have enough rep. I hope you'll understand. –  noonand May 12 '11 at 13:43
    
@noonand: No problem, I appreciate the comment. :) –  Fixee May 12 '11 at 14:58

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.