# Interpolating a Polynomial with a Subset of Interpolation Points

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

• 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$? – Chester Aug 26 '15 at 13:32
• @Chester Yes is the answer for both of your questions. – user13676 Aug 26 '15 at 13:33
• 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? – Chester Aug 26 '15 at 14:25
• @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. – user13676 Aug 26 '15 at 14:30
• 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. – 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.
• 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$? – user13676 Aug 27 '15 at 8:51