Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
I don't think there's a useful, general formula for $k(x)$. People have tabulated values for various ranges of $n$. –  Gerry Myerson Sep 12 '13 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 '13 at 13:30
1  
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. –  Jyrki Lahtonen Sep 13 '13 at 3:58
    
@JyrkiLahtonen can i get a generator in $F_2[x]/(f(x))$ by $m(x)\pmod{f(x)}$? –  Nax Sep 14 '13 at 0:44
1  
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. –  Jyrki Lahtonen Sep 15 '13 at 5:30

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.