<p>That statement is not known to be true -- and I note that since you posted your question, it has been edited.</p>
<p>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).</p>
<p>We do know of a proof that if you can factor an arbitrary integer <span class="math-container">$n$</span> into two non-trivial factors <span class="math-container">$r,s$</span> (so that <span class="math-container">$n=rs$</span> and <span class="math-container">$1&lt;r&lt;n$</span>, <span class="math-container">$1&lt;s&lt;n$</span>), then you can completely factor <span class="math-container">$n$</span> into primes.  This is easy to accomplish, by just recursively applying the algorithm to <span class="math-container">$r,s$</span>.  This too might be what the author was thinking of.</p>
<p>See also <a href="https://cstheory.stackexchange.com/a/6733/5038">https://cstheory.stackexchange.com/a/6733/5038</a> (but beware that some of the other answers on that page are misleading or erroneous).</p>

CC BY-SA 4.0
2023-05-05T08:10:18.107Z
ah, I missed that post. Thanks a lot.
glS
CC BY-SA 4.0
2023-05-05T10:13:34.613Z
Another factor (no pun intended) to consider is that factoring semiprimes is enough for breaking cryptographic protocols such as RSA.
Emil Jeřábek
CC BY-SA 4.0
2023-05-05T20:21:10.740Z
@EmilJeřábek Yes -- although multi-prime RSA has been proposed, see e.g. https://cr.yp.to/papers/pqrsa-20170419.pdf
Charles
CC BY-SA 4.0
2023-05-05T07:23:48.140Z
2023-05-05T07:23:48.140Z
D.W.
<p>The <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="nofollow noreferrer">Wikipedia page about Shor's algorithm</a> currently contains the following sentence:</p>
<blockquote>
<p>A complete factoring algorithm is possible using extra classical methods if <span class="math-container">$N$</span> is a semiprime, that is, if it is the product of just two primes <span class="math-container">$p$</span> and <span class="math-container">$q$</span>; therefore the algorithm only needs to achieve that.</p>
</blockquote>
<p>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 &quot;extra classical methods&quot;.
I was however unable to find a reference or other mentions of this fact.</p>
<p>I found a few places discussing how/why factoring semiprimes is particularly difficult, for example <a href="https://crypto.stackexchange.com/a/74796/57005">this post on crypto.SE</a>, and other relevant Wikipedia pages such as <a href="https://en.wikipedia.org/wiki/Integer_factorization" rel="nofollow noreferrer">Integer factorization</a> and <a href="https://en.wikipedia.org/wiki/Semiprime" rel="nofollow noreferrer">Semiprime</a>.
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?</p>

<factoring>
Does being able to efficiently factor semiprimes allow to efficiently factor any integer?
glS
# Does being able to efficiently factor semiprimes allow to efficiently factor any integer?

(Asked by: username_0 on 2023-05-04)

The [Wikipedia page about Shor's algorithm](https://en.wikipedia.org/wiki/Shor%27s_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](https://crypto.stackexchange.com/a/74796/57005), and other relevant Wikipedia pages such as [Integer factorization](https://en.wikipedia.org/wiki/Integer_factorization) and [Semiprime](https://en.wikipedia.org/wiki/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?

**Tags:** factoring

---

## 1 answers

### Answer by username_1 on 2023-05-05. Score: 5 | Accepted answer

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, $1), 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).

> **Comments:**
> **username_0**: ah, I missed that post. Thanks a lot.  
> **username_2**: Another factor (no pun intended) to consider is that factoring semiprimes is enough for breaking cryptographic protocols such as RSA.  
> **username_3**: @EmilJeřábek Yes -- although multi-prime RSA has been proposed, see e.g. https://cr.yp.to/papers/pqrsa-20170419.pdf  

---

