Search code examples
javaencryptiongalois-field

Multiplicative inverse table GF(2^4) in Java or C array

I have to write a table look up for multiplicative inverse in GF(24). I already wrote out the multiplication table and I'm not looking forward to doing that again. Here's the table I wrote as an example. I hope nobody ever has to write this again. I felt stupid.

Multiplication table over GF(24) 

// Multiplication table over Galois Field 2^4 
byte mulTable[][] = {
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   0,   0,   0,   0,   0,   0},
        {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0xa, 0xb, 0xc, 0xd, 0xe, 0xf}, 
        {0, 2, 4, 6, 8, 0xa, 0xc, 0xe, 3, 1, 7, 5, 0xb, 9, 0xf, 0xd},
        {0, 3, 6, 5, 0xc, 0xf, 0xa, 9, 0xb, 8, 0xd, 0xe, 7, 4, 1, 2},
        {0, 4, 8, 0xc, 3, 7, 0xb, 0xf, 6, 2, 0xe, 0xa, 5, 1, 0xd, 9},
        {0, 5, 0xa, 0xf, 7, 2, 0xd, 8, 0xe, 0xb, 4, 1, 9, 0xc, 3, 6},
        {0, 6, 0xc, 0xa, 0xb, 0xd, 7, 1, 5, 3, 9, 0xf, 0xe, 8, 2, 4},
        {0, 7, 0xe, 9, 0xf, 8, 1, 6, 0xd, 0xa, 3, 4, 2, 5, 0xc, 0xb},
        {0, 8, 3, 0xb, 6, 0xe, 5, 0xd, 0xc, 4, 0xf, 7, 0xa, 2, 9, 1},
        {0, 9, 1, 8, 2, 0xb, 3, 0xa, 4, 0xd, 5, 0xc, 6, 0xf, 7, 0xe},
        {0, 0xa, 7, 0xd, 0xe, 4, 9, 3, 0xf, 5, 8, 2, 1, 0xb, 0xc, 6},
        {0, 0xb, 5, 0xe, 0xa, 1, 0xf, 4, 7, 0xc, 2, 9, 0xd, 6, 8, 3},
        {0, 0xc, 0xb, 7, 5, 9, 0xe, 2, 0xa, 6, 1, 0xd, 0xf, 3, 4, 8},
        {0, 0xd, 9, 4, 1, 0xc, 8, 5, 2, 0xf, 0xb, 6, 3, 0x3, 0xa, 7},
        {0, 0xe, 0xf, 1, 0xd, 3, 2, 0xc, 9, 7, 6, 8, 4, 0xa, 0xb, 5},
        {0, 0xf, 0xd, 2, 9, 6, 4, 0xb, 1, 0xe, 0xc, 3, 8, 7, 5, 0xa}
    };

I don't want to do that again for the inverses!
Does anyone know of a table (preferably in a Java or C 16x16 array) suitable for copying and pasting from? I searched github trying to find one that was written already, but no joy.

Motivation/Rational
I don't strictly have to have to do a table look up, but I don't want to add a hundred lines of code just to generate the field on the fly (that's just an estimate, but I doubt I could do it in less).

Solution

  • The multiplication table represents a binary operation "*": x * y = z if and only if mulTable[x][y] == z

    The inverse of an element x is another element y such that x * y = 1, equivalently mulTable[x][y] == 1. Sometimes the inverse does not exist. For this binary operation the inverse of 0 doesn't exist. With that background the following code computes the table of inverses using only the multiplication table you provided.

    public static byte[] computeInverseTable() {
    byte [] inverseTable = new byte[16];
    inverseTable[0] = 0; // the inverse of 0 doesn't exist.

    for (int x = 1; x<16; x++) {
        for (int y = 1; y<16; y++) {
            if (mulTable[x][y] == 1) {
                inverseTable[x] = (byte) y;
                break;
            }
        }
    }
    return inverseTable;
}