# Probability that a random polynomial over a finite field can be factorized to linear terms.

Suppose that $f\in\mathbb{F}_p[x]$ is a degree $d$ random univariate polynomial with coefficients from a finite field $\mathbb{F}_p$. What is the probability that $f$ can be written as: $$f(x)=\prod_{j=1}^d(x-\alpha_j),$$ for $\alpha_j\in\mathbb{F}_p$?

My heuristic guess: we have got $p^d$ different polynomials. I have also got $p$ options to choose $\alpha_1$, $p-1$ options for $\alpha_2$,..., and $p-d+1$ options for $\alpha_d$. Considering all possible rotations of $\alpha_j$, the probability is equal to: $\frac{p(p-1)\cdots(p-d+1)}{p^dd!}$. However it seems that I am missing roots with multiplicity larger than $1$. Any idea?

• Stars and Bars lets you compute the number of combinations with repetition.
– lulu
May 26, 2016 at 11:57

As lulu indicated in a comment, you need to count the number of combinations of roots with repetition. You have $d$ roots to distribute over $p$ bins; the number of ways to do this is $\binom{d+p-1}d$, so the probability is
$$\frac{\binom{d+p-1}d}{p^d}\;.$$
For $d\ll p$ this is roughly $\frac1{d!}\frac1p$, so about a fraction $\frac1{d!}$ of all monic polynomials can be fully factored.