# how to find generator in $F_2[x]/(f(x))$?

a finite field $F_{2^n}\cong F_2[x]/(f(x))$($f(x)$is irreducible polynomial with the degree of $n$), so the elements in $F_{2^n}$ can be seen a polynomial modular $f(x)$, that is :$$\{g_0(x),g_1(x),...,g_{2^n-1}(x)\}_{f(x)}$$

There is a isomorphism that $\varphi=\left\{ \begin{array}{l l} F_{2^n}\to F_2[x]/(f(x)) \\ \xi \to k(x) & \quad \text{$\xi$is primitive element}\end{array} \right.\$

Because $\xi$ is primitive element in $F_{2^n}$, so $\varphi(\xi)=k(x)$ can also generate all the elements in $F_2[x]/(f(x))$.

My question is that how to find $k(x)$, and what the structure of $k(x)$?

thanks a lot

• I don't think there's a useful, general formula for $k(x)$. People have tabulated values for various ranges of $n$. Sep 12, 2013 at 12:32
• if a primitive polynomial ( degree$=n$ )is found, then it's roots are primitive elements. considering one of these roots $\xi$, $\varphi(\xi)=k(x)$, then a $k(x)$ is found. is this feasible?
– Nax
Sep 12, 2013 at 13:30
• You make it sound like $F_{2^n}$ is given as a kind of a black box. In this answer I describe a method for finding the minimal polynomial $m(x)$ of $\xi$. More often than not you would already know $m(x)$ though. Your question is equivalent to finding a zero of $m(x)$ in $F_2[x]/(f(x))$. That is a bit taxing. Examples have been handled here, but they are either small, or use an ad hoc trick. Sep 13, 2013 at 3:58
• @JyrkiLahtonen can i get a generator in $F_2[x]/(f(x))$ by $m(x)\pmod{f(x)}$?
– Nax
Sep 14, 2013 at 0:44
• Just to make sure: If $m(x)$ is the minimal polynomial of $\xi$, then $F_{2^n}=F_2[\xi]$ is identified with $F_2[x]/(m(x))$, and you are looking for an isomorphiam between $F_2[x]/(m(x))$ and $F_2[x]/(f(x))$. We know that one exists, but it is difficult to find an explicit one. Sep 15, 2013 at 5:30

The answer to this question depends on the representation of $\mathbb F_{2^n}$ you have in mind.

Suppose the elements of $\mathbb F_{2^n}$ just have names e.g. $a_0, a_1, \ldots, a_{2^n-1}$, without any meaning ascribed to them, and you use $2^n\times 2^n$ addition and multiplication tables for arithmetic in $\mathbb F_{2^n}$. You also have a more concrete representation of $\mathbb F_{2^n}$ as $\mathbb F_{2}[x]/(f(x))$, in which representation, addition and multiplication tables are not necessary since arithmetic on the $g_i(x)$'s is done as polynomial addition in $\mathbb F_{2}[x]$ and polynomial multiplication in $\mathbb F_{2}[x]$ followed by a residue computation modulo $f(x)$. In this case, if you know that $a_i \in \mathbb F_{2^n}$ is a zero of $f(x)$, then the desired isomorphism is

$$a_i \leftrightarrow x$$

and the images of all other $a_j$ follow from this. For example, if $a_j = (a_i)^2$ (which we need to use the tables to figure out), then

$$a_j \leftrightarrow x^2$$

and if $a_i+a_j = a_i + (a_i)^2 = a_k$, then $$a_k \leftrightarrow x + x^2$$ and so on and so forth.

But what if you do not know which of the $a_m$ are zeroes of $f(x)$? Well, the brute-force way is simply to try each $a_m$ by evaluating $f(a_m)$ (via the addition and multiplication tables) and checking if the evaluation results in $0$. A slightly more efficient way is to not bother evaluating any of $f(a_m^2)$, $f(a_m^{2^2})$, $\cdots$, $f(a_m^{2^{n-1}})$ if $f(a_m) \neq 0$ because of $a_m$ is not a zero of $f(x)$, then its conjugates cannot be zeroes of $f(x)$ either.