3

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

http://bit.ly/1eNTQgI

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 $$

Yoseph Haryanto
  • 33
  • Lagrange should give you back the original polynomial. Could you give an example of a polynomial that was not correctly recovered? I suspect that you may have not fully appreciated the fact the original polynomial shoul also have coefficients in the field $\Bbb{Z}_{251}$. – Jyrki Lahtonen Dec 29 '13 at 16:40
  • 1
    Added new information regarding your comment :) – Yoseph Haryanto Dec 30 '13 at 04:32
  • Ok. My suspicion confirmed. Modulo $251$ you have $251=0$, so also $251/2=0/2=0$. Similarly $-51=-51+251=200$, so $-51/2=200/2=100$. – Jyrki Lahtonen Dec 30 '13 at 05:50

1 Answers1

3

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$$

Bill Dubuque
  • 272,048
  • Wait. I'm having a quite hard time digesting your answer. I'll try to read it carefully. – Yoseph Haryanto Dec 30 '13 at 04:34
  • @Yoseph I updated my answer to address your newly added example. – Bill Dubuque Dec 30 '13 at 04:43
  • I got it. So basically when operating modulo on fraction, i cannot use it in form real number? I was having a dead end because I process the fraction into a real number first :) – Yoseph Haryanto Dec 30 '13 at 04:48
  • Anyway, thanks a lot! You saved my day – Yoseph Haryanto Dec 30 '13 at 04:52
  • @Yoseph If $,b,$ is coprime to the modulus then $,b^{-1} = 1/b,$ uniquely exists, so the fraction $, x = a/b = ab^{-1}$ uniquely exists, i.e. the equation $,b, x\equiv a,$ has a unique solution. If $,b,$ is not coprime to the modulus then the equation may have no solutions, or more than one solution. – Bill Dubuque Dec 30 '13 at 04:53