On finite field arithmetic in characteristic $2$

Abstract

We are interested in extending normal bases of ${\mathbf{F}}_{2^n}/{\mathbf{F}}_2$ to bases of ${\mathbf{F}}_{2^{nd}}/{\mathbf{F}}_2$ which allow fast arithmetic in ${\mathbf{F}}_{2^{nd}}$. This question has been recently studied by Thomson and Weir in case $d$ is equal to $2$. We construct efficient extended bases in case $d$ is equal to $3$ and $4$. We also give conditions under which Thomson-Weir construction can be combined with ours.

22 pages