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
aoverp.
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?
pis the integer representation of the polynomial that defines the field.