Siguiente: Bibliography Arriba: Algorithms for field arithmetic Anterior: Square root

Trace

If $m\vert n$ then $\mathbb{F}_{2^m}$ is a subfield of $\mathbb{F}_{2^n}$, or $\mathbb{F}_{2^n}$ is an extension of $\mathbb{F}_{2^m}$. In this case, the map

$$T_m^n:\mathbb{F}_{2^n}\to\mathbb{F}_{2^m}\ \,\ x\mapsto \sum_{k=0}^{\frac{n}{m}-1}x^{2^{mk}}$$

is called the trace. $T_m^n$ is a $\mathbb{F}_{2^m}$-linear map. Consequently,

$$A(X)=\sum_{i=0}^{\frac{n}{m}-1}a_iX^i\ ,\ a_i\in\mathbb{F}_m... ...arrow\ T_m^n(A(X)) = \sum_{i=0}^{\frac{n}{m}-1}a_iT_m^n(X^i).$$ (11)

And,

$$T_m^n(X^i) = \left(\sum_{k=0}^{\frac{n}{m}-1}X^{2^{mk}i}\right)\bmod p_{nm}(X),$$ (12)

where $p_{nm}(X)\in\mathbb{F}_m[X]$ is an irreducible polynomial of degree $\frac{n}{m}$. Then by pre-computing the values at (12), the values of the trace can be calculated according to relation (11).