Polynomial Interpolation

Aydin.A

New member
Joined
Aug 30, 2015
Messages
1
Let us define polynomial $T=(x-\beta)\cdot g(x)$ over finite field $\mathbb{Z}_p$. Degree of $T$ is at most $n-1$, $\beta$ is chosen uniformly at random from the field of $p$ elements. We evaluate $T$ at some $x_i$ values. So we get $(x_1, y_1\cdot r_1),...,(x_n, y_n\cdot r_n)$, where $P(x_i)=y_i \cdot r_i$


Let $r_i \in \vec{v}=[r_1,..., r_n]$. We shuffle the elements in the vector $\vec{v}$. So an element in $i^{th}$ position is moved to a uniformly random $s^{th}_i$ position: $r_i \rightarrow r_{s_i}$


Given $(x_1,y_1\cdot r_{s_1}),...,(x_n,y_n\cdot r_{s_n})$ we interpolate polynomial $T'$.


**Question**: What is the probability that $T'$ has root $\beta$ ?




Assumption: $x_i \neq x_j$,$y_i\neq 0 ,r_i \neq 0$, $x_i,y_i,r_i \in \mathbb{Z}_p$. Not all $r_i$'s can be 1.
 
Top