World's most popular travel blog for travel bloggers.

# Is it Polynomial to decide whether any product of input numbers satisfies a boolean expression?

, ,
Problem Detail:

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.

###### Asked By : Albert Hendriks

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.