 Ellen Chang

2022-07-02

Solve a set of non linear Equations on Galois Field
${M}_{1}=\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}}$
${M}_{2}=\frac{{y}_{2}-{y}_{0}}{{x}_{2}-{x}_{0}}$
${M}_{1},{M}_{2},{x}_{1},{y}_{1},{x}_{2},{y}_{2},$, are known and they are chosen from a $GF\left({2}^{m}\right).$. I want to find ${x}_{0},{y}_{0}$I ll restate my question. Someone chose three distinct ${x}_{0},{x}_{1},{x}_{2}$, as well as ${y}_{0},{y}_{1},{y}_{2}$, then computed ${M}_{1},{M}_{2}$, and finally revealed ${M}_{1},{M}_{2},{x}_{1},{y}_{1},{x}_{2},{y}_{2}$, but not ${x}_{0},{y}_{0}.$ to us.All the variables are chosen from a Galois Field.
I want to recover the unknown ${x}_{0},{y}_{0}.$. Is it possible to accomplish that?
If a set of nonlinear equations have been constructed with the aforementioned procedure e.g.
${M}_{1}=\frac{{k}_{1}-\left({y}_{0}+\left(\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}}\right)\left({l}_{1}-{x}_{0}\right)\right)}{\left({l}_{1}-{x}_{0}\right)\left({l}_{1}-{x}_{1}\right)}$
${M}_{2}=\frac{{k}_{2}-\left({y}_{0}+\left(\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}}\right)\left({l}_{2}-{x}_{0}\right)\right)}{\left({l}_{2}-{x}_{0}\right)\left({l}_{2}-{x}_{1}\right)}$
${M}_{3}=\frac{{k}_{3}-\left({y}_{0}+\left(\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}}\right)\left({l}_{3}-{x}_{0}\right)\right)}{\left({l}_{3}-{x}_{0}\right)\left({l}_{3}-{x}_{1}\right)}$
${M}_{4}=\frac{{k}_{4}-\left({y}_{0}+\left(\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}}\right)\left({l}_{4}-{x}_{0}\right)\right)}{\left({l}_{4}-{x}_{0}\right)\left({l}_{4}-{x}_{1}\right)}$
where ${x}_{0},{y}_{0}{x}_{1},{y}_{1}$ are the unknown GF elements. Can I recover the unknown elements?
My question was if the fact that the set of equations is defined on a Galois Field imposes any difficulties to find its solution.
If not I suppose that the set can be solved. Is this true? Ordettyreomqu

Expert

The first system can be solved in the usual way, provided the "slopes" ${M}_{i}$i are distinct. Solve each for the knowns ${y}_{k}$, $k=1,2$ and subtract. You can then get to
${x}_{0}=\frac{{M}_{2}{x}_{2}-{M}_{1}{x}_{1}-{y}_{2}+{y}_{1}}{{M}_{2}-{M}_{1}},$
and then use one of the equations you already formed with this ${x}_{0}$ plugged in to get ${y}_{0}.$. Since this method only uses addition/subtraction multiplication/(nonzero)division it works in any field, in particular in your Galois field.

Do you have a similar question?