Algorithms for factorization using the decision version

Question

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?

Answer 1

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.)