2
$\begingroup$

I have an input number c of n bits and its prime factorization. I want to find a divisor of c with certain fixed bits "f". For example:

INPUT:
c=1100011 (99) (n=7)
prime factorization = 11,11,1011 (3,3,11)
f=0??1?0?

OUTPUT:
o=0001001 (9)

Unfortunately, it's no use to check all divisors, because according to http://en.wikipedia.org/wiki/Divisor there may be up to O(sqrt(2^n)) divisors, which is exponential.

$\endgroup$
3
$\begingroup$

Here is one special case that is solvable a bit more efficiently than brute force. Suppose all of the fixed bits are consecutive and in the least significant bits. For instance, we are given the desired value for the low $k$ bits. Then this problem amounts to asking whether there is a divisor $d$ of $c$ such that $d \equiv f \pmod{2^k}$.

In other words, if $T$ is the multiset of prime factors of $c$, we are looking for a submultiset $S \subseteq T$ such that

$$\prod_{x \in S} x \equiv f \pmod{2^k},$$

where $f,k,T$ are given. Let me sketch an algorithm for this special case.

How can we find a solution to this equation without enumerating all $2^{|T|}$ submultisets? One way is to take discrete logs and reduce this to a subset sum problem. In particular, the multiplicative group $(\mathbb{Z}/2^k\mathbb{Z})^*$ is isomorphic to $(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/2^{k-2}\mathbb{Z})$. Let $\varphi$ be an isomorphism that maps $(\mathbb{Z}/2^k\mathbb{Z})^* \to (\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/2^{k-2}\mathbb{Z})$. Then, we search for a $S$ such that

$$\sum_{x \in S} \varphi(x) = \varphi(f).$$

So, if we can compute $\varphi$ efficiently, this basically reduces to a subset sum problem modulo $2^{k-2}$. And it turns out that $\varphi$ can be computed efficiently using Hensel lifting (basically, you find the discrete log of $x$ modulo 8, then modulo 16, then modulo 32, and so on; at each step there are only two possibilities for the discrete log, so you try them both). So, you compute $T^* = \{\varphi(x) : x \in T\}$ and $f^* = \varphi(f)$ and then try to find a submultiset $S^* \subseteq T^*$ such that

$$\sum_{y \in S^*} y = f^*.$$

This is a subset sum problem modulo $2^{k-2}$ (if you allow me to handwave over the $\mathbb{Z}/2\mathbb{Z}$ part of the range of $\varphi$).

And finally, there are algorithms for the subset sum problem that are more efficient than brute force trial-and-error of all subsets. This then gives you an algorithm for your original problem, in the special case where all the fixed bits are consecutive and in the least least significant bits.


This connection also suggests that your problem is probably not in P. In particular, it appears that we can show that your problem is at least as hard as subset sum, which is known to be NP-hard. Therefore, it looks like your problem will be NP-hard, too.

$\endgroup$
  • $\begingroup$ Thanks for your interesting answer. It seems that subset-sum can be reduced to "subset multiplication (mod 2^c)" and the latter to my problem. I'm going to learn about the discrete log and the notation for multiplicative groups. $\endgroup$ – Albert Hendriks Feb 25 '15 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.