Imagine we have $\vec{x}=(x_1,...x_n)$ and two polynomials $P_1$ and $P_2$. Degree of $P_1$ is fixed $n-1$, but degree of $P_2$ can be at most $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_1,...,y_n)$ and $\vec{v}'=(y'_1,...,y'_n)$. We compute $\vec{v}''=\vec{v}\cdot \vec{v}′$.

Question: 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$?

Definition: We define all values and polynomials over a field $\mathbb{Z}_p$ for large prime $p$, $x_i\neq x_j$, $x_i$'s are not the roots of polynomials $P$ and $P'$.

  • $\begingroup$ What is the probability space in this context? $\endgroup$ – drhab Aug 27 '15 at 17:39
  • $\begingroup$ @drhab It is $\mathbb{Z}_p$. Correct me if I am wrong. $\endgroup$ – user13676 Aug 27 '15 at 17:41

Your Answer

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

Browse other questions tagged or ask your own question.