Let polynomial $P$ be $P(x)=g(x).(x−β)$, where $g$ is a polynomial and $\beta \leftarrow \mathbb{F}_p$. We evaluate $P$ at some $\textbf{x}=(x_1,..,x_n)$. This gives us $\textbf{y}=(y_1,..,y_n)$. Assume some of $y_i$'s are accidentally changed to some random values $y′_i$'s. Now we interpolate $(x_1,y_1),...,(x_i,y′_i),..(x_j,y′_j),...(x_n,y_n)$, to get a polynomial $P′$.
My question: What is the probability that $P′$ has the root β?
Definitions: $y_i$ is defined as $P(x_i)=y_i$, $x_i \neq0$ , $x_i\neq x_j$, the polynomials, $x_i$'s and $y_i$'s are defined over finite field $\mathbb{F}_p$ for a large prime $p$.
Answer
The probability is $\frac{1}{p}$.
One way to see this is to imagine that instead of $(x_n,y_n')$ you take $(\beta,0)$ as an interpolation point. Then you get a unique polynomial $\tilde{P}$ of degree at most $n-1$ satisfying $\tilde{P}(x_i)=y_i'$ for $i Note : I treated the problem like all $y_i$ had been changed to values $y_i'$, which are possibly equal to $y_i$.
No comments:
Post a Comment