Show that for every nonzero element aGF127 we can compute it

Show that for every non-zero element a-GF(127), we can compute its multiplicative inverse a-1 (mod 127) with no more than 12 multiplications (including squaring operations).

Solution

Consider GF(128) = GF(2⁷)

We can write the polynomial equivalent as x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1

Thus, GF(127) = x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x = x(x⁶ + x⁵ + x⁴ + x³ + x² + x +1)

The degree of GF(127) is 7

If all the elements. a, are non zero, we can safely omit the x and degree of x⁶ + x⁵ + x⁴ + x³ + x² + x +1 is 6.

Each of the x can be 0 or 1 for powers of 1-6, thereby the total number of multiplicatiosn req = 12.