Consider this equation :
$$q(x) = (a_0 + a_1 x + a_2 x^2 + \cdots + a_{r-1} x^{r-1}) \pmod {251} $$
then I'll find the value of
$$ q(1), q(2), q(3), \dots ,q(n) $$
with $r \le n$ and $ 0 <= a < 251 $
The question is:
Is it possible to reconstruct the polynomial given any subset of
$q(1), q(2), q(3), \dots ,q(n)$ with amount of subset is greater than or equal to $r$
I have tried it using Lagrange Interpolation method. Without the modulo, the polynomial is constructed perfectly. But using the modulo, sometimes it's giving different polynomial. Although the result is correct answer in terms of following the method correctly, it doesn't give the original polynomial I want.
Anything I missed out, or some misunderstanding regarding the concept of Lagrange Interpolation?
I got this problem from this paper on link below
Edit :
The equation above is at section 3.1 on this paper
Edit again :
Example. suppose the polynomial is $$ 100x^2 + 100 $$
and I will count the value without including the modulo :
$ q(1) = 200 $
$ q(2) = 500 $
$ q(3) = 1000 $
using the Lagrange Interpolation calculator on http://www.wolframalpha.com/input/?i=interpolating+polynomial+calculator
Of course it will return the original polynomial. But when count using the modulo
$ q(1) = 200 % 251 = 200 $
$ q(2) = 500 % 251= 249 $
$ q(3) = 1000 % 251 = 247 $
It will return different equation. I have done the calculation manually and using online solver on link above
The polynomial returned is :
$$ -51x^2/2 +251x/2 + 100 $$
Best Answer
Lagrange interpolation is nothing but a special case of CRT (Chinese Remainder Theorem). Namely, the special case where the ring is a ring of polynomials $\,K[x]\,$ over a field $\,K.$
Then we may apply CRT to the system $\ q(x) \equiv q(a_i) \pmod{x-a_i},\,$ because the $\,x-a_i\,$ are pairwise coprime (comaximal), since the $\,a_i\,$ are distinct, and the coefficient ring is field.
CRT yields a solution $\,q(x)\,$ that is unique modulo $\,g(x) = (x-a_1)\cdots (x-a_n).\,$ In particular there is a unique solution of degree $\,< \deg g.\,$ So one way to force your solutions to be unique is to reduce them mod $g$ to decrease the degree, and normalize the coefficients modulo $251,\,$ e.g. choose the least natural remainders mod $251$, i.e. those in the interval $[0,250],\,$ e.g. yours is
$\,{\rm mod}\ 251\!:\ {-51}\equiv 200,\,$ so $\,\color{#c00}{-51/2}\equiv 200/2\equiv \color{#c00}{100},\ $ and $\ \color{#0a0}{251\equiv 0}\ $ hence
$$\color{#c00}{-51/2}\,\ x^2 +\color{#0a0}{251}/2\,\ x + 100\, \equiv\, \color{#c00}{100}\, x^2 + 100$$