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?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
All of the following algorithms either find a complete factor or a complete non-trivial factorization:
Trial division.
Pollard rho.
Pollard $p-1$ and its variants, including the elliptic curve method (ECM).
Shanks' SQUFOF.
Quadratic sieve (QS).
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.)
answered May 25, 2015 at 4:47