Fast Inversion in Composite Galois Fields GF((2 n ) m )

We describe an improvement of Itoh and Tsujii's algorithm for inversion over Galois fields GF ((2 n ) m ). In particular, raising an element to the 2 ln power, l an integer, in polynomial basis representation can be done with a binary, fixed matrix. Finally, we show that the inversion complexity is essentially given by the number of multiplications. I. Introduction Itoh and Tsujii's algorithm for inversion can be efficiently applied to Galois fields GF ((2 n ) m ) in normal and polynomial basis representations[1, 2]. In this contribution, we show considerable complexity improvements by choosing a binary field polynomial. We show the complexity of an inversion can depend almost entirely on the number of multiplications and we present complexity formulae for multiple squaring operations. II. Preliminaries [1, 2] compute A \Gamma1 = (A r ) \Gamma1 A r\Gamma1 , A 2 GF ((2 n ) m ),A 6= 0 , where A r 2 GF (2 n ) and r = (2 nm \Gamma 1)=(2 n \Gamma 1). This ..