roots of polynomial over finite field

Question

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}$?

Answer 1

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)$.