Given a irreducible polynomial $f$ of degree $n$ over a finite field $\mathbb{F}_{p}$. How do I find any root $\alpha \in \mathbb{F}_{p^n}$ of $f$?
Is there a better way than trying out every element of $\mathbb{F}_{p^n}$?
[Math] roots of polynomial over finite field
finite-fieldsirreducible-polynomialsroots
Best Answer
There are several methods to find roots of (irreducible) polynomials over finite fields, which are better than just testing every element. For example, the article Finding roots of polynomials over finite fields explains the fast polynomial evaluation algorithm, with some examples of primitive polynomials over $GF(2)$.