Ellen Chang

Answered

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({2}^{m}).$. 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}-({y}_{0}+(\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}})({l}_{1}-{x}_{0}))}{({l}_{1}-{x}_{0})({l}_{1}-{x}_{1})}$

${M}_{2}=\frac{{k}_{2}-({y}_{0}+(\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}})({l}_{2}-{x}_{0}))}{({l}_{2}-{x}_{0})({l}_{2}-{x}_{1})}$

${M}_{3}=\frac{{k}_{3}-({y}_{0}+(\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}})({l}_{3}-{x}_{0}))}{({l}_{3}-{x}_{0})({l}_{3}-{x}_{1})}$

${M}_{4}=\frac{{k}_{4}-({y}_{0}+(\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}})({l}_{4}-{x}_{0}))}{({l}_{4}-{x}_{0})({l}_{4}-{x}_{1})}$

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?

${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({2}^{m}).$. 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}-({y}_{0}+(\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}})({l}_{1}-{x}_{0}))}{({l}_{1}-{x}_{0})({l}_{1}-{x}_{1})}$

${M}_{2}=\frac{{k}_{2}-({y}_{0}+(\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}})({l}_{2}-{x}_{0}))}{({l}_{2}-{x}_{0})({l}_{2}-{x}_{1})}$

${M}_{3}=\frac{{k}_{3}-({y}_{0}+(\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}})({l}_{3}-{x}_{0}))}{({l}_{3}-{x}_{0})({l}_{3}-{x}_{1})}$

${M}_{4}=\frac{{k}_{4}-({y}_{0}+(\frac{{y}_{1}-{y}_{0}}{{x}_{1}-{x}_{0}})({l}_{4}-{x}_{0}))}{({l}_{4}-{x}_{0})({l}_{4}-{x}_{1})}$

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?

Answer & Explanation

Ordettyreomqu

Expert

2022-07-03Added 22 answers

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.

${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.

Most Popular Questions