Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
What i'm trying to do, is descibed here en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing –  Jasmin Jan 20 '13 at 0:58
show 5 more comments

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

share|improve this answer
    
yes, this was the field that was used! :) Thank you :) But do you know what steps i should follow in order to find the function i am looking for? In addition do you know how to interpolate this points using matlab in the field Z*257? I don't know very match, and i really appreciate your help. –  Jasmin Jan 20 '13 at 1:18
    
@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
    
Thank you. i will study the page. Do you also know how to do this, by hand? i mean, what steps i should follow in order to find out the function I am looking for without using a computer? –  Jasmin Jan 20 '13 at 1:28
    
to do by hand see this link: link, @Andreas –  Rustyn Jan 20 '13 at 1:30
    
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
show 2 more comments

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.