A fast algorithm for computing multiplicative inverses in \(\text{GF}(2^ m)\) using normal bases (Q1120276)

The authors develop fast algorithms for computing \(x^{-1}\) for non-zero elements \(x\) of \(\text{GF}(2^ m)\) and \(\text{GF}((2^ n)^ m)\) on a computer. For example, if \(m\) is odd \(x^{-1}\) can be computed by at most \(2\lfloor \log_ 2(m-1)\rfloor\) multiplications and \(m-1\) cyclic shifts. The results are obtained upon applying relations like \[ X^{2^{2^{r+1}}- 1}=(X^{2^{2^ r}-1})^{2^{2^ r}}(X^{2^{2^ r}-1}), \] in order to replace multiplications by cyclic shifts. The presentation is non-mathematical.