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.

up vote 2 down vote accepted

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.

  • I appreciate your answer. I myself have done some implementations and have similar evidence as yours. I was wondering if there is a theoretic upper bound (maybe with clever use of Groebner basis, or some lattice representation, or some theorem on cardinality of varieties in polynomial ideals). This depends of course on the vector $c=(c_1,\dots,c_k)$, but given the symmetry of the system, there may be a reasonable closed form. – Tal-Botvinnik Sep 14 at 12:38

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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