On the Complexity of Parallel Algorithms for Computing Inverses in $GF(2^m)$ with $m$ Prime

摘要

Inversion over a finite field $GF(2^m)$ is usually an expensive operation which is a crucial issue in many applications, such as cryptography and error-control codes. In this paper, three different strategies for computing the inverse over binary finite fields $GF(2^m)$ , called Eulerian, Gaussian, and Euclidean, respectively, are discussed and compared in terms of time and space complexity. In particular, some new upper and lower bounds to the respective complexities are evaluated.