Counting the number of binary solutions of quadratic system

Question

I have a quadratic system of equations related to a balanced RSA modulus $n=pq$ (i.e. $\log p\approx\log q$), and I want to give an upper bound on the number of solutions. Indeed, let $p_i,q_i$ be binary variables, and let $c_i$ be integers such that $0\leq c_i\leq i+1$.

$$\left\{\begin{array}{ll} p_0q_0&=c_0\\ p_0q_1+p_1q_0 &= c_1\\ p_0q_2+p_1q_1+p_2q_0 &= c_2\\ p_0q_3+p_1q_2+p_2q_1+p_3q_0 &= c_3\\ &\vdots \\ \sum_{i+j=k}p_iq_j &= c_k \end{array}\right.$$

Given the fact that one solution to this system exists (i.e., the complete factorization $p,q$), I wanted to quantify the number of other solutions to this quadratic system.

I know that there are lattice representations that help in this direction, and probabilistic and deterministic algorithms that actually solve them. But I want just to have an estimate on the number of solutions, maybe taking into account the symmetry of the system. A hint or reference will be highly appreciated.

Answer 1

Actually, it would appear that a standard breadth-first search works for this specific problem.

The algorithm tracks all the solutions that satisfy the equation up to bit $n$, and for each such solution, it considers all possible extensions to bit $n+1$ (there are four), and whether they satisfy the condition on $c_{n+1}$.

If you use this algorithm on the standard factorization problem, it fails miserably (as the number of intermediate solutions approximately doubles at each step until you hit the half-way point); this happens because each extension satisfies the next condition with probability 0.5. However, for this problem, the condition that needs to be satisfied is $\sum_{i+j=k}p_iq_j = c_k$, which for large $k$ has a considerably smaller probability of holding for an incorrect solution, and hence incorrect solutions are pruned much faster.

I threw together an implementation, and it showed promise; given the arbitrarily product $314159 \times 271829$, such a state search gave a maximum of 22 intermediate solutions (11, really, as I counted solutions with swapped $p$ and $q$ separately), and this was after processing bit 11.

This finds all the solutions fast enough that you should be able to use this to obtain a count.