Itoh-Tsujii Inversion in Standard Basis and Its Application in Cryptography and Codes

Jorge Guajardo Merchan, Chris­tof Paar

Designs, Codes and Cryptography, 25, pp. 207-216, 2002.


This contribution is concerned with a generalization of Itoh and Tsujii's algorithm for inversion in extension elds 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 eld multiplications and exponentiations. As the main contribution, for three important classes of elds we show that the Frobenius map can be explored to perform the exponentiations required for the inversion algorithm eciently. 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 eld classes considered.

[gz] [pdf]

Tags: cryptography