Multiplicative Inverses

To be able to compute finite field multiplicative inverses, that is, 1/x, a trick has been used in this implementation. Using exponentiation and logarithms with a common base, the following identity can be utilized:

Using exponentiation and logarithms to compute 1/x.

In this case, the base number 3 has been chosen, as it is the simplest primitive root. By using finite field multiplication when computing the exponents and logarithms, the multiplicative inverse is easy to implement. Instead of computing exponents and logarithms every time, two lookup tables are used. Since the multiplicative inverse is only used when preparing the S-box described in S-Boxes, the memory used for the two lookup tables can be used for other purposes when the S-box has been prepared.

The lookup table computation can be described by the following pseudo code:

tempexp = 0
tempnum = 1
do
    exponentiation_table[ tempexp ] = tempnum
    logarithm_table[ tempnum ] = tempexp
    increase tempexp
    multiply tempnum by 3 modulo 0x11B
loop while tempexp < 256