2
$\begingroup$

I am trying to solve a problem of breaking an amatuer cryptography.

The problem boils down to solving a combined system of linear and bilinear equations having $50$ unknowns.

For representational purposes, the equations look similar to the following, with $x$, $y$ and $z$ being the unknowns.

\begin{align} \begin{cases} 3x + 10y + 8z + 5xy &= 1470 \\ 2x + 10y + 3z + yz + xz &= 1210 \\ x + 5y + z + 3xy + 16xz &= 5540 \\ x + 3y + 8z + 12xy + 4yz &= 5110 \end{cases} \end{align}

The above system has the solution $x=10 , y=20, z=30$.

I want to know the method for solving these type of equations. Can gaussian elimination be applied on such a system ?

$\endgroup$
8
  • $\begingroup$ You say you have $50$ unknowns. Out of curiosity, how many equations do you have? Also, in average, how many terms are there per equation? (Since you have cross terms $x_i x_j$, simple Gaussian elimination would be difficult.) $\endgroup$
    – Tito Piezas III
    Aug 15, 2016 at 16:33
  • $\begingroup$ @RobertIsrael: Accdg to this wiki article, Maple has built-in functionality for such systems. However, what's the most number of equations and variables $x_i$ that Maple can handle when the system has no degree $n>1$ but includes cross terms $x_i x_j$? $\endgroup$
    – Tito Piezas III
    Aug 15, 2016 at 16:43
  • $\begingroup$ @TitoPiezasIII There are 40 equations. On average each have 3000 terms including cross ones. $\endgroup$
    – Extreme Coders
    Aug 15, 2016 at 16:44
  • $\begingroup$ So 50 variables, 40 equations, and 3000 terms per equation? Ouch. And an under-determined system at that. The wiki link above may point to alternative approaches. $\endgroup$
    – Tito Piezas III
    Aug 15, 2016 at 16:47
  • $\begingroup$ @TitoPiezasIII Thanks a lot. I will check. $\endgroup$
    – Extreme Coders
    Aug 15, 2016 at 16:57

1 Answer 1

Reset to default
1
$\begingroup$

solving equation (1) for $$z$$ we obtain $$-5/8\,xy-3/8\,x-5/4\,y+{\frac{735}{4}}=0$$ (I) plugging this in the second equation we obtain $$-5/8\,{x}^{2}y-3/8\,{x}^{2}-7/2\,xy+{\frac {1477\,x}{8}}-5/8\,x{y}^{2} -5/4\,{y}^{2}+190\,y-{\frac{2635}{4}} =0$$ (II) pliugging (I) in the third equation $$-{\frac {141\,xy}{8}}-10\,{x}^{2}y-6\,{x}^{2}+{\frac {23525\,x}{8}}+{ \frac {15\,y}{4}}-{\frac{21425}{4}}=0$$ (III) plugging (I) in the fourth equation we get $$11/2\,xy-5/2\,x{y}^{2}-5\,{y}^{2}+728\,y-2\,x-3640=0$$ (IV) solving (IV) for $$y$$ we obtain $$y=-{\frac {48\,{x}^{2}-23525\,x+42850}{80\,{x}^{2}+141\,x-30}}$$ (V) plugging this in (III) factorizing and simplifying we get $$ \left( x-10 \right) \left( 13120\,{x}^{4}-5741148\,{x}^{3}-54229691 \,{x}^{2}+11341510\,x+205150100 \right) =0$$ the rest do it by yourself.

$\endgroup$
2
  • 1
    $\begingroup$ The OP gave this system with $3$ unknowns only as an example. But his actual problem has $50$ unknowns. Since the system involves terms with $x_i$ and $x_i y_j$, the degree of the final equation would rise too fast using this approach. $\endgroup$
    – Tito Piezas III
    Aug 15, 2016 at 15:30
  • $\begingroup$ @TitoPiezasIII Yes, I wanted an approach that can be automated such as using matrix operations. Solving a 50 variable system by hand is not possible. $\endgroup$
    – Extreme Coders
    Aug 15, 2016 at 16:18

Your Answer

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

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