Calculating the multiplicative inverse of a number in a Galois field

Question

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?

• Doc Brown: A Galois field of order p where p is a prime? Or arbitrary Galois fields? Or powers of specific primes?
• Melab: @DocBrown No, p is the integer representation of the polynomial that defines the field.
• Doc Brown: For characteristics 2 I found this one: cs.colorado.edu/~jrblack/class/csci6454/s14/hw/ffield.py Did not try it by myself.
• Doc Brown: Then strip it down, noone stops you from doing this. These are only 765 LOC, well documented, nothing which should give you a headache.
• Doc Brown: ??? 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.