0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $P'$ is the polynomial interpolating the $n$ points in $S$, so it certainly has degree $n-1$ at most. But I don't understand how you choose $\beta$. If it's picked randomly among the elements in your field $\mathbb{F}_p$ there is no reason that it should be a root of $P$... $\endgroup$ – Arnaud D. Aug 22 '15 at 13:45
  • $\begingroup$ @Arnaud We first define $P$ where $P=g.(x-\beta)$, where $g$ is a polynomial. Then 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 is what is the probability that $P'$ has the root $\beta$. $\endgroup$ – user13676 Aug 22 '15 at 13:53
  • $\begingroup$ I'm editing the question. $\endgroup$ – user13676 Aug 22 '15 at 14:00
  • $\begingroup$ Ah I understand better now. Can we assume that we know exactly how many $y_i$'s are changed? Or do we only know that there has been some change, but without any detail? $\endgroup$ – Arnaud D. Aug 22 '15 at 14:02
  • $\begingroup$ @Arnaud In fact I want it for data integrity check, so we do not know anything about the changes. That is why we insert $\beta$ to let us detect such a change, so we know $\beta$. But I need to know how sure I can be with this check. $\endgroup$ – user13676 Aug 22 '15 at 14:07
3
$\begingroup$

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<n$ and $\tilde{P}(\beta)=0$. Let $\tilde{y_n}=\tilde{P}(x_n)$. You know that $P'$ has degree at most $n-1$ and satisfies $P'(x_i)=y_i'$ for all $i$, thus in particular for $i<n$. It follows from the uniqueness of interpolation polynomials that $P'(\beta)=0$ iff $P'=\tilde{P}$ iff $\tilde{y}_n=\tilde{P}(x_n)=y_n'$, and since $y_n'$ is taken uniformly randomly in $\mathbb{F}_p$, the probability that $y_n'=\tilde{y}_n$ is $\frac{1}{p}$.

Note : I treated the problem like all $y_i$ had been changed to values $y_i'$, which are possibly equal to $y_i$.

$\endgroup$
  • $\begingroup$ What if some of $y_i$'s are changed (e.g. two or three of them)? Am I right that the other unchanged $y_i$'s may increase the chance that $\beta$ appear in the interpolating polynomial's root? $\endgroup$ – user13676 Aug 22 '15 at 15:11
  • $\begingroup$ Actually the number of values changed doesn't influence the result in my answer. $\endgroup$ – Arnaud D. Aug 22 '15 at 15:11
  • $\begingroup$ @Arnaud Before the clarification that $\deg P = n-1$, it wasn't necessarily true that $\tilde{P}(\beta) = 0$ (for instance, if $\deg P > n$, then just knowing that $P(\beta)=0$ does not imply much about $\tilde{P}(\beta)$ :). $\endgroup$ – Erick Wong Aug 22 '15 at 15:38
  • 1
    $\begingroup$ Yes, that's right. (Also I corrected the typo you mentioned. I hope there is no other one.) $\endgroup$ – Arnaud D. Aug 22 '15 at 16:10
  • 1
    $\begingroup$ I will mention that this is kind of trivial in this case (though matches the question); if all of the $y_{i}$ are allowed to change/not change, you are replacing your polynomial $P(x)$ with some random polynomial $P^{\prime}(x)$ of degree at most $n-1$. Because this polynomial is random, the value $P^{\prime}(\beta)$ is also a random element of $\mathbb{F}_{p}$, so probability $P^{\prime}(\beta)=0$ is $1/p$. $\endgroup$ – Morgan Rodgers Aug 23 '15 at 7:22

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.