Itoh-Tsujii inversion in standard basis and its application in cryptography and codes
This contribution is concerned with a generalization of Itoh and Tsujii's algorithm for inversion in extension fields GF(q(m)). Unlike the original algorithm, the method introduced here 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 we show that the Frobenius map can be explored 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 standard basis as for normal basis representation for the field classes considered.
inversion cryptography codes galois fields polynomial basis aop esp