Roots of random polynomials.

991 Views Asked by At

Assume $P(x)$ is a random polynomial of degree $d$, where its coefficients are picked uniformly at random from $\mathbb{F}_p$, and $p$ is a large prime number. So the polynomial is defined over $\mathbb{F}_p$.

Question 1: What is the probability that polynomial $P(x)$ has at least one root?

Question 2: Are roots of $P(x)$ random values in $\mathbb{F}_p$?

1

There are 1 best solutions below

6
On

Given $x \in \mathbb F_p$, the probability that a random polynomial of degree $d$ has $x$ as a root is $1/p$. Thus the expected number of roots of a random polynomial is $1$. Unfortunately these events are not independent, but we may speculate that for large $d$ and $p$ the number of roots is not too badly approximated by a Poisson distribution, which would say the probability of no roots is approximately $1/e$.