1
$\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 ?

|cite|improve this question|||||
$\endgroup$
  • $\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 '16 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 '16 at 16:43
  • $\begingroup$ @TitoPiezasIII There are 40 equations. On average each have 3000 terms including cross ones. $\endgroup$ – Extreme Coders Aug 15 '16 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 '16 at 16:47
  • $\begingroup$ @TitoPiezasIII Thanks a lot. I will check. $\endgroup$ – Extreme Coders Aug 15 '16 at 16:57
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.

|cite|improve this answer|||||
$\endgroup$
  • 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 '16 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 '16 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.