Integer Factorization problem: Given integers $N, M$, find an integer $d< M < N$ that divides $N$. Is it easier to find the value of a single bit? This problem is at least as hard as integer factorization. What is the best known upper bound on the complexity of finding the value of $i^{th}$ bit of $d$ ? I'm interested in algorithms that are asymptotically better than the best known integer factorization algorithm.
Bit complexity of integer factorization?
cc.complexity theory