How would I implement the Multiplicative Inverse in GF2^8 in Python 3? My current functions look like this:
def gf_add(a, b):
return a ^ b
def gf_mul(a, b, mod=0x1B):
p = bytes(hex(0x00))
for i in range(8):
if (b & 1) != 0:
p ^= a
high_bit_set = bytes(a & 0x80)
a <<= 1
if high_bit_set != 0:
a ^= mod
b >>= 1
return p
Here is how I'd do it:
The function
gf_degree
calculates the degree of the polynomial, andgf_invert
, naturally, inverts any element of GF(2^8), except 0, of course. The implementation ofgf_invert
follows a "text-book" algorithm on finding the multiplicative inverse of elements of a finite field.Example
Here is a live demo.
As mentioned in the comments you could also have used a logarithmic approach, or simply use brute force (trying every combination of multiplication).