Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have the following set of equations:

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

Does the previous set of equations is solvable?

And more...

If I have the following set of equations:

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

As Dilip Sarwate clarified the set of equations is constructed by someone who " chose three distinct x0,x1,x2, as well as y0,y1,y2, then computed M1, M2, and finally revealed $M_1,M_2,x_1,y_1,x_2,y_2$ but not $x_0,y_0$ to us" i.e. it is known that the system has solution.

My question was: Can I recover the $x_0, y_0$ or in the second set of equations can I recover $x_0, x_1, y_0, y_1$ and generally in nonlinear sets to recover the respective $x_i, y_i$ by the provided info, on a GF? and the main point of my question: Does the fact that the set of equations is defined on a Galois Field impose any difficulties to find its solution?

I was not sure that it is possible to compute the solution of the problem with the aforementioned parameters on a Galois Field.

As Dilip Sarwate stated in his answer the solution of the previous problem can be recovered for linear and nonlinear equations.

share|improve this question
2  
Since you are working in a field, and presuming all values are defined, both your equations can be rewritten as linear equations. You got two linear equations with two unknown, so the answer is "yes". –  Henrick Hellström Jul 18 '13 at 8:20
    
If the set of equations is larger (as in the edited question) the answer still remains the same? –  Herc11 Jul 18 '13 at 9:23
1  
I thinks that it is unsolvable because there would be 3 unknown variables $$a=y_1-y_0, b=y_2-y_0, and x_0$$. What's are you tring to ssay with your question? –  Herc11 Jul 18 '13 at 12:24
1  
i think that as you stated the problem, the set of equations is unsovalble. It is different to know a,c than knowing k=a-c. –  Herc11 Jul 18 '13 at 12:49
2  
Could you edit your question so (1) it is clear how it relates to cryptography? –  Paŭlo Ebermann Jul 20 '13 at 19:07
show 6 more comments

1 Answer 1

There have been extensive comments by the OP on this question as well as a related one and its answers and the consensus don't seem to be converging at all to anything sensible.

Broadly speaking, the field in which we are operating influences the answer to the question of whether a system of equations has solutions or not to some extent, but not in the ways that the OP thinks it does. Whether we are operating in a prime field or an extension of a prime field (what the OP calls gf or GF) has relatively little to do with the matter. In particular, for linear equations, the general theory of linear equations over a field usually has more to say about the matter than the identity of the field.

As Henrick Hellström has pointed out in a comment on the question, the first set of equations in the OP's question can be converted into a pair of linear equations in the unknowns $x_0$ and $y_0$, say $$\begin{align} a_{11}x_0 + a_{12}y_0 &= b_1\\ a_{21}x_0 + a_{22}y_0 &= b_2\end{align}$$ where the $a_{ij}$ and the $b_k$ are functions of the known quantities $M_1, M_2, x_1, y_1, x_2, y_2$. I refuse to calculate and state explicitly what the $a_{ij}$ and the $b_k$ are in terms of the known quantities. I will differ from Henrick slightly, though, in that I do not think that these equations are solvable for each and every choice of $M_1, M_2, x_1, y_1, x_2, y_2$. This has nothing to do with whether these quantities belong to GF$(2^m)$ or GF$(p^m)$ for $p > 2$ or GF$(p)$ and everything to do with basic linear equation theory: the matrix might be singular for some choices of $M_1, M_2, x_1, y_1, x_2, y_2$ in which case we get multiple solutions rather than a unique solution, or the matrix might be singular and the equations might be inconsistent in which case no solution exists.

All this, however, as well as the OP's questions about other equations is irrelevant in the context of Shamir's secret sharing scheme which is referenced in the other question but not in this one but which I believe is the reason for these questions.

If 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, then we can find $x_0$ and $y_0$ from the given relationships, and inconsistency is not an issue. Note the requirement that $x_0, x_1, x_2$ be distinct which allows the unnamed someone to avoid the heartbreak of division by $0$ when computing $M_1$ and $M_2$.

Similar remarks apply to the nonlinear equations in the OP's question as well.

share|improve this answer
    
When I tried to solve a system of quadratics I found out that ${x_0}^{2}$ has come up. I think that I should have to compute the square root of the x0. Is it possible in GF? –  Herc11 Jul 25 '13 at 11:01
1  
It seems that these questions will never converge... In a finite field GF$(2^m)$, every element has a square root (not true in GF$(p^m)$ for $p > 2$) and the square root can be found easily. One way that always works is to square the element $m-1$ times: $$\sqrt{x_0} = \underbrace{((\cdots ((x)^2)^2\cdots)^2)^2} ~~~ m-1 ~\text{squarings}$$ More efficient methods use the properties of the irreducible polynomial used to define the field, or log tables, etc. –  Dilip Sarwate Jul 25 '13 at 12:35
    
Ok. The same stands for e.g.$\sqrt[3]{x_0}$ or more generally $\sqrt[n]{x_0}$ ? I am asking because in some cases the system may have 10 unknonws and 10 equations. Thus, powers such as ${x_0}^{10}$ will come up and the computation of $\sqrt[10]{x_0}$ will be needed. –  Herc11 Jul 25 '13 at 12:48
1  
Sigh.... No, you cannot use the idea mentioned in my previous comment for square roots for other roots in GF$(2^m)$. The kinds of equations you are looking to solve seem to be closely related to Lagrange interpolation and thus should not need $n$-th roots (or square roots for that matter) in the solution process, but if you feel that they do, then to each his own. –  Dilip Sarwate Jul 25 '13 at 14:47
    
Lagrange interpolation does not need n-th roots, but if you try to solve the problem posted in the question I think that they may be needed. Once again, Can I compute roots $\sqrt[1/n]{x}$? –  Herc11 Jul 25 '13 at 14:55
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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