Lagrange Interpolation for finite field GF(2^8), for Secret Reconstruction I'm using Lagrange's Interpolation technique to reconstruct the secret from a set of point pairs (x,y).
Since I only need the secret, not the whole polynomial, I have simplified the reconstruction process as follows:


  Let Secret $D = 10$, and we use a 3 out of 3 secret sharing scheme which generates 3 key pairs
      and all of them are needed to reconstruct the secret. We pick two random numbers as the coefficients.
      This gives us the polynomial $5x^2 + 2x + 10$.
      3 Points are generated from the polynomial: $(1, 17)$, $(2, 34)$, $(3, 61)$
      To get secret $D$, we only need to take care of the constant part of Lagrange's Polynomial.
  $$
\it{l}_{0} = \dfrac{(x-2)(x-3)}{(1-2)(1-3)} = \dfrac{(x-2)(x-3)}{2}
$$
  $$
\it{l}_{1} = \dfrac{(x-1)(x-3)}{(2-1)(2-3)} = \dfrac{(x-1)(x-3)}{-1}
$$
  $$
\it{l}_{2} = \dfrac{(x-1)(x-2)}{(3-1)(3-2)} = \dfrac{(x-1)(x-2)}{2}
$$
  
  By only considering the constant part of Lagrange's Polynomial (ignore $x$es),
      we can calculate secret $D$:
  
  $$
D = 17 \dfrac{(-2)(-3)}{2} + 34 \dfrac{(-1)(-3)}{-1} + 61 \dfrac{(-1)(-2)}{2}
= 10
$$
  
  which is our secret.


Now the same method should work for finite field GF(2^8) as long as the arithmetic are replaced with finite field arithmetic. However this is not the case:

unsigned int decodeByte(vector&lt;pair&lt;unsigned int, unsigned int&gt;&gt; keys) {
    int numKeys = keys.size();
    //extract the x's and y's from the vector
    vector&lt;int&gt; x;
    vector&lt;int&gt; y;
    for (int i = 0; i &lt; numKeys; i++) {
        x.push_back(keys[i].first); //extract x
        y.push_back(keys[i].second); //extract y
    }

    GF256elm result(0);
    for (int i = 0; i &lt; numKeys; ++i) {
        //calculate the constant term of lagrange interpolation polynomial
        GF256elm l(1);
        for (int j = 0; j &lt; numKeys; ++j) {
            if (i == j)
                continue;
            GF256elm nxj = GF256elm(x[j]); 
            GF256elm xi = GF256elm(x[i]); //xj
            GF256elm xj = GF256elm(x[j]); //xj
            GF256elm ximxj = xi - xj;  //xi - xj
            GF256elm prod = nxj / ximxj; // (-xj)/(xi-xj)
            l *= prod;
        }
        GF256elm product = GF256elm(y[i]) * l;
        result += product;
    }
    return result.getVal();
}


Basically what I'm doing here is I'm calculating $\dfrac{-2}{1-2}$, then multiply it with $\dfrac{-3}{1-3}$, then multiplying everything by 17, (which is the y value from the first point $(1, 17)$). This is the first term in D's equation above. I then go on and calculate the other two terms.

Problem is, instead of 10, I get 14 as my answer.

My Questions  


In finite field arithmetic, negating x ($-x$) is really $0 - x$, which is actually $0 \oplus x$ (XOR), and it ends up being $x$ itself, am I right?  
Is there anything wrong with my approach to finding the Secret $D$?


Additional info:  

My division and multiplication is implemented using table look up. This part of the code has been tested and its results are the same as other sources.

GF256elm&amp; GF256elm::operator*=(const GF256elm&amp; other) {
    int temp = (_logTable[val] + _logTable[other.val]) % 255;
    val = _expTable[temp];
    return *this;
}

GF256elm&amp; GF256elm::operator/=(const GF256elm&amp; other) {
    int t = _logTable[val] - _logTable[other.val];
    int temp =  ((t % 255) + 255) % 255;
    val = _expTable[temp];
    return *this;
}
I now see your problem; it's more fundamental than what my previous answer assumed.  You state:

Now the same method should work for finite field GF(2^8) as long as the arithmetic are replaced with finite field arithmetic. However this is not the case

where you interpret &quot;should work&quot; as &quot;coming up with the exact same answer&quot;.
Actually, that's not the case.  Your original example appears to be designed in the infinite field $Q$ (or some superfield); you then use the exact same shares, reinterpret them as $GF(2^8)$ points (in some unspecified representation), and then are confused that answers you get aren't precisely the same.
$Q$ and $GF(2^8)$ are both fields, but they are about as unlike as fields can get.  For example:

$2+2=4$  (in the field $Q$)
$2+2=0$  (in the field $GF(2^8)$)
$3 \times 3 = 9$  (in the field $Q$)
$3 \times 3 = 5$  (in the field $GF(2^8)$, in the most common representation)

Your original shares $(1, 17)$, $(2, 34)$, $(3, 61)$ were computed in $Q$; if they were computed in $GF(2^8)$, they would have lhad different values.  Therefore, it is not suprising that if you reconstruct them in a field other than what they were computed in, you'll come up with a different answer.  I recomputed your shares using the original polynomial (assuming a polynomial representation of $GF(2^8)$), and came up with the values $(1, 13)$, $(2, 26)$, $(3, 29)$
To test your code, you'll need to come up with your own shares, computing in the field you're using to reconstruct.
(You'll also need to fix up your multiplication logic, in case one of the shares happen to be the value 0)