Factoring may be easier than you think


Factoring integers into prime factors has a reputation as an extraordinarily difficult problem. If you read some popular accounts, you get the impression that humanity has worked hard on this problem for centuries, if not millennia, and that the chances of an efficient algorithm are negligible. If true, that would be great, because some important cryptosystems rely on the difficulty of factoring. Unfortunately, it’s mostly hype based on wishful thinking. Enough people have tried to find efficient factoring algorithms that we can be confident the problem isn’t easy, but there’s no reason to think it’s impossible.

The first thing to realize is that until the advent of public key cryptography in the 1970’s, few people cared about factoring. Some people were interested in it for its intrinsic beauty, but nobody thought it was good for anything, and it certainly wasn’t the notorious unsolved problem it is today. If anything, it was mildly obscure.

Even today, how many researchers have ever seriously tried to find an efficient factoring algorithm? I don’t know, since most people who fail don’t announce their attempts (and who knows how much classified work there has been), but it’s not hard to estimate. Let’s say a serious attempt consists of several months of work by an expert, someone who knows enough number theory to read the literature on this problem. Then the number of people who have seriously tried must be on the order of magnitude of 100. It would be ridiculous to say “100 smart people tried and failed to solve this problem, so it’s clearly impossible,” but that’s what most claims regarding the difficulty of factoring amount to.