Consider we has a polynomial $P=(x-\beta)g(x)$, where $\beta \leftarrow \mathbb{Z}_p$, $p$ is a large prime, and $g(x)$ is a non-zero polynomial.

Here degree of $P$ is fixed $n$. We evaluate $P$ at $(x_1,..., x_{n+1})$. So we get $(y_1,...,y_{n+1})$ where $P(x_i)=y_i$.

Question: Given $n$ pairs $(x_1,y_1),...,(x_n,y_n)$ we interpolate a polynomial $P'$ of degree at most $n-1$.What is the probability that $P'$ has root $\beta$ too?

TBN: $x_i\neq\beta$

edit: $x_i\neq x_j$ and $x_i \in \mathbb{Z}_p$ but $x_i$'s are not necessarily picked uniformly at random

  • $\begingroup$ When you say "given $n$ pairs", you mean a random sample of the $n+1$ pairs above, not necessarily the first $n$, correct? Also, $P'$ is not necessarily the derivative of $P$? $\endgroup$ – Chester Aug 26 '15 at 13:32
  • $\begingroup$ @Chester Yes is the answer for both of your questions. $\endgroup$ – user13676 Aug 26 '15 at 13:33
  • $\begingroup$ Do you know anything about the initial $(x_1,\ldots,x_{n+1})$? are the $x_i$ distinct? are the $x_i$ drawn according to some distribution, e.g. uniform on some interval? $\endgroup$ – Chester Aug 26 '15 at 14:25
  • $\begingroup$ @Chester Yes $x_i$'s are distinct values. They are elements of the field, but we do not know about their distribution; because, in the security context they are taken by a malicious party. However, $\beta$ is a uniformly random value. $\endgroup$ – user13676 Aug 26 '15 at 14:30
  • 1
    $\begingroup$ Using the Lagrange interpolant for $P'$, $$P'(\beta) = 0 \Rightarrow \sum_{i=1}^n (x_i-\beta)g(x_i)\prod_{k\neq i}^n\frac{\beta-x_k}{x_i-x_k} = 0 \Rightarrow \sum_{i=1}^n \frac{g(x_i)}{\prod_{k\neq i}^nx_i-x_k}=0$$ I'm not really sure that you could say anything about the probability about the latter being zero without assumptions on the distribution of $x_i$. Even so, this looks quite nasty. Perhaps there's a nicer way. $\endgroup$ – Chester Aug 26 '15 at 18:53

Since $P$ has degree $n$ and $P'$ has degree $n-1$ at most, $P-P'$ has degree $n$, so it has $n$ distincts roots at most. Since $P(x_i)=y_i=P'(x_i)$ for $i\in\{1,\dots,n\}$, $P'(\beta) \neq P(\beta)=0$, so $P'$ cannot have $\beta$ has a root.

  • $\begingroup$ Could you please have a look at this question if you have time. $\endgroup$ – user13676 Aug 27 '15 at 8:44
  • $\begingroup$ Imagine we have $\vec{x}=(x_1,...x_n)$ and two polynomials $P_1$ and $P_2$. Both's degree are smaller than $n−1$ but their product $P_1\cdot P_2$ has a degree greater than $n−1$. $P_1$ has root $\beta$, where $\beta \leftarrow \mathbb{Z}_p$ for large prime $p$. We evaluate both polynomials at $\vec{x}=(x_1,...,x_n)$. So we get $\vec{v}=(y_i,...,y_n)$ and $\vec{v}'=(y'_1,...,y'_n)$. We compute $\vec{v}''=\vec{v}\cdot \vec{v}'$. The question is given $\vec{v}''$ and $\vec{x}$ what is the probability that we interpolate a polynomial of degree at most $n−1$ and has root $\beta$? $\endgroup$ – user13676 Aug 27 '15 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.