2
$\begingroup$

I want to programmatically solve the following system (here in size 3): $$ \left\{ \begin{array}{ll} x_1 y_1 &\equiv a_1 \pmod 2 \\ x_2 y_1 + x_1 y_2 &\equiv a_2 \pmod 2 \\ x_3 y_1 + x_2 y_2 + x_1 y_3 &\equiv a_3 \pmod 2 \\ \qquad\quad\space x_3 y_2 + x_2 y_3 &\equiv a_4 \pmod 2 \\ \qquad\qquad\qquad\space\space x_3 y_3 &\equiv a_5 \pmod 2 \\ \end{array} \right. $$ I found those academic papers that seem to be in the field:

However, I'm having hard time understanding them (I'm a computer scientist). Would anyone explain how to tackle this kind of problem, or point me to an appropriate ressource? Thanks.

$\endgroup$
  • 1
    $\begingroup$ So $a_1,a_2,\ldots,a_5$ are known and the others are variables? In that case the system of equations is about writing the quartic polynomial $$p(T)=a_1+a_2T+a_3T^2+a_4T^3+a_5T^4$$ as a product of two quadratics $$p(T)=f(T)g(T),$$ where $$f(T)=x_1+x_2T+x_3T^2$$ and $$g(T)=y_1+y_2T+y_3T^2.$$ Therefore I would do this as follows. 1) Factor $p(T)$. This is quite easy for quartics, and not difficult more generally as long as the degree doesn't blow up. 2) Find all the quadratic factors $f(T)$ (or factors of some other given degree), This is easy with the know factorization. $\endgroup$ – Jyrki Lahtonen Jan 7 '18 at 23:11
  • 1
    $\begingroup$ (cont'd) 3) find the matching $y$-polynomials $g(T)$ from the factorization. Of course, if the general class of systems that you want to solve doesn't fit under this umbrella, then we need something else. I would expect quadratic systems to fall, but I may be wrong. Somehow this reminds me of a Reed-Muller code decoding problem that was solved by Seroussi and Lempel by figuring out how to write an arbitrary symmetric matrix $A$ over $\Bbb{F}_2$ in the form $A=BB^T$ back in the day... :-) $\endgroup$ – Jyrki Lahtonen Jan 7 '18 at 23:14

Your Answer

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

Browse other questions tagged or ask your own question.