A Euclidean Algorithm for Normal Bases

Inversion in finite fields \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$GF(2^k)$\end{document} is a critical operation for many applications. A well-known representation basis, i.e., normal basis, provides an efficient squaring operation realized as a simple rotation of the operand coefficients. Inversion in normal basis is computed using methods derived from Fermat’s Little theorem, e.g., the Itoh–Tsujii algorithm or with the aid of basis conversion algorithms using the Extended Euclidean algorithm. In this paper we present alternative normal basis inversion algorithm derived from the polynomial version of the extended Euclidean algorithm. The normal basis Euclidean algorithm has (roughly) the same complexity as the polynomial version of the Euclidean algorithm. The proposed algorithm requires on average a linear number of multiplications. We also present a modification to our algorithm which delays the multiplications to the very end of the computation and thereby gives opportunity for recursive computation using only a logarithmic number of multiplications.