We define polynomial $P=(x-\beta)\cdot g(x)$, where degree of $P$ is fixed $n-1$, $\beta$ is chosen uniformly at random from the field of $p$ elements. We evaluate $P$ at some $x_i$ values. So we get $(x_1, y_1),...,(x_n, y_n)$, where $P(x_i)=y_i$.

Then we compute $(x_1,y_1\cdot r_1),..., (x_n,y_n\cdot r_n)$, for arbitrary values of $r_i$. Here a subset (but not all) of $r_i$'s can be 1. Given $(x_1,y_1\cdot r_1),..., (x_n,y_n\cdot r_n)$ we interpolate a polynomial $T$ of degree at most $n-1$.

My Question: Is it possible that $T$ has root $\beta$ too?

hypothesis: $x_i\neq x_j$,$y_i \neq 0, r_i\neq 0$. For those $r_i$'s that are not 1, $r_i \neq r_j$. Also $p$ is a large prime number (e.g. 256-bit). edit:The polynomials are defined over $\mathbb{Z}_p$. $x_i, r_i \in \mathbb{Z}_p$

  • $\begingroup$ It is possible. Does an example suffice to satisfy your inquisitiveness? $\endgroup$ – hardmath Aug 29 '15 at 14:58
  • $\begingroup$ @hardmath I need to have a short chat with you if you don't mind $\endgroup$ – user13676 Aug 30 '15 at 11:12
  • $\begingroup$ The chatroom is ready for discussion. There are roundabout ways (user scripts) to support MathJax/LaTeX, but chat does not natively do so. However I think I'll be able to interpret "raw" MathJax strings. $\endgroup$ – hardmath Aug 30 '15 at 14:18
  • $\begingroup$ @hardmath How can I write there? $\endgroup$ – user13676 Aug 30 '15 at 14:21

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.