1
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Are coefficients in $\mathbb F_p$ or in $\mathbb F_{p^n}$? $\endgroup$
    – Cloudscape
    Commented Mar 30, 2017 at 11:30
  • 1
    $\begingroup$ The coeffecients are in $\mathbb{F}_p$ $\endgroup$ Commented Mar 30, 2017 at 11:38
  • 3
    $\begingroup$ How is the field $\Bbb{F}_{p^n}$ given? How large are $p$ and $n$ in the case that interests you? An irreducible polynomial of degree $n$ over $\Bbb{F}_p$ has exactly $n$ roots in $\Bbb{F}_{p^n}$. They form a single orbit under the action of the Galois group (iterates of Frobenius). $\endgroup$ Commented Mar 30, 2017 at 11:39
  • $\begingroup$ I have not worked too much with finite fields, but maybe something like a companion matrix over field elements could work? $\endgroup$ Commented Mar 30, 2017 at 11:39
  • 1
    $\begingroup$ If it has a root, it won't be irreducible in $\mathbb F_{p^n}$. Let $\alpha \in \mathbb F_{p^n}$ be a root of $f$, ie. $f(\alpha) = 0$. We carry out division with remainder, dividing $f$ by the polynomial $(x - \alpha)$: $$ f(x) = (x - \alpha)q(x) + \beta,~~~~~~~ \beta \in \mathbb F_{p^n} $$ Inserting $x = \alpha$ in the above equation proves $\beta = 0$ and $f = (x - \alpha)q$, contradicting irreducibility. On the other hand, if the root is not in $\mathbb F_p$ and the coefficients of $f$ are in $\mathbb F_p$, then $f$ may be irreducible in $\mathbb F_p$. $\endgroup$
    – Cloudscape
    Commented Mar 30, 2017 at 11:39

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .