O(log₂m) iterative algorithm for multiplicative inversion in GF(2^m)

Abstract

A new algorithm that can calculate the multiplicative inverses in GF(2m) with O(log2m) iterations is presented. While this algorithm requires in total the same number of multiplications ([log2(m - 1)] + Hw(m - 1) - 1) with the best known algorithm [1], the latency, if mapped to a hardware, can be reduced significantly ([log2(m - 2)] + 1), comparable to the best case result, which is implemented using Fermat's little theorem.