4

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?

8
  • A Galois field of order p where p is a prime? Or arbitrary Galois fields? Or powers of specific primes?
    – Doc Brown
    Mar 22, 2016 at 22:55
  • @DocBrown No, p is the integer representation of the polynomial that defines the field.
    – Melab
    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.
    – Doc Brown
    Mar 23, 2016 at 6:37
  • 1
    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
    Mar 23, 2016 at 22:20
  • 1
    ??? 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.
    – Doc Brown
    Mar 24, 2016 at 7:01

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.