<p>All of the following algorithms either find a complete factor or a complete non-trivial factorization:</p>

<ol>
<li><p>Trial division.</p></li>
<li><p>Pollard rho.</p></li>
<li><p>Pollard $p-1$ and its variants, including the elliptic curve method (ECM).</p></li>
<li><p>Shanks' SQUFOF.</p></li>
<li><p>Quadratic sieve (QS).</p></li>
<li><p>Number field sieve (NFS).</p></li>
</ol>

<p>As far as I understand this list includes all algorithms actually used to factor integers in real life.</p>

<p>Finding just one bit of a factor sounds very unnatural to me, and I can't imagine an algorithm which can find one bit without finding all bits. (Even the SAT algorithm for factorization will find all bits at once.)</p>

CC BY-SA 3.0
2015-05-25T04:47:00.503Z
2015-05-25T04:47:00.503Z
Yuval Filmus
<p>Are there any practical algorithms for integer factorization that work by solving the decision version of the problem $\log N$ times to isolate a factor? Or is the decision version of only theoretical interest?</p>

<factoring>
Algorithms for factorization using the decision version
Elliot Gorokhovsky
# Algorithms for factorization using the decision version

(Asked by: username_0 on 2015-05-24)

Are there any practical algorithms for integer factorization that work by solving the decision version of the problem $\log N$ times to isolate a factor? Or is the decision version of only theoretical interest?

**Tags:** factoring

---

## 1 answers

### Answer by username_1 on 2015-05-25. Score: 6 | Accepted answer

All of the following algorithms either find a complete factor or a complete non-trivial factorization:

1. Trial division.
2. Pollard rho.
3. Pollard $p-1$ and its variants, including the elliptic curve method (ECM).
4. Shanks' SQUFOF.
5. Quadratic sieve (QS).
6. Number field sieve (NFS).

As far as I understand this list includes all algorithms actually used to factor integers in real life.

Finding just one bit of a factor sounds very unnatural to me, and I can't imagine an algorithm which can find one bit without finding all bits. (Even the SAT algorithm for factorization will find all bits at once.)


---

