# Interpolation problem

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?

-
You want the 4-degree interpolant? –  Rustyn Jan 20 '13 at 0:46
yes, that is the one i want ... –  Jasmin Jan 20 '13 at 0:48
For those of us not familiar with Octave, can you explain what $((157 -136,75x + 133, 2083x^2 -61, 25x^3 +8,7917x^4))$ is supposed to be? –  George V. Williams Jan 20 '13 at 0:50
@GeorgeV.Williams That is his proposed 4-degree polynomial interpolant given those 5 points, (I believe this is the polynomial is program is spitting back @ him). –  Rustyn Jan 20 '13 at 0:53
What i'm trying to do, is descibed here en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing –  Jasmin Jan 20 '13 at 0:58

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.
@Andreas: See this page, Example 4. It seems that you want something like F := Dom::IntegerMod(257): P := interpolate([XList, YList], values, [X, Y], F). –  TMM Jan 20 '13 at 1:25
You basically want to solve $Ax \equiv b \mod 257$, where $$A = \left(\begin{matrix} 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 16 & 8 & 4 & 2 & 1 \\ 81 & 27 & 9 & 3 & 1 \\ 256 & 64 & 16 & 4 & 1\end{matrix}\right), \quad x = \left(\begin{matrix} a_4 \\ a_3 \\ a_2 \\ a_1 \\ a_0 \end{matrix}\right), \quad b = \left(\begin{matrix} 157 \\ 101 \\ 67 \\ 4 \\ 72 \end{matrix}\right).$$ The solution will be $(a_4, a_3, a_2, a_1, a_0) = (148, 3, 251, 56, 157)$. –  TMM Jan 20 '13 at 1:39