Intereting Posts

What does the discriminant of an algebraic number field mean intuitively?
Three Circles Meeting at One Point
Is my proof correct? (Conformal equivalence of two circular annuli)
Why is the Kleene star of a null set is an empty string?
Linear vs nonlinear differential equation
Show that $\int_0^\infty \frac{x\log(1+x^2)}{e^{2\pi x}+1}dx=\frac{19}{24} – \frac{23}{24}\log 2 – \frac12\log A$
Find a conformal map from semi-disc onto unit disc
Conditions for which $n | {n \choose k}$ for all $k$
$a^m=b^m$ and $a^n=b^n$ imply $a=b$
Topology of matrices
Find all integer solutions for the equation $|5x^2 – y^2| = 4$
Why can't I use the disk method to compute surface area?
Is $\int_a^b f(x) dx = \int_{f(a)}^{f(b)} f^{-1}(x) dx$?
Trying to understand the slick proof about the dual space
Prove that matrix can be square of matrix with real entries

In a number of papers related to efficient implementation of the AES Sbox, people are computing stuff (the multiplicative inverse for instance) in GF(($2^4$)$^2$) instead of GF($2^8$). In some cases they complicate it further by going down to GF(((($2^2$)$^2$)$^2$)…

My question is how do we find the transformation from one representation to the other and back ?

Examples of such paper freely available on the net:

- irreducibility of $x^{5}-2$ over $\mathbb{F}_{11}$.
- Is it true that every element of $\mathbb{F}_p$ has an $n$-th root in $\mathbb{F}_{p^n}$?
- Proof Check: Number of elements of $\mathbb{F}_{p^{n}}$ of the form $a^{p}-a$ for some $a \in \mathbb{F}_{p^{n}}$.
- Primes as sum of squares in finite field
- Give $3$ examples of a field extensions which are neither normal nor separable.
- Irreducible polynomial which is reducible modulo every prime

The field GF($2^8$) is defined by the irreducible polynomial fixed in the AES standard:

**m($x$) = $x^8$ + $x^4$ + $x^3$ + $x$ + 1**

The irreducible polynomial for the subfield can be chosen freely, for example, for GF(($2^4$)$^2$), a popular choice is

**n($x$) = $x^2$ + {1}$x$ + {e}**

From that they deduce a map function such that $a_h x + a_l = map(a), a_h , a_l$ ∈ GF ($2^4$ ), a ∈ GF ($2^8$ ) and the inverse function $map^-1$, but I have no clue about how they do, and how to verify if the result is right or not.

For **m($x$)** and **n($x$)** given as example, the following equations are the expected result:

$a_A = a_1 ⊕ a_7$

$a_B = a_5 ⊕ a_7$

$a_C = a_4 ⊕ a_6$

$a_l0 = a_C ⊕ a_0 ⊕ a_5$

$a_h0 = a_C ⊕ a_5$

$a_l1 = a_1 ⊕ a_2$

$a_h1 = a_A ⊕ a_C$

$a_l2 = a_A$

$a_h2 = a_B ⊕ a_2 ⊕ a_3$

$a_l3 = a_2 ⊕ a4$

$a_h3 = a_B$

Any pointer on a book which covers this problem is very welcome too^^

- Lack of understanding of the proof of the existence of an irreducible polynomial of any degree $n \geq 2$ in $\mathbb{Z}_p$
- continuous map on $\mathbb{R}$ which is the identity on $\mathbb{Q}$ is the identity map, hence Aut$(\mathbb{R}/\mathbb{Q})= 1.$
- When a holomorphy ring is a PID?
- Show $F(U) = K((x^q -x)^{q-1})$.
- Determine the degree of the splitting field for $f(x)=x^{15}-1$.
- Show that $\mathbb{Q}(\sqrt{2 +\sqrt{2}})$ is a cyclic quartic field i.e. is a galois extension of degree 4 with cyclic galois group
- Proving that a polynomial is not solvable by radicals.
- Probability of a random $n \times n$ matrix over $\mathbb F_2$ being nonsingular
- Examples of Galois connections?
- Galois group and the Quaternion group

I try to describe the passage between $GF(16)$ and $GF(4^2)$. The same principles can be applied in going from $GF(256)$ to $GF(16^2)$ and back.

Let us begin with $GF(4)$. It’s elements are $0,1$, an element called $\alpha$ (aka the generator of the field) and $\alpha+1$. The arithmetic follows from the rule that $\alpha$ is a zero of the polynomial $x^2+x+1$, in other words $\alpha^2=\alpha+1$. In a program we represent the element

$a_1\alpha+a_0$ with the pair of bits $(a_1,a_0)$. So the individual bits are viewed as coefficients of a (at most linear) polynomial that we imagine to be evaluated at $\alpha$.

Similarly elements of $GF(16)$ are represented as sequences of bits $(a_3,a_2,a_1,a_0)$. This sequence represents the element $a_3\beta^3+a_2\beta^2+a_1\beta+a_0$, where $\beta$ is the (possibly, but hopefully not mysterious) generator. This time the arithmetic follows from the fact that $\beta$ is a zero of the polynomial $x^4+x+1$, in other words $\beta^4=\beta+1$. For example,

we then see that

$$

\beta^5=\beta\cdot\beta^4=\beta(\beta+1)=\beta^2+\beta,

$$

and

$$

\beta^{10}=(\beta^5)^2=(\beta^2+\beta)^2=\beta^4+2\beta^2\beta+\beta^2

=\beta^4+\beta^2=\beta^2+\beta+1,

$$

using the fact that in all fields of characteristic two we have $2=1+1=0$. This piece of information is systematically used in a lot of software and hardware in the sense that field addition is implemented as bitwise XOR of the sequences representing the elements of the field.

We make the important observation that $\beta^2+\beta$ is a root of the same equation

$x^2=x+1$ as $\alpha$. This allows us to identify $GF(4)$ as a subset of $GF(16)$. We can choose to equate $\alpha=\beta^2+\beta$.

**Transformation from $GF(16)$ to $GF(4^2)$:** Consider an arbitrary element

$z=a_3\beta^3+a_2\beta^2+a_1\beta+a_0$ of $GF(16)$. We can get rid of the high powers of $\beta$ here using the equation $\beta^2+\beta=\alpha$, or rather the equivalent form

$\beta^2=\beta+\alpha$, and its consequence

$\beta^3=\beta\cdot\beta^2=\beta(\beta+\alpha)=\beta^2+\alpha\beta=\alpha\beta+\beta+\alpha.$ Substituting these allows us to rewrite

$$

\begin{aligned}

z&=a_3(\alpha\beta+\beta+\alpha)+a_2(\beta+\alpha)+a_1\beta+a_0

=(a_3\alpha+[a_3+a_2+a_1])\beta+([a_3+a_2]\alpha+a_0)\\

&=a_h\beta+a_\ell,

\end{aligned}

$$

where $a_h=(a_3\alpha+[a_3+a_2+a_1])$ and $a_\ell=([a_3+a_2]\alpha+a_0)$ are elements of $GF(4)$. Internally we represent elements of $GF(4)$ with the sequence of coefficient of $\alpha^j,j=0,1$, e.g. $a_h=a_{h1}\alpha+a_{h0}$, so here

$$

a_{h1}=a_3,\quad a_{h0}=a_3+a_2+a_1,\quad a_{\ell1}=a_3+a_2,\quad a_{\ell0}=a_0.

$$

**Transformation from $GF(4^2)$ to $GF(16)$:** The other direction is also straightforward with the identification $\alpha=\beta^2+\beta$ in place. If we are given an element of

$GF(4^2)$ in the form

$$

z=a_h\beta+a_\ell,

$$

where $a_h=a_{h1}\alpha+a_{h0}$ and $a_\ell=a_{\ell1}\alpha+a_{\ell0}$, then

$$

\begin{aligned}

z&=(a_{h1}[\beta^2+\beta]+a_{h0})\beta+(a_{\ell1}[\beta^2+\beta]+a_{\ell0})\\

&=a_{h1}\beta^3+(a_{\ell1}+a_{h1})\beta^2+(a_{h0}+a_{\ell1})\beta+a_{\ell0}\\

&=z_3\beta^3+z_2\beta^2+z_1\beta+z_0,

\end{aligned}

$$

where $z_3=z_{h1}$, $z_2=(a_{\ell1}+a_{h1})$, $z_1=(a_{h0}+a_{\ell1})$ and

$z_0=a_{\ell0}$.

**Inversion in $GF(4^2)$:** Here the idea is to take advantage of the fact that inversion is easier in $GF(4)$ than it would be in $GF(16)$. Namely $1^{-1}, \alpha^{-1}=\alpha+1$

and $(\alpha+1)^{-1}=\alpha$. Equivalently $x^{-1}=x^2$ for any non-zero $x\in GF(4)$.

The idea is similar to inverting a complex number $z=x+yi$ where $x,y$ are real, at least one non-zero. There we make the observation that

$$

(x+yi)(x-yi)=x^2+y^2=Q(x,y),

$$

where we can deduce that the **real number** $Q(x,y)\neq0$. As we know how to compute the reciprocal of $Q(x,y)$ we can take advantage and compute

$$

\frac1{x+yi}=\frac1{Q(x,y)}(x-yi).

$$

The key to the success of such calculation is (this is bread and butter in field theory, but does

require a more extensive background in abstract algebra) that $i$ and $-i$

are roots of the same polynomial $x^2+1$ with real coefficients.

We can do something similar here. Remember that $\beta$ is a root

of the polynomial $x^2+x+\alpha$ with coefficients in $GF(4)$. The other root

of that polynomial is $\beta’=\beta+1$, because

$$

\beta’^2+\beta’=(\beta+1)^2+(\beta+1)=\beta^2+1+\beta+1=\beta^2+\beta=\alpha.

$$

So given an element $z=a_h\beta+a_\ell$ of $GF(4^2)$ let’s calculate

$$

z(a_h\beta’+a_\ell)=a_h^2\beta\beta’+a_ha_\ell(\beta+\beta’)+a_\ell^2.

$$

Here $\beta\beta’=\beta(\beta+1)=\beta^2+\beta=\alpha$ and $\beta+\beta’=1$, so we get

$$

z(a_h\beta’+a_\ell)=Q(a_h,a_\ll),

$$

where $Q(x,y)=\alpha x^2+xy+y^2$. Here we can prove that $Q(x,y)\neq0$

if at least one of $x,y$ is non-zero. If $x=0$, then $Q(x,y)=Q(0,y)=y^2\neq0$,

because then $y\neq0$. OTOH, if $x\neq0$, then

$$

Q(x,y)=\frac1{x^2}\left(\alpha+\frac{y}{x}+(\frac{y}{x})^2\right).

$$

Here the factor in round parens is $P(y/x)$, where $P(T)=T^2+T+\alpha$.

We have seen that $P(T)=0$, when $T=\beta$ or $T=\beta’$. Because $P(T)$ is

a quadratic polynomial it can have at most two zeros in the field $GF(16)$.

Because neither of those zeros was in the smaller field $GF(4)$ we can deduce that here

$P(y/x)\neq0$, because $y/x\in GF(4)$.

Putting all this together gives us, at long last,

$$

z^{-1}=\frac{1}{Q(a_h,a_\ell)}(a_h\beta’+a_\ell)

=\frac{1}{Q(a_h,a_\ell)}(a_h\beta+[a_h+a_\ell]).

$$

In other words, using the representation of $GF(16)$ as $GF(4^2)$

allows us to calculate the inverse in $GF(16)$ as a single inversion,

a single addition, and two multiplications in $GF(4)$. I guess that may be

worth the engineers’ while in this setting.

**What is needed to extend this to conversion between $GF(256)$ and $GF(16^2)$:**

AES specifies that the field $GF(256)$ be given by using a generator $\theta$

that is a zero of the polynomial $x^8+x^4+x^3+x+1$ [**EDIT Earlier I had another polynomial here. Corrected.**]. IOW the arithmetic of $GF(256)$ follows

from the rule

$$

\theta^8=\theta^4+\theta^3+\theta+1.

$$

We need to identify a copy of $GF(16)$ inside that field. A little bit of tinkering

allowed me to find that

$$

(\theta^{16}+\theta)=\theta^2+\theta^3+\theta^4+\theta^6

$$

is a solution of $x^4+x+1=0$. So let us declare

$$\beta=\theta^2+\theta^3+\theta^4+\theta^6.$$

Then we can calculate that

$${\bf\{e\}}=(1,1,1,0)_2=\beta^3+\beta^2+\beta=\theta^2+\theta^3+\theta^5+\theta^6+\theta^7.$$

It is possible to prove that

the polynomial $q(x)=x^2+x+{\bf\{e\}}$ has no solutions in $GF(16)$, and hence two in $GF(256)$.

The simplest proof of this relies on the properties of the trace mapping.

A little bit of searching reveals that the roots of $q(x)$ in $GF(256)$ are

$$

\gamma=\theta+\theta^2+\theta^3+\theta^4+\theta^5+\theta^6+\theta^7

$$

and

$$\gamma+1=\gamma^{16}.$$

We can then represent

elements $z\in GF(256)$ in “$GF(16^2)$” format like

$$

z=a_h\gamma+a_\ell,

$$

where this time $a_h,a_\ell\in GF(16)$. The formula

for converting the 8-tuple of bits $(z_0,z_1,\ldots,z_7)$ to

the pair $(a_h,a_\ell)\in GF(16)^2$ such that

$$

z_0+z_1\theta+z_2\theta^2+\cdots+z_7\theta^7=z=a_h\gamma+a_\ell

$$

is quite messy, and I haven’t calculated it.

- Interesting Medieval Mathematics Lecture/Activity Ideas?
- Is bijection mapping connected sets to connected homeomorphism?
- Deciding whether $2^{\sqrt2}$ is irrational/transcendental
- Does an injective endomorphism of a finitely-generated free R-module have nonzero determinant?
- How can this be proved $\lim_{x\to\infty}(f(x)+f'(x))=l$
- Help understand the proof of infinitely many primes of the form $4n+3$
- Markov chain with finite positive recurrent states
- Given $a_{1}=1, \ a_{n+1}=a_{n}+\frac{1}{a_{n}}$, find $\lim \limits_{n\to\infty}\frac{a_{n}}{n}$
- identity of $(I-z^nT^n)^{-1} =\frac{1}{n}$
- Sufficient conditions for being a PID
- Locus of vertex of parabolas through three points
- How to prove this limit composition theorem?
- Intersection of kernels and linear dependence of functionals
- Closure of a number field with respect to roots of a cubic
- What kind of “symmetry” is the symmetric group about?