3
$\begingroup$

My question is related to this question.

All operations and polynomials are defined over a finite field of prime order: $\mathbb{F}_p$, where $p$ is a large prime number.


There are two parties involved in this question: A and B. Party A picks two arbitrary non-zero elements of the field: $(\alpha, \beta)$. Party B picks a uniformly random polynomial $P(x)$ of degree $d$.

Question: What is the probability that $P(\alpha)=\beta$?

would it be correct to say that the probability is at most $\frac{1}{p}$?

$\endgroup$
1
$\begingroup$

I assume a uniformly random polynomial of degree $d$ has every coefficient uniformly chosen from $\{0, 1, \dots, p-1\}$, except the highest degree coefficient is chosen from $\{1, 2, \dots, p-1\}$, i.e. it cannot be $0$.

Write $P(x) = Q(x) + c$ where $c$ is the constant term randomly chosen, i.e. $Q(x)$ has no constant term. Then $P(\alpha) = \beta$ iff $c = \beta - Q(\alpha)$. Therefore:

$$Prob(P(\alpha) = \beta) = Prob(c = \beta - Q(\alpha)) = 1/p$$

because for any choice of $\alpha, \beta$ and coefficients of $Q$, there is exactly $1/p$ chance that a uniformly-chosen $c$ will be just the value you need.

$\endgroup$
  • $\begingroup$ thanks for the clear answer-- two questions: (1) what if we relax the assumption that the highest degree cannot be $0$ (2) what if we assume the polynomial degree is in the range $[1,d]$-- Am I right that we will still have the same probability as your answer is independent of the polynomial degree and the degree can be 1? Thanks! $\endgroup$ – Ay. Sep 26 '19 at 8:55
  • $\begingroup$ yeah, as long as the constant term is picked uniformly, the prob is $1/p$. it doesnt matter how $\alpha, \beta$ and coefficients in $Q$ are picked. they can be uniform, uniform with exception (for $0$), non-uniform, hand-picked by an adversary, etc. none of that matters as long as the constant term is uniform. $\endgroup$ – antkam Sep 26 '19 at 11:12
1
$\begingroup$

Let $p$ be a large prime and let $P\in F_p[x]$ be a random polynomial. Then its values $(P(i))_{i\in[[0,p-1]]}$ are independent and uniformly random in $[[0,p-1]]$. Here, we assume that $\alpha,\beta$ may be $0$.

Then, if we fix random $\beta$ and $P$, then the number $k$ of solutions of $P(x)=\beta$ is, in general, in $[[0,4]]$ (according to the normal law which is an approximation of the Bernouilli law). Thus $prob(P(\alpha)=\beta)\approx k/p$.

Now, if our random $P$ varies, then the mean of the number of solutions of $P(x)=\beta$ is $\approx 1$; finally, the required probability that $P(\alpha)=\beta$ is $\approx 1/p$.

EDIT. antkam is right. If we fix the degree $d$ of the polynomials, then, for every $\beta$, the mean of the number of solutions of $P(x)=\beta$ is exactly $1$. Thus the required probability is exactly $1/p$.

$\endgroup$
  • $\begingroup$ Why $\approx 1/p$? Shouldn't it be exactly $1/p$? Is there something wrong with my answer? $\endgroup$ – antkam Sep 25 '19 at 23:33
  • $\begingroup$ @antkam, cf. my edit. $\endgroup$ – loup blanc Sep 26 '19 at 8:19
  • $\begingroup$ thanks for the answer-- can you clarify what $k$ refers to and where 4 comes from. $\endgroup$ – Ay. Sep 26 '19 at 8:53
  • $\begingroup$ I dont think we need to fix the degree. Unless there's something wrong with my answer, the only thing that matters is that the constant term is uniformly random. The rest of the coefficients can be non-uniform or even hand-picked by an adversary. $\endgroup$ – antkam Sep 26 '19 at 11:14

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.