Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
Not a full answer, but hopefully a useful partial answer.
First of all, there is an obvious barrier. How do you specify $d$? If we simply wish to find this for any factor $d$ then there are several legitimate values for some of the bits. This means that really from a single bit you can't always tell where you have a trivial factor (say 1 or N) or a non-trivial factor. This means that in general the problem is likely to be as hard as factoring. If for example you there was a factor of hamming weight 2 with the last bit as 1, you would need to obtain all the bits to be sure that it was non-trivial (if for example the first $n-1$ bits you try are all 0 except for the very least significant bit).
However it is possible to obtain relationships between bits in two factors.
This is easy to do for less significant bits, but becomes harder as you move up. If the complexity didn't increase in one direction, it would obviously lead a more efficient algorithm for factoring.
For example, take $N=pq$. Then $p=2p' + p_0$ and $q=2q' + q_0$. where $p_0$ and $q_0$ are single bits. Then $N=4p'q' + 2(p'q_0 + q'p_0) + p_0q_0$, so $N \equiv p_0 q_0 \mbox{ mod }2$. If N is odd, then $p_0 = q_0 = 1$, and so $N=4p'q' + 2(q' + p') + 1$. Now, if instead it was 0, 2 would have been a non-trivial factor, so lets ignore that case, and consider only $p_0 = q_0 = 1$. We can take $p= \sum_{i=0}^n 2^i p_i$ and $q= \sum_{i=0}^n 2^i q_i$.
Then we have $N = \sum_{i,j=0}^n 2^{i+j} p_i q_j$. This implies that $N \equiv \sum_{i=0}^n \sum_{j=0}^{m-i-1} 2^{i+j} p_i q_j \mbox{ mod }2^m$. This then gives you a relationship between the $m$ least significant bits of $p$ and $q$. Since we can also obtain similar relationships for $(m-1) ... 1$ this gives us a set of $m$ constraints that the bits need to satisfy, each containing at most $m$ terms in the sum. Naively, one could consider testing all possible values of $p_{m-1}...p_0$ and $q_{m-1}...q_0$,but in practice it is more efficient to simply find all possible pairs for the $2^1$ constraint, than use only these as the less significant bits when checking which pairs satisfy the $2^2$ constraint and so on up to the $2^m$ constraint. Unfortunately, how effective this is will depend on the number of factors, as well as other things, since if a number has a large number of small factors, there will be a huge number of possible ways of combining these, and so a huge number of legitimate strings for the least significant bits.
For example, if we consider $N = x!$, then we have $\ln{N} \approx x \ln x - x$. So the number of bits in $N$ scales roughly as $x$ times the number of bits in $x$. Now, if we consider how many different possible ways there are to find a factor of $N$ there are, we know that it must be at least $2^{x-1}$, since this is the number of ways of multiplying a subset of ${2 ... x}$, so there are an exponential number of factors. Even if we consider factors less than $\frac{x}{2} \ln x$ bits (less than approx $\sqrt{n}$) we find that there are more than $2^{\frac{x}{2}}$ possibilities, and thus more than $2^{\frac{x}{2}}$ unique bit strings satisfying all constraints up to $2^{\frac{x}{2}\ln x}$. Thus this approach is necessarily exponential in the worst case.
In the worst case to enumerate all such pairs (testing each possible pair) takes time $O(m^2 2^{2m})$.
Hope this is useful.
If the size of output is not large (say polynomial), then one can compute the function from its bit-graph easily.
In particular, since the size of $d$ will be linear in the size of $N$, one can compute $d$ from your problem in linear-time and logarithmic space, i.e. the bit-graph function is not easier than the original function in this case. (For problem to make sense, I assume that we are looking for a well-defined $d$, say the smallest or largest non-trivial divisor.)
The bit-graph complexity is more interesting if the size of output is large, such as functions $n!$ or $n^m$.
