how to solve system of quadratic equations (mod N)

Question

Given a two equations: $${(ax_1 + b)}^2 = c_1 \pmod N$$ $${(ax_2 + b)}^2 = c_2 \pmod N$$

• $N=p.q$
• $p$ and $q$ are large primes
• $x_1, x_2$ and $c_1, c_2$ are known

Is it computationally feasible to solve this system for $a$ and $b$? If not prove that the problem is intractable. Could it help if we have more than two equations?

Answer 1

First we have to make sure that the c_i are quadratic residues mod N, usind Legendre symbols. After that we solve each equation in turn and take the intersection of the solution sets.