4

The Wikipedia page about Shor's algorithm currently contains the following sentence:

A complete factoring algorithm is possible using extra classical methods if $N$ is a semiprime, that is, if it is the product of just two primes $p$ and $q$; therefore the algorithm only needs to achieve that.

The sentence is not very clear, but if I'm interpreting correctly, they are saying that if we are able to factor efficiently semiprimes, then we are able to factor efficiently any integer, using "extra classical methods". I was however unable to find a reference or other mentions of this fact.

I found a few places discussing how/why factoring semiprimes is particularly difficult, for example this post on crypto.SE, and other relevant Wikipedia pages such as Integer factorization and Semiprime. I didn't, however, find mentions or references to the statement that the Wikipedia page seems to be hinting at. Is the statement accurate? If so, why techniques are used to obtain this reduction?

glS
  • 142
  • 7

1 Answers1

5

That statement is not known to be true -- and I note that since you posted your question, it has been edited.

We do not know of any proof that if you can factor products of two primes, you can factor all integers. However, all reasonable algorithms that we know of for factoring products of two primes also immediately generalize to factoring arbitrary integers; perhaps this is what the author was thinking of. Also, for all reasonable algorithms that we know of, factoring products of two large primes is the hardest case (it takes at least as much work as factoring products of three or more primes).

We do know of a proof that if you can factor an arbitrary integer $n$ into two non-trivial factors $r,s$ (so that $n=rs$ and $1<r<n$, $1<s<n$), then you can completely factor $n$ into primes. This is easy to accomplish, by just recursively applying the algorithm to $r,s$. This too might be what the author was thinking of.

See also https://cstheory.stackexchange.com/a/6733/5038 (but beware that some of the other answers on that page are misleading or erroneous).

D.W.
  • 12,054
  • 2
  • 34
  • 80