0
$\begingroup$

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


In the literature, especially in cryptography, a random polynomial defined as a polynomial whose coefficients are distributed uniformly at random over a field, e.g. $\mathbb{F}_p$. A simple way of constructing a random polynomial of degree $d$ is to pick $d+1$ random values from the field and build a polynomial.

Question: Is $ f=\prod^{d}_{i=1}(x-r_i)$ a random polynomial, where $r_i$'s are picked uniformly random fron the field?

$\endgroup$
1
$\begingroup$

No, because some polynomials cannot arise at all by this procedure.

For example only about half of the polynomials of the form $x^2+c$ are products of linear factors.

And of course by multiplying together $x-r_i$ factors you can only ever get monic polynomials.

In general, observe that both the set of ordered sequences of $d$ roots and the set of monic polynomials of degree $d$ have the same cardinality, but the mapping from roots to polynomials is not injective since the ordering of the root doesn't matter. So some of the polynomials must be missed by the mapping when $d>1$.

$\endgroup$
  • $\begingroup$ Are you saying that within the space of polynomials generated by the described method, a given polynomial will not be “random” even if the roots are chosen at random? $\endgroup$ – abiessu Sep 8 '18 at 19:28
  • 1
    $\begingroup$ @abiessu: That too, because a given polynomial with multiple roots will be produced less often than a given polynomial whose roots are all different wil be. $\endgroup$ – hmakholm left over Monica Sep 8 '18 at 19:29

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.