The Itoh-Tsujii inversion algorithm is used to invert elements in a finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

. It was introduced in 1988 and first used over GF(2^m) using the normal basis

Normal basis

In mathematics, a normal basis in field theory is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis...

 representation of elements, however the algorithm is generic and can be used for other bases, such as the polynomial basis

Polynomial basis

In mathematics, the polynomial basis is a basis for finite extensions of finite fields.Let α ∈ GF be the root of a primitive polynomial of degree m over GF...

. It can also be used in any finite field, GF(p^m).

The algorithm is as follows:

Input: A ∈ GF(p^m)

Output: A⁻¹

1. r ← (p^m − 1)/(p − 1)
2. compute A^{r − 1} in GF(p^m)
3. compute A^r = A^{r − 1} · A
4. compute (A^r)⁻¹ in GF(p)
5. compute A⁻¹ = (A^r)⁻¹ · A^{r −1}
6. return A⁻¹

This algorithm is fast because steps 3 and 5 both involve operations in the subfield GF(p). Similarly, if a small value of p is used a lookup table can be used for inversion in step 4. The majority of time spent in this algorithm is in step 2, the first exponentiation. This is one reason why this algorithm is well-suited for the normal basis, since squaring and exponentiation are relatively easy in that basis.