Interpolation problem

Question

I have the equation $f(x)=148x^4 + 3x^3 + 251x^2 + 56x + 157$.

This equation gives us the points below.

$(0,157),(1,101), (2,67), (3,4), (4,72)$

I want to interpolate this points in a $4$ degree polynomial, to get the equation $f(x)$ above.

However, when I try to make the interpolation using matrices, with Octave, i get a different equation $((157 -136, 75 x + 133,2083 x^2 - 61, 25 x^3 +8, 7917x^4))$. Does anyone knows what is happening, and how I can fix this?

Thanks in advance.

Answer 1

Shamir's secret sharing scheme uses finite field arithmetic instead of integer arithmetic, and in your example, it seems that the field $\mathbb{Z}_{257}$ was used. For example, modulo $257$ we indeed have $f(1) = 615 \equiv 101 \mod 257$, but your polynomial does not satisfy $f(1) = 101$ over the reals. So if you try to interpolate this polynomial over the reals, you will get a different function.

Note that those five points uniquely determine a degree-4 polynomial over the reals, which is the one you mention, but it is not the function $f$ you are looking for.