Lecture: 15 - 16

[ Home ][ PDF ]

Topics: Conjugate elements,Automorphism and Traces

Conjugate elements with repect to a subfiled

In theorem 2.14 we saw that if $\alpha \in \mathbb{F_{q^m}}$ is a root of an irreducible polynomail $f$ over $\mathbb{F_q}$ then all the roots of $f$ are representeed by:

$$\alpha , \alpha^q, \alpha^{q^2},...,\alpha^{q^{m-1}}$$

Theorem 2.14:

Irreducible poly in $\mathbb{F_q[x]}$ of degree m has a root in $\mathbb{F_{q^m}}$.

To address elements of a field which are $q$-th powers of each other we introduced the notion of conjugates. (Def 2.17)

Two properties of conjugate elements giveen by 2.18 and Corollary 2.19

Prop: 2.18

The conjugates of $\alpha \in \mathbb{F_q}^$ with respect to any subfield $\mathbb{F_q}$ have the same order in the group $\mathbb{F_q}^$.

Proof:

Since $\mathbb{F_q}^$ is cyclic group by theorem 2.8, the result follows from Theorem 1.15 (ii) and the fact that every power of charateristic of $\mathbb{F_q}$ is relatively prive to the order $q-1$ of $\mathbb{F_q}^ \square$

Corollary 2.19

Result at 2.18 if $\alpha$ is a primitive element of $\mathbb{F_q}$, then so are altso its conjugate with respect to any subfiled of $\mathbb{F_q}$

Exmample

Example of conjugate element in $\mathbb{F_{16}}$ with respect to different subfields.

Let $\alpha \in \mathbb{F_{16}}$ be an root of:

$$f(x) = x^4+x + 1 \in \mathbb{F_2{x}}$$

Then the conjugate of $\alpha$ with respect to $\mathbb{F_2}$ are:

$$\alpha, \alpha^2 , \alpha^4 = \alpha +1 , \alpha^8 = \alpha^2 + 1$$

Each of them being a primitive element of $\mathbb{F_{16}}$

The conjugates of $\alpha$ with respect to $\mathbb{F_4}$ are $\alpha$ and $\alpha^4 = \alpha+1$.

Automorphism for fields over a subfield

With automorphism $\sigma$ of $\mathbb{F_{q^m}} over $\mathbb{F_q}. We meawn automophisme that fixes an element of \mathbb{F_q}.

We then require that:

$\sigma$ be a one-to-one mapping from $\mathbb{F_{q^m}}$ onto itself.

And the following holds:

$$\forall \alpha , \beta \in \mathbb{F_{q^m}}$$ $$\sigma ( \alpha + \beta ) = \sigma(\alpha ) + \sigma(\beta)$$ $$\sigma(\alpha \cdot \beta ) = \sigma(\alpha ) \cdot \sigma(\beta)$$ $$\sigma (a) = a , \forall a \in \mathbb{F_q}$$

Characterisation of all distinct automorphisms of $\mathbb{F_{q^m}}$ over $\mathbb{F_q}$

Definition 2.21

Distinct automiophism of $\mathbb{F_{q^m}}$ over $\mathbb{F_q}$ are exactly the mapping:

$$\sigma_0, \sigma_1, \sigma_2, .. , \sigma_{m-1}$$

defineds by $\sigma_j(\alpha + \beta ) = \sigma_j( \alpha) + \sigma_j(\beta )$ because of theorem 1.46, so that $\sigma_j$ is an endomorphism of $\mathbb{F_{q^m}}$.

Further more $\sigma_j(\alpha ) = 0$ iff $\alpha = 0$ and so $\sigma_j$ is one-to-one. Since $\mathbb{F_{q^m}}$ is a finite set, $\sigma_j$ is and epimorphism and therefor an automorphism of $\mathbb{F_{q^m}}$.

Moreover we have $\sigma_j(a) = a$ for all $a\in \mathbb{F_q}$ by lemma 2.3 and so each $\sigma_j$ is and automophism of $\mathbb{F_{q^m}}$ over $\mathbb{F_q}$.

The mapping $\sigma_0, \sigma_1, \sigma_2, .. , \sigma_{m-1}$ are distinct since they attain disctinct values for primitieve elements of $\mathbb{F_{q^m}}$

Now suppose that $\sigma$ is an arbitraty automorphism of $\mathbb{F_{q^m}}$ over $\mathbb{F_q}.

Let $\beta$ be a primitive element (generator) of $\mathbb{F_{q^m}} and let

$$f(x) = x^m + a_{m-1}\cdot x^{m-1} + ... + a_0 \in \mathbb{F_2[x]}$$

be its minimal polynomial over $\mathbb{F_q}$.

Then we have that:

$$0 = \sigma ( \beta^m + a_{m-1} \cdot \beta^{m-1} + ... + a_0)$$ $$= \sigma ( \beta^m) + a_{m-1} \cdot \sigma ( \beta^{m-1}) + ... + a_0)$$

So that $\sigma(\beta )$ is a root of $f$ in $\mathbb{F_{q^m}}$

It follows from Theorem 2.14 that: $ \sigma(\beta ) = \beta^{q^j}$ for some $j \in [ 0 \leq j \leq m-1]$

Since $\sigma$ is a homomophism, we get that $\sigma (\alpha) = \alpha^{q^j}$ for all $\alpha \in \mathbb{F_{q^m}}$.

On the basis of 2.21, it is evident that conjugates of $\alpha \in \mathbb{F_{q^m}}$ with respect to $\mathbb{F_q}$ are obtainsed by applying all automophisms of $\mathbb{F_{q^m}}$ over $\mathbb{F_q}$ to element $\alpha$.

The automorphism of $\mathbb{F_{q^m}}$ over $\mathbb{F_{q}}$ form a group with the operation being the usual composition of mappings.

The information provided in Theorem 2.21 shows that this gorup of automophisms of $\mathbb{F_{q^m}}$ over $\mathbb{F_{q}}$ is a cyclic group of order $m$ generated by $\sigma_1$

Construction of irreducible ploynomials

An irreducible polynomial over $\mathbb{F_q}$ of degree $n$ remains irreducible over $\mathbb{F_{q^k}}$ iff $k$ and $n$ are relative prime.

Relative prime: Two primes that don’t divide eachother. Coprime: where you have common factors.

$$21 = (1),(3),7,21$$ $$24 = (1),2,(3),4,6,8,12,24$$

They share 1 and 3 as divisors, $21$ and $24$ are then coprime.

Example 1

Polynomial $x^2 + x + 1$ is irreducible over $\mathbb{F_2}$ degree $2$ The it is irreducible over $\mathbb{F_{2^n}}$ is $n$ is a odd number.

Example 2

Polynomial $x^3 + x + 1$ is irreducible over $\mathbb{F_{2}}$ degree 3 Then it is irreducible over $\mathbb{F_{2^n}}$ iff $n$ is not dividible by $3$.

Traces of elements of finite fields

Section 3, p50

In this section we adopt again the viewpoint of regarding $F=\mathbb{F_{q^m}}$ of the finite fields $K=\mathbb{F_{q}}$ as a vectorspace over $K$ (Chapter 1, section 4).

Then $F$ has dimentions $m$ over K, and if {$\alpha_1, …, \alpha_m$} is a basis of $F$ over $K$, each element $\alpha \in F$ can be uniquerly represented in the form:

$$\alpha = c_1 \cdot \alpha_1 + ... + c_m \cdot \alpha_m$$

with $c_j \in K$ for $1 \leq j \leq m$

We introduce an important mapping fraom $F \to K$ which will turn out to be linear.

Let $\alpha \in F$, Then the sum of all conjugates of $\alpha$ with respect to $K$ is called “The trace of $\alpha$ over $K$” and is denoted by:

$$Tr_{F/K} (\alpha )$$

Definition 2.22

For $\alpha \in F = \mathbb{F_{q^m}}$ and $K = \mathbb{F_q}$

The trace of $Tr_{F/K} (\alpha )$ of $\alpha$ over $K$ is defined by:

$$Tr_{F/K} (\alpha ) = \alpha + \alpha^q + ... + \alpha^{q^{m-1}}$$

If $K$ is a prime subfield of $F$ then $Tr_{F/K}(\alpha)$ is called the absoulute trace of $\alpha$ and simply denoted $ Tr_{F} (\alpha ) $

In other words, the trace of $\alpha$ over $K$ is the sum of all the conjugates of $\alpha$ with respect to $K$.

Still another description of the trace may be obtained as follows.

Let $f \in K[x]$ be the minimal polynomial of $\alpha$ over $K$. It’s degree $d$ is a divisor of $m$.

Then $g(x)=f(x)^{m/d} \in K$ is called the charateristic polynomial $\alpha$ over $K$.

By theorem 2.14, the roots of $f$ in $F$ are given by:

$$\alpha, \alpha^q, ..., \alpha^{q^{d-1}}$$

And then a remark following 2.17 implies that the roots of $g$ in $F$ are precisley the conjucages of $\alpha$ with respect to $K$.

Hence:

$$g(x) = x^m + a_{m-1} \cdot x^{m-1} + ... + a_0$$ $$= (x - \alpha ) \cdot ( x - \alpha^q ) \cdot ... \cdot (x - \alpha^{q^{m-1}}$$

And a comparison of coefficients show that:

$$Tr_{F/K}(\alpha) = -a_{m-1}$$

In particular, $Tr_{F/K}(\alpha)$ is always an element of $K$

Theorem 2.23 Holds all 5 properite sof the trace funtion.

Let $K=\mathbb{F_q}$ and $F=\mathbb{F_{q^m}}$ Then the trace function $Tr_{F/K}$ satifies the following properties:

i)

$$Tr_{F/K}(\alpha + \beta) = Tr_{F/K}(\alpha) + Tr_{F/K}(\alpha), \forall \alpha , \beta \in F$$

ii)

$$Tr_{F/K}(c \cdot \alpha) = c \cdot Tr_{F/K}(\alpha), \forall c \in K, \forall \alpha \in F$$

iii)

$Tr_{F/K}(\alpha)$ is linear tranformation from $F$ onto $K$, when both $F$ and $K$ are viewed as vectospaces over $K$.

iv)

$Tr_{F/K}(a) = m \cdot a, \forall a \in K$ $m$ is comming from $\mathbb{F_{q^m}}$

v)

$$Tr_{F/K}(\alpha^q) = Tr_{F/K}(\alpha), \forall \alpha \in \mathbb{F}$$

Where $q$ is from $\mathbb{F_{q^m}}$

Proof (p.51)

Main takeway i) and ii) make iii) $Tr_{F/K}(\alpha)$ into a linear tranformation. It is sufficient to show that $\alpha \in F$ with $Tr_{F/K}(\alpha) \neq 0 $

$Tr_{F/K}(\alpha) = 0$ iff $\alpha$ is a root of the polynomial:

$$x^{q^{m-1}} + ... + x^q + x \in K[x] \in F$$

But since this polynomial casn have at most $q^{m-1}$ roots in $F$ and $F$ has $q^m$ elements. We have are done, $F_{q^{m-1}} \neq F_{q^{m}} \square$

Theorem 2.25

Lef $F$ be a finite extention of $K = \mathbb{F_q}$. Then for $\alpha \in F$ we have: $Tr_{F/K}(\alpha) = 0$ iff $\alpha = \beta^q - \beta$ for some $\beta \in F$.

Proof

Suppose $\alpha \in F = \mathbb{F_q}$ with $Tr_{F/K}(\alpha) = 0$ and let $\beta$ be a root of $x^q - x - \alpha$ in some extension field of $F$. Then $\beta^q - \beta = \alpha$ and:

$$0 = Tr_{F/K}(\alpha)$$ $$RHS = \alpha + \alpha^q + .. + \alpha^{q^{q-1}}$$ $$= ( \beta^q - \beta) + (\beta^q - \beta)^q + ... + (\beta^q - \beta)^{q^{m-1}}$$ $$= ( \beta^q - \beta) + (\beta^{q^2} - \beta^q) + ... + (\beta^{q^m} - \beta^{q^{m-1}})$$ $$= ( \beta^{q^m} - \beta)$$ $$\text{So that } \beta \in F$$ $$\square$$

Theorem 2.26 Transitivity of Trace

Let $K$ be a finite field. Let $F$ be a finite extension of $K$ and $E$ be a finite extendsion of $F$

$ (K \subseteq F \subseteq E)$ , $K$ is the smallest field

$$Tr_{E/K}(\alpha) = Tr_{F/K}(Tr_{E/F}(\alpha)), \forall \alpha \in E$$

Proof is on page 53.

Basis of finite files over their subfields

Chapter 2, 3

If $F = \mathbb{F_{q^m}}$ and $K = \mathbb{F_q}$ then $F$ can be viewed as an $m$ dimentional vector space over $K$.

If $\alpha_1, … , \alpha_m$ is a basis of $F$ over $K$, then each element $\alpha$ in $F$ can be uniquely represented on the form:

$$\alpha = c_1 \cdot \alpha_1, + ... + c_m \cdot \alpha_m$$

with $c_1, … , c_m \in K$

There can be seceral different basis. There are tre particulare basis

• Dual basis
• Polynomial basis
• Normal basis

Definition 2.30 Dual basis

Let $K$ be a finite field and $F$ a finite extendion of $K$.

Then two bases {$\alpha, \alpha_m$ } and { $\beta, \beta_m$ } of $F$ over $K$ are said to be dual (complementary) bases if for $1 \leq i,j \leq m$:

$$Tr_{F/K}(\alpha_i \cdot \beta_j) = \begin{cases} 0 , \text{for } i \neq j\\ 1, \text{for } i = j \end{cases}$$

The dual basis is uniquely determind since its definition implies that the coefficient $c_j{\alpha} , 1\leq j \leq m$ in 2.04 are given by:

$$c_j(\alpha) = Tr_{F/K}(\beta_j \cdot \alpha) , \forall \alpha \in F$$

and by Theorem 2.24 the element $\beta_j \in F$ is uniquely determined by the linear trasformation $c_j$.

Definition 2.32 Normal basis

Let $K= \mathbb{F_q}$ and $F = \mathbb{F_{q^m}}$.

Then a basis of $F$ over $K$ on the form { $\alpha, \alpha^q, … , \alpha^{q^{m-1}}$}.

Consists of a suitable element $\alpha \in F$ and its conjugate with respect to $K$ is called the normal basis of $F$ over $K$.

The basis { $\alpha, \alpha^2, 1+\alpha+\alpha^2$} of $\mathbb{F_8}$ over $\mathbb{F_2}$

Is a normal basis of $\mathbb{F_8}$ over $\mathbb{F_2}$ since $ 1 + \alpha + \alpha^2 = \alpha^4$.

Definition: Polybasis

A basis $F$ over $K$ of the form:

$$1, \alpha, \alpha^2, ... , \alpha^{m-1}$$

with $\alpha$ defining element of $F$ over $K$.

That is $F = K(\alpha)$ is called a polynomial basis.

If $\alpha$ is a primitice element of $F$ then $1, \alpha, \alpha^2, … , \alpha^{m-1}$ os a polynomial basis.

Example 2.31

Let $\alpha \in \mathbb{F_8}$ be a root of the irreducivble polynomial

$$x^3 + x^2 +1 \in \mathbb{F_2[x]}$$

Then $\mathbb{F_8} = \mathbb{F_2(\alpha)}$ and $1, \alpha, \alpha^2 ,\alpha^{3}$ is a polynomial basis

On the other hand $1, \alpha, \alpha^2, 1 + \alpha + \alpha^2$ is a basis dual to itself and it si also a normal basis over $\mathbb{F_2}$

Since $1 + \alpha + \alpha^2 = \alpha^4$,

then $1, \alpha, \alpha^2, 1 + \alpha + \alpha^2$ is a normal basis over $\mathbb{F_2}$