Itoh-Tsujii inversion in standard basis and its application in cryptography and codes (Q1598873)

The article is concerned with a generalization of Itoh and Tsujii's algorithm [\textit{T. Itoh} and \textit{S. Tsujii}, Inf. Comput. 78, 171--177 (1988; Zbl 0672.68015)], for inversion in extension fields \(\text{GF}(q^m)\). Unlike the original algorithm, the method introduced by the authors uses a standard (or polynomial) basis representation. The inversion method is generalized for standard basis representation, and relevant complexity expressions are established, consisting of the number of extension field multiplications and exponentiations. As the main contribution, for three important classes of fields the authors show that the Frobenius map can be exploited to perform the exponentiations required for the inversion algorithm efficiently. As an important consequence, Itoh and Tsujii's inversion method shows almost the same practical complexity for the standard basis as for the normal basis representation for the field classes considered.