3. as example

In $\mathbb {Z}\left/ 2\right. \left[ X\right]$ , the characteristic polynomial of $\mathrm{GF}\! \left( 16 \right)$ splits as $X^{16}-X=\left( X^{4}-X\right) P_{\xi }\, P_{\alpha }\, P_{\beta }$ where $P_{\xi }\left ( X\right ) =X^{4}+X+1$ , $P_{\alpha }\left( X\right) =X^{4}+X^{3}+1$ et $P_{\beta }\left( X\right) =X^{4}+X^{3}+X^{2}+X+1$ . The factor $X^{4}-X$ occurs since $\mathrm{GF}\! \left( 4 \right)$ is embedded into $\mathrm{GF}\! \left( 16 \right)$ , and the three others factors are defining $\psi$ -classes of proper elements of $\mathrm{GF}\! \left( 16 \right)$ . It can be checked that $\Phi _{5}=P_{\beta }$ and $\Phi _{15}=P_{\xi }\, P_{\alpha }$ .

In what follows, it assumed that one among the four root of the polynomial $P_{\xi }$ has been elected as ``the true $\xi$ ''. The other three roots of $P_{\xi }$ are therefore the successive images of $\xi$ by $\psi$ , i.e. $\xi ^{2},\, \xi ^{4},\, \xi ^{8}$ and $P_{\xi }$ splits as $P_{\xi }\left( X\right) =\left( X-\xi \right) \left( X-\xi ^{2}\right) \left( X-\xi ^{4}\right) \left( X-\xi ^{8}\right)$ .

For any $s$ in $\left[ 0\dots 14\right]$ , we define $R_{s}\left( X\right) \in \mathbb {Z}\! \left/ p\right. \left[ X\right]$ as $X^{s}\,{\rm mod}\,P_{\xi }\left( X\right)$ . Therefore, we have $\xi ^{s}=R_{s}\left( \xi \right)$ , expressing $\xi ^{s}$ as a linear combination of the $1,\, \xi ,\, \xi ^{2},\, \xi ^{3}$ . In Table 1, the first two columns give the correspondence $\xi ^{s}\mapsto R_{s}\left( \xi \right)$ , enlarged by the convention that $\xi ^{\infty }=0$ and $R_{\infty }=0$ . For an easier identification of the $R_{s}\left( \xi \right)$ , the third column gives the $R_{s}\left( 2\right)$ computed inside $\mathbb {N}$ (e.g. $X^{3}+X+1$ is mapped to $8+2+1=11$ ).

Table: Describing elements of $\mathrm{GF}\! \left( 16 \right)$ as polynomials in $\xi$ , $\alpha$ or $\beta$ .

$\xi ^{s}$	$R_{s}\left( \xi \right)$	$R_{s}\left( 2\right)$	$\alpha ^{t}$	$R_{t}$ $\left( \alpha \right)$	$R_{t}\left( 2\right)$	$\beta ^{u}$	$R_{u}\left( \beta \right)$	$R_{u}\left( 2\right)$
$\xi ^{\infty }$	$0$	$0$	$\alpha ^{\infty }$	$0$	$0$		$0$	$0$
$\xi ^{0}$	$1$	$1$	$\alpha ^{0}$	$1$	$1$	$1$	$1$	$1$
$\xi ^{1}$	$\xi$	$2$	$\alpha ^{13}$	$\alpha ^{2}+\alpha$	$6$		$\beta ^{2}+\beta$	$6$
$\xi ^{2}$	$\xi ^{2}$	$4$	$\alpha ^{11}$	$\alpha ^{3}+\alpha ^{2}+1$	$13$		$\beta ^{3}+\beta +1$	$11$
$\xi ^{3}$	$\xi ^{3}$	$8$	$\alpha ^{9}$	$\alpha ^{2}+1$	$5$	$\beta ^{2}$	$\beta ^{2}$	$4$
$\xi ^{4}$	$\xi +1$	$3$	$\alpha ^{7}$	$\alpha ^{2}+\alpha +1$	$7$		$\beta ^{2}+\beta +1$	$7$
$\xi ^{5}$	$\xi ^{2}+\xi$	$6$	$\alpha ^{5}$	$\alpha ^{3}+\alpha +1$	$11$		$\beta ^{3}+\beta ^{2}+1$	$13$
$\xi ^{6}$	$\xi ^{3}+\xi ^{2}$	$12$	$\alpha ^{3}$	$\alpha ^{3}$	$8$	$\beta ^{4}$	$\beta ^{3}+\beta ^{2}+\beta +1$	$15$
$\xi ^{7}$	$\xi ^{3}+\xi +1$	$11$	$\alpha$	$\alpha$	$2$		$\beta +1$	$3$
$\xi ^{8}$	$\xi ^{2}+1$	$5$	$\alpha ^{14}$	$\alpha ^{3}+\alpha ^{2}$	$12$		$\beta ^{3}+\beta$	$10$
$\xi ^{9}$	$\xi ^{3}+\xi$	$10$	$\alpha ^{12}$	$\alpha +1$	$3$	$\beta$	$\beta$	$2$
$\xi ^{10}$	$\xi ^{2}+\xi +1$	$7$	$\alpha ^{10}$	$\alpha ^{3}+\alpha$	$10$		$\beta ^{3}+\beta ^{2}$	$12$
$\xi ^{11}$	$\xi ^{3}+\xi ^{2}+\xi$	$14$	$\alpha ^{8}$	$\alpha ^{3}+\alpha ^{2}+\alpha$	$14$		$\beta ^{3}+1$	$9$
$\xi ^{12}$	$\xi ^{3}+\xi ^{2}+\xi +1$	$15$	$\alpha ^{6}$	$\alpha ^{3}+\alpha ^{2}+\alpha +1$	$15$	$\beta ^{3}$	$\beta ^{3}$	$8$
$\xi ^{13}$	$\xi ^{3}+\xi ^{2}+1$	$13$	$\alpha ^{4}$	$\alpha ^{3}+1$	$9$		$\beta ^{3}+\beta ^{2}+\beta$	$14$
$\xi ^{14}$	$\xi ^{3}+1$	$9$	$\alpha ^{2}$	$\alpha ^{2}$	$4$		$\beta ^{2}+1$	$5$

The key point to observe in Table 1 is that all polynomials inside $\left( \mathbb {Z}\! \left/ p\right. \right) _{3}\left[ \xi \right]$ are obtained, proving that $\xi$ is a primitive root of $\mathrm{GF}\! \left( 16 \right) ^{*}$ . All these primitive roots are the $\varphi$ $\left( 15\right) =8$ elements $\xi ^{k}$ where $\left( k,\, 15\right) =1$ . Four of them are $\xi ,\, \xi ^{2},\, \xi ^{4},\, \xi ^{8}$ i.e. the roots of $P_{\xi }$ , and the remaining four : $\xi ^{7},\, \xi ^{14},\, \xi ^{28}=\xi ^{13},\, \xi ^{26}=\xi ^{11}$ are the roots of $P_{\alpha }$ (the other factor of $\Phi _{15}$ ). Defining $\alpha$ as $\xi ^{7}$ , we have $\xi =\alpha ^{13}$ since $7\times 13\equiv 1\,{\rm mod}\,15$ and therefore $\xi ^{s}=\alpha ^{t}$ where $t\equiv 13s\,{\rm mod}\,15$ . Computation of the $R_{t}\left( \alpha \right) \doteq \alpha ^{t}\,{\rm mod}\,P_{\alpha }$ leads to the second part of 1.

It can be seen that $\beta \doteq \xi ^{9}$ is a root of $P_{\beta }$ , the other being $\beta ^{2}=\xi ^{3}$ , $\beta ^{4}=\xi ^{6}$ and $\beta ^{3}=\beta ^{8}=\xi ^{12}$ . Here again, $\mathrm{GF}\! \left( 16 \right)$ can be described by polynomials in $\beta$ (which is a proper element of $\mathrm{GF}\! \left( 16 \right)$ ), but not by powers of $\beta$ (which is not a primitive root). We obtain the third part of Table 1.

3.2 Zech's logarithms in $\mathrm{GF}\! \left( 16 \right)$

Table 2 explains the Imamura's algorithm to compute the Zech logarithm relative to a given primitive polynomial. While tabulating the correspondence $s\mapsto R_{s}\left( 2\right)$ , the reverse correspondence $R_{s}\left( 2\right) \mapsto s$ can be tabulated on the fly (the first part of Table 2). Thereafter, adding $1$ to $\xi ^{s}$ is adding $1$ to $R_{s}\left( \xi \right)$ and therefore going forwards to the next $R_{s}\left( 2\right)$ , or going $p-1$ places backwards in the $R_{s}\left( 2\right)$ list [7]. If we take $s=12$ , we obtain $\xi ^{12}=\xi ^{3}+\xi ^{2}+\xi +1$ , i.e. $R_{s}\left( 2\right) =15$ . Therefore $\xi ^{Z\left( 12\right) }\doteq \xi ^{12}+1=\xi ^{3}+\xi ^{2}+\xi$ , i.e. $R_{z\left( s\right) }\left( 2\right) =14$ and $Z_{\xi }\left( s\right) =11$ .

It is obvious that all the Zech functions relative to $\psi$ -conjugates of a given $\xi$ are identical : the Zech function depends only from the chosen primitive polynomial, and not of a particular root of that polynomial. Therefore, we have two Zech's logarithms that are defined over $\mathrm{GF}\! \left( 16 \right)$ : the $s\mapsto Z_{\xi }\left( s\right)$ already tabulated and the $t\mapsto Z_{\alpha }\left( t\right)$ obtained using $P_{\alpha }$ (tabulated in last column of Table 2).

Table 2: The Imamura's algorithm using $P_{\xi }\left ( X\right ) =X^{4}+X+1$ .

$R_{s}\left( 2\right)$	$s$	$s$	$R_{s}\left( 2\right)$	$R_{s}\left( 2\right) \pm 1$	$Z_{\xi }\left( s\right)$	$s+Z_{\xi }\left( s\right)$	$Z_{\alpha }\left( t\right)$
$0$	$\infty$	$\infty$	$0$	$1$	$0$	$\infty$	$0$
$1$	$0$	$0$	$1$	$0$	$\infty$	$\infty$	$\infty$
$2$	$1$	$1$	$2$	$3$	$4$	$5$	$12$
$3$	$4$	$2$	$4$	$5$	$8$	$10$	$9$
$4$	$2$	$3$	$8$	$9$	$14$	$2$	$4$
$5$	$8$	$4$	$3$	$2$	$1$	$5$	$3$
$6$	$5$	$5$	$6$	$7$	$10$	$0$	$10$
$7$	$10$	$6$	$12$	$13$	$13$	$4$	$8$
$8$	$3$	$7$	$11$	$10$	$9$	$1$	$13$
$9$	$14$	$8$	$5$	$4$	$2$	$10$	$6$
$10$	$9$	$9$	$10$	$11$	$7$	$1$	$2$
$11$	$7$	$10$	$7$	$6$	$5$	$0$	$5$
$12$	$6$	$11$	$14$	$15$	$12$	$8$	$14$
$13$	$13$	$12$	$15$	$14$	$11$	$8$	$1$
$14$	$11$	$13$	$13$	$12$	$6$	$4$	$7$
$15$	$12$	$14$	$9$	$8$	$3$	$2$	$11$

Putting $\alpha =\xi ^{k}$ (where $\gcd \left( k,\, q-1\right) =1$ ), we have $\xi ^{k\, Z_{\alpha }\left( t\right) }=\alpha ^{Z_{\alpha }\left( t\right) }=\alpha ^{t}+1=\xi ^{k\, t}+1$ leading to the translation formula

3.3 Using the Zech table to solve quadratic equations

The usual way to solve the equation $a\, x^{2}+b\, x+c=0$ is not relevant in the $\mathrm{GF}\! \left( 2^{m} \right)$ fields. Discarding the obvious cases where $a\, b=0$ , we put $z\doteq a\, x/b$ and obtain $z^{2}+z+a\, c/b^{2}=0$ . Therefore, if $z=\zeta$ is a root of that equation, the other is $z=\zeta +1$ , leading to $a\, c/b^{2}=\zeta \left( \zeta +1\right)$ . Taking the (discrete) logarithm we get $L_{\xi }\left( a\, c/b^{2}\right) =L_{\xi }\left( \zeta \right) +Z_{\xi }\left( L_{\xi }\left( \zeta \right) \right)$ , and the problem is restated as finding $s\in \mathbb {N}_{q}$ such that $s+Z_{\xi }\left( s\right)$ has the prescribed value.

Taking $x^{2}+\xi ^{2}x+\xi ^{10}$ as example, we get $z^{2}+z+\xi ^{4}=0$ . From Table 2, $\zeta _{1}=\xi ^{6}$ and = $\zeta _{2}=\xi ^{13}$ are obtained, leading to the requested roots : $x_{1}=\xi ^{9}$ and $x_{2}=\xi$ .

3. $\mathrm{GF}\! \left( 16 \right)$ as example

3.1 Vector space structure of $\mathrm{GF}\! \left( 16 \right)$

3.2 Zech's logarithms in $\mathrm{GF}\! \left( 16 \right)$

3.3 Using the Zech table to solve quadratic equations