An Algorithm for Inversion in GF(2^m) Suitable for Implementation Using a Polynomial Multiply Instruction on GF(2)

摘要

An algorithm for inversion in GF(2m) suitable for implementation using a polynomial multiply instruction on GF(2) is proposed. It is based on the extended Euclid''s algorithm. In the algorithm, operations corresponding to several contiguous iterations of the VLSI algorithm proposed by Brunner et al. is represented as a matrix. They are calculated at once through the matrix efficiently by means of a polynomial multiply instruction on GF(2). For example, in the case where the word size of a processor and m are 32 and 571, respectively, the algorithm calculates inversion with about the half number of instructions of the conventional algorithm on the average.