# Calculating the multiplicative inverse of a number in a Galois field

I was told to come here from Stack Overflow because I was "looking for an algorithm". I'm trying to implement it in Python, but there is nowhere on the net that gives a straightforward way for calculating the multiplicative inverse of a number in a Galois field.

The requirements for the algorithm are pretty simple:

• Input: A number representing the polynomial of a GF(2^n) field (`p`) and a number representing the polynomial of which to calculate the inverse of (`a`).
• Output: The number representing the polynomial which is the multiplicative inverse of `a` over `p`.

This has to be on the fly. I can't be bothered with calculating log/anti-log tables because those take up too much space when the field is large. I tried using the extended Euclidean algorithm described here on Wikipedia, but I don't know how to implement `(1/r)*t` and it triggers the error statement when I set `a` to `3` and `p` to `0x11b` (AES Galois field). This is incredibly frustrating that there is no simple code or simple explanation about multiplicative inverses in Galois fields. Any ideas for this algorithm I'm searching for?

• A Galois field of order p where p is a prime? Or arbitrary Galois fields? Or powers of specific primes? Commented Mar 22, 2016 at 22:55
• @DocBrown No, `p` is the integer representation of the polynomial that defines the field. Commented Mar 22, 2016 at 23:30
• For characteristics 2 I found this one: cs.colorado.edu/~jrblack/class/csci6454/s14/hw/ffield.py Did not try it by myself. Commented Mar 23, 2016 at 6:37
• Then strip it down, noone stops you from doing this. These are only 765 LOC, well documented, nothing which should give you a headache. Commented Mar 23, 2016 at 22:20
• ??? Line 175 ff, self.Inverse is asigned there (three possible definitions, each one optimized for a differnt order of the GF). Took me a simple "Ctrl-F" to find it. Commented Mar 24, 2016 at 7:01