Galois Fields Multiplication

Guillermo Morales-Luna
Computer Science Section
CINVESTAV-IPN

Basic operations on the hypercube

Sucessor of an n-length binary string. The sucessor of the 1 constant string is the empty string.

\(suc[ls_, n_] := 
      Module[{ls1, i, fl}, 
ls1 = ls; i = 0; 
        fl = True; 
While[i < n\  && \ fl, \(i++\); 
          fl = \((ls1[\([n - i + 1]\)] == 1)\); 
          If[fl, ls1[\([n - i + 1]\)] = 0] ]; 
If[
          fl, {}, ls1[\([n - i + 1]\)] = 1; 
          ls1]
]\)

Right binary representation (the least significant digit appears at right, the most significant at left)

binrepri[s_, n_] := 
      Module[{x}, 
x = 
          s[[1]] ;  
Do[
          x = 2 x +  s[[i]], {i, 2, 
            n}]; 
x
]

Left binary representation

binreple[s_, n_] := binrepri[Reverse[s], n]

Complementary vector

comvec[s_, n_] := Table[Mod[1 + s[[i]], 2], {i, n}]

For any given integer x and length n, let us calculate the b-based representation of x of length n:

brep[x_, n_, b_] := 
      Module[{ar, i, j, x1}, 
ar = Table[0, {i, n}];  
        i = 1; x1 = x; 
While[
          x1 > 0  &&  i ≤ n, 
j = Mod[x1, b]; 
          x1 = (x1 - j)/b; 
          If[! j == 0, 
            ar[[i]] = 
              j]; 
i++]; 
ar
]

The base-2 representation is

binrep[x_, n_] := Reverse[brep[x, n, 2]]

Galois field multiplication

Basic definitions

Let F = {0,1}  be the Galois field of 2 elements. Given an n, the following procedure finds the minimum k such that p(X)=1+(X^k)+(X^n)is irreducible over F, if there is one such k, otherwise, it outputs the value n.

firr[n_] := 
      Module[{m, fl, px}, 
m = 0; 
        fl = True; 
While[
          fl, m++; 
px = 
            Factor[x^n + x^m + 1,  
              Modulus -> 
                2]; 
fl = (Head[px] == 
                Times)]; 
m
]

The i-th polynomial can be obtained as follows:

pol[i_, n_] := 
      Module[{s, pl}, 
s = 
          binrep[i, n]; 
pl = 
          Apply[Plus, Table[s[[k]] x^(n - k), {k, n}]]; 
        pl
]

The product of the i-th polynomial times the j-th polynomial reduced by the irreducible polynomial (X^n)+ (X^k)+1 is

prdpol[i_, j_, k_, n_] := 
      Module[{s, t, px}, 
s = pol[i, n]; t = pol[j, n];  
        px = Expand[s t] ; 
PolynomialRemainder[px, 
          x^n + x^k + 1, x]
]

Taking module 2 over the coefficients, we get

red[i_, j_, k_, n_] := 
      Module[{pix, tb, cf}, 
pix = 
          prdpol[i, j, k, n]; 
tb = 
          Table[pix - PolynomialRemainder[pix, x^k1, x], {k1, 0, 
              n - 1}]; 
cf = 
          Table[(tb[[i1]] - tb[[i1 + 1]])/x^(i1 - 1), {i1, 
              n - 1}]; 
AppendTo[cf, 
          tb[[n]]/x^(n - 1)]; 
cf = 
          Mod[cf, 2]; 
binreple[cf, 
          n]
]

The table of the Galois field multiplication is calculated as follows

gfml[n_] := 
      Module[{k, twn}, 
k = firr[n]; 
If[
          k == n, {}, 
twn = 
            2^n - 1; 
Table[
            red[i, j, k, n], {i, 0, twn}, {j, 0, 
              twn}]
]]

Examples

According to the above definition, the following tables for the Galois field multiplication result:

tb2 = {{0, 0, 0, 0}, {0, 1, 2, 3}, {0, 2, 3, 1}, {0, 3, 1, 
            2}};
tb3 = {{0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 2, 3, 4, 5, 6, 7}, {0, 2, 4, 
            6, 3, 1, 7, 5}, {0, 3, 6, 5, 7, 4, 1, 2}, {0, 4, 3, 7, 6, 2, 5, 
            1}, {0, 5, 1, 4, 2, 7, 3, 6}, {0, 6, 7, 1, 5, 3, 2, 4}, {0, 7, 5, 
            2, 1, 6, 4, 3}};
tb4 = {{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, 10, 11, 12, 13, 14, 15}, {0, 2, 4, 6, 8, 10, 
            12, 14, 3, 1, 7, 5, 11, 9, 15, 13}, {0, 3, 6, 5, 12, 15, 10, 9, 
            11, 8, 13, 14, 7, 4, 1, 2}, {0, 4, 8, 12, 3, 7, 11, 15, 6, 2, 14, 
            10, 5, 1, 13, 9}, {0, 5, 10, 15, 7, 2, 13, 8, 14, 11, 4, 1, 9, 
            12, 3, 6}, {0, 6, 12, 10, 11, 13, 7, 1, 5, 3, 9, 15, 14, 8, 2, 
            4}, {0, 7, 14, 9, 15, 8, 1, 6, 13, 10, 3, 4, 2, 5, 12, 11}, {0, 
            8, 3, 11, 6, 14, 5, 13, 12, 4, 15, 7, 10, 2, 9, 1}, {0, 9, 1, 8, 
            2, 11, 3, 10, 4, 13, 5, 12, 6, 15, 7, 14}, {0, 10, 7, 13, 14, 4, 
            9, 3, 15, 5, 8, 2, 1, 11, 6, 12}, {0, 11, 5, 14, 10, 1, 15, 4, 7, 
            12, 2, 9, 13, 6, 8, 3}, {0, 12, 11, 7, 5, 9, 14, 2, 10, 6, 1, 13, 
            15, 3, 4, 8}, {0, 13, 9, 4, 1, 12, 8, 5, 2, 15, 11, 6, 3, 14, 10, 
            7}, {0, 14, 15, 1, 13, 3, 2, 12, 9, 7, 6, 8, 4, 10, 11, 5}, {0, 
            15, 13, 2, 9, 6, 4, 11, 1, 14, 12, 3, 8, 7, 5, 
            10}};
tb5 = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 
            25, 26, 27, 28, 29, 30, 31}, {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 
            20, 22, 24, 26, 28, 30, 5, 7, 1, 3, 13, 15, 9, 11, 21, 23, 17, 
            19, 29, 31, 25, 27}, {0, 3, 6, 5, 12, 15, 10, 9, 24, 27, 30, 29, 
            20, 23, 18, 17, 21, 22, 19, 16, 25, 26, 31, 28, 13, 14, 11, 8, 1, 
            2, 7, 4}, {0, 4, 8, 12, 16, 20, 24, 28, 5, 1, 13, 9, 21, 17, 29, 
            25, 10, 14, 2, 6, 26, 30, 18, 22, 15, 11, 7, 3, 31, 27, 23, 
            19}, {0, 5, 10, 15, 20, 17, 30, 27, 13, 8, 7, 2, 25, 28, 19, 22, 
            26, 31, 16, 21, 14, 11, 4, 1, 23, 18, 29, 24, 3, 6, 9, 12}, {0, 
            6, 12, 10, 24, 30, 20, 18, 21, 19, 25, 31, 13, 11, 1, 7, 15, 9, 
            3, 5, 23, 17, 27, 29, 26, 28, 22, 16, 2, 4, 14, 8}, {0, 7, 14, 9, 
            28, 27, 18, 21, 29, 26, 19, 20, 1, 6, 15, 8, 31, 24, 17, 22, 3, 
            4, 13, 10, 2, 5, 12, 11, 30, 25, 16, 23}, {0, 8, 16, 24, 5, 13, 
            21, 29, 10, 2, 26, 18, 15, 7, 31, 23, 20, 28, 4, 12, 17, 25, 1, 
            9, 30, 22, 14, 6, 27, 19, 11, 3}, {0, 9, 18, 27, 1, 8, 19, 26, 2, 
            11, 16, 25, 3, 10, 17, 24, 4, 13, 22, 31, 5, 12, 23, 30, 6, 15, 
            20, 29, 7, 14, 21, 28}, {0, 10, 20, 30, 13, 7, 25, 19, 26, 16, 
            14, 4, 23, 29, 3, 9, 17, 27, 5, 15, 28, 22, 8, 2, 11, 1, 31, 21, 
            6, 12, 18, 24}, {0, 11, 22, 29, 9, 2, 31, 20, 18, 25, 4, 15, 27, 
            16, 13, 6, 1, 10, 23, 28, 8, 3, 30, 21, 19, 24, 5, 14, 26, 17, 
            12, 7}, {0, 12, 24, 20, 21, 25, 13, 1, 15, 3, 23, 27, 26, 22, 2, 
            14, 30, 18, 6, 10, 11, 7, 19, 31, 17, 29, 9, 5, 4, 8, 28, 
            16}, {0, 13, 26, 23, 17, 28, 11, 6, 7, 10, 29, 16, 22, 27, 12, 1, 
            14, 3, 20, 25, 31, 18, 5, 8, 9, 4, 19, 30, 24, 21, 2, 15}, {0, 
            14, 28, 18, 29, 19, 1, 15, 31, 17, 3, 13, 2, 12, 30, 16, 27, 21, 
            7, 9, 6, 8, 26, 20, 4, 10, 24, 22, 25, 23, 5, 11}, {0, 15, 30, 
            17, 25, 22, 7, 8, 23, 24, 9, 6, 14, 1, 16, 31, 11, 4, 21, 26, 18, 
            29, 12, 3, 28, 19, 2, 13, 5, 10, 27, 20}, {0, 16, 5, 21, 10, 26, 
            15, 31, 20, 4, 17, 1, 30, 14, 27, 11, 13, 29, 8, 24, 7, 23, 2, 
            18, 25, 9, 28, 12, 19, 3, 22, 6}, {0, 17, 7, 22, 14, 31, 9, 24, 
            28, 13, 27, 10, 18, 3, 21, 4, 29, 12, 26, 11, 19, 2, 20, 5, 1, 
            16, 6, 23, 15, 30, 8, 25}, {0, 18, 1, 19, 2, 16, 3, 17, 4, 22, 5, 
            23, 6, 20, 7, 21, 8, 26, 9, 27, 10, 24, 11, 25, 12, 30, 13, 31, 
            14, 28, 15, 29}, {0, 19, 3, 16, 6, 21, 5, 22, 12, 31, 15, 28, 10, 
            25, 9, 26, 24, 11, 27, 8, 30, 13, 29, 14, 20, 7, 23, 4, 18, 1, 
            17, 2}, {0, 20, 13, 25, 26, 14, 23, 3, 17, 5, 28, 8, 11, 31, 6, 
            18, 7, 19, 10, 30, 29, 9, 16, 4, 22, 2, 27, 15, 12, 24, 1, 
            21}, {0, 21, 15, 26, 30, 11, 17, 4, 25, 12, 22, 3, 7, 18, 8, 29, 
            23, 2, 24, 13, 9, 28, 6, 19, 14, 27, 1, 20, 16, 5, 31, 10}, {0, 
            22, 9, 31, 18, 4, 27, 13, 1, 23, 8, 30, 19, 5, 26, 12, 2, 20, 11, 
            29, 16, 6, 25, 15, 3, 21, 10, 28, 17, 7, 24, 14}, {0, 23, 11, 28, 
            22, 1, 29, 10, 9, 30, 2, 21, 31, 8, 20, 3, 18, 5, 25, 14, 4, 19, 
            15, 24, 27, 12, 16, 7, 13, 26, 6, 17}, {0, 24, 21, 13, 15, 23, 
            26, 2, 30, 6, 11, 19, 17, 9, 4, 28, 25, 1, 12, 20, 22, 14, 3, 27, 
            7, 31, 18, 10, 8, 16, 29, 5}, {0, 25, 23, 14, 11, 18, 28, 5, 22, 
            15, 1, 24, 29, 4, 10, 19, 9, 16, 30, 7, 2, 27, 21, 12, 31, 6, 8, 
            17, 20, 13, 3, 26}, {0, 26, 17, 11, 7, 29, 22, 12, 14, 20, 31, 5, 
            9, 19, 24, 2, 28, 6, 13, 23, 27, 1, 10, 16, 18, 8, 3, 25, 21, 15, 
            4, 30}, {0, 27, 19, 8, 3, 24, 16, 11, 6, 29, 21, 14, 5, 30, 22, 
            13, 12, 23, 31, 4, 15, 20, 28, 7, 10, 17, 25, 2, 9, 18, 26, 
            1}, {0, 28, 29, 1, 31, 3, 2, 30, 27, 7, 6, 26, 4, 24, 25, 5, 19, 
            15, 14, 18, 12, 16, 17, 13, 8, 20, 21, 9, 23, 11, 10, 22}, {0, 
            29, 31, 2, 27, 6, 4, 25, 19, 14, 12, 17, 8, 21, 23, 10, 3, 30, 
            28, 1, 24, 5, 7, 26, 16, 13, 15, 18, 11, 22, 20, 9}, {0, 30, 25, 
            7, 23, 9, 14, 16, 11, 21, 18, 12, 28, 2, 5, 27, 22, 8, 15, 17, 1, 
            31, 24, 6, 29, 3, 4, 26, 10, 20, 19, 13}, {0, 31, 27, 4, 19, 12, 
            8, 23, 3, 28, 24, 7, 16, 15, 11, 20, 6, 25, 29, 2, 21, 10, 14, 
            17, 5, 26, 30, 1, 22, 9, 13, 18}};

As density plot graphs, they are displayed as follows:

ListDensityPlot[tb2]

ListDensityPlot[tb3]

ListDensityPlot[tb4]

ListDensityPlot[tb5]

Ring multiplication

Basic definitions

The ring multiplication, modulus n, is

rngml[n_] := 
      Table[Mod[i j, n], {i, 0, n - 1}, {j, 0, n - 1}]

thus, the ring multiplication in the Galois field, is

rnmtgf[n_] := rngml[2^n]

Examples

The following tables result,

sb2 = {{0, 0, 0, 0}, {0, 1, 2, 3}, {0, 2, 0, 2}, {0, 3, 2, 
            1}};
sb3 = {{0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 2, 3, 4, 5, 6, 7}, {0, 2, 4, 
            6, 0, 2, 4, 6}, {0, 3, 6, 1, 4, 7, 2, 5}, {0, 4, 0, 4, 0, 4, 0, 
            4}, {0, 5, 2, 7, 4, 1, 6, 3}, {0, 6, 4, 2, 0, 6, 4, 2}, {0, 7, 6, 
            5, 4, 3, 2, 1}};
sb4 = {{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, 10, 11, 12, 13, 14, 15}, {0, 2, 4, 6, 8, 10, 
            12, 14, 0, 2, 4, 6, 8, 10, 12, 14}, {0, 3, 6, 9, 12, 15, 2, 5, 8, 
            11, 14, 1, 4, 7, 10, 13}, {0, 4, 8, 12, 0, 4, 8, 12, 0, 4, 8, 12, 
            0, 4, 8, 12}, {0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 1, 6, 
            11}, {0, 6, 12, 2, 8, 14, 4, 10, 0, 6, 12, 2, 8, 14, 4, 10}, {0, 
            7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9}, {0, 8, 0, 8, 
            0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8}, {0, 9, 2, 11, 4, 13, 6, 15, 
            8, 1, 10, 3, 12, 5, 14, 7}, {0, 10, 4, 14, 8, 2, 12, 6, 0, 10, 4, 
            14, 8, 2, 12, 6}, {0, 11, 6, 1, 12, 7, 2, 13, 8, 3, 14, 9, 4, 15, 
            10, 5}, {0, 12, 8, 4, 0, 12, 8, 4, 0, 12, 8, 4, 0, 12, 8, 4}, {0, 
            13, 10, 7, 4, 1, 14, 11, 8, 5, 2, 15, 12, 9, 6, 3}, {0, 14, 12, 
            10, 8, 6, 4, 2, 0, 14, 12, 10, 8, 6, 4, 2}, {0, 15, 14, 13, 12, 
            11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}};
sb5 = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 
            25, 26, 27, 28, 29, 30, 31}, {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 
            20, 22, 24, 26, 28, 30, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 
            22, 24, 26, 28, 30}, {0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 1, 
            4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 2, 5, 8, 11, 14, 17, 20, 
            23, 26, 29}, {0, 4, 8, 12, 16, 20, 24, 28, 0, 4, 8, 12, 16, 20, 
            24, 28, 0, 4, 8, 12, 16, 20, 24, 28, 0, 4, 8, 12, 16, 20, 24, 
            28}, {0, 5, 10, 15, 20, 25, 30, 3, 8, 13, 18, 23, 28, 1, 6, 11, 
            16, 21, 26, 31, 4, 9, 14, 19, 24, 29, 2, 7, 12, 17, 22, 27}, {0, 
            6, 12, 18, 24, 30, 4, 10, 16, 22, 28, 2, 8, 14, 20, 26, 0, 6, 12, 
            18, 24, 30, 4, 10, 16, 22, 28, 2, 8, 14, 20, 26}, {0, 7, 14, 21, 
            28, 3, 10, 17, 24, 31, 6, 13, 20, 27, 2, 9, 16, 23, 30, 5, 12, 
            19, 26, 1, 8, 15, 22, 29, 4, 11, 18, 25}, {0, 8, 16, 24, 0, 8, 
            16, 24, 0, 8, 16, 24, 0, 8, 16, 24, 0, 8, 16, 24, 0, 8, 16, 24, 
            0, 8, 16, 24, 0, 8, 16, 24}, {0, 9, 18, 27, 4, 13, 22, 31, 8, 17, 
            26, 3, 12, 21, 30, 7, 16, 25, 2, 11, 20, 29, 6, 15, 24, 1, 10, 
            19, 28, 5, 14, 23}, {0, 10, 20, 30, 8, 18, 28, 6, 16, 26, 4, 14, 
            24, 2, 12, 22, 0, 10, 20, 30, 8, 18, 28, 6, 16, 26, 4, 14, 24, 2, 
            12, 22}, {0, 11, 22, 1, 12, 23, 2, 13, 24, 3, 14, 25, 4, 15, 26, 
            5, 16, 27, 6, 17, 28, 7, 18, 29, 8, 19, 30, 9, 20, 31, 10, 
            21}, {0, 12, 24, 4, 16, 28, 8, 20, 0, 12, 24, 4, 16, 28, 8, 20, 
            0, 12, 24, 4, 16, 28, 8, 20, 0, 12, 24, 4, 16, 28, 8, 20}, {0, 
            13, 26, 7, 20, 1, 14, 27, 8, 21, 2, 15, 28, 9, 22, 3, 16, 29, 10, 
            23, 4, 17, 30, 11, 24, 5, 18, 31, 12, 25, 6, 19}, {0, 14, 28, 10, 
            24, 6, 20, 2, 16, 30, 12, 26, 8, 22, 4, 18, 0, 14, 28, 10, 24, 6, 
            20, 2, 16, 30, 12, 26, 8, 22, 4, 18}, {0, 15, 30, 13, 28, 11, 26, 
            9, 24, 7, 22, 5, 20, 3, 18, 1, 16, 31, 14, 29, 12, 27, 10, 25, 8, 
            23, 6, 21, 4, 19, 2, 17}, {0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 
            16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 16, 0, 
            16, 0, 16}, {0, 17, 2, 19, 4, 21, 6, 23, 8, 25, 10, 27, 12, 29, 
            14, 31, 16, 1, 18, 3, 20, 5, 22, 7, 24, 9, 26, 11, 28, 13, 30, 
            15}, {0, 18, 4, 22, 8, 26, 12, 30, 16, 2, 20, 6, 24, 10, 28, 14, 
            0, 18, 4, 22, 8, 26, 12, 30, 16, 2, 20, 6, 24, 10, 28, 14}, {0, 
            19, 6, 25, 12, 31, 18, 5, 24, 11, 30, 17, 4, 23, 10, 29, 16, 3, 
            22, 9, 28, 15, 2, 21, 8, 27, 14, 1, 20, 7, 26, 13}, {0, 20, 8, 
            28, 16, 4, 24, 12, 0, 20, 8, 28, 16, 4, 24, 12, 0, 20, 8, 28, 16, 
            4, 24, 12, 0, 20, 8, 28, 16, 4, 24, 12}, {0, 21, 10, 31, 20, 9, 
            30, 19, 8, 29, 18, 7, 28, 17, 6, 27, 16, 5, 26, 15, 4, 25, 14, 3, 
            24, 13, 2, 23, 12, 1, 22, 11}, {0, 22, 12, 2, 24, 14, 4, 26, 16, 
            6, 28, 18, 8, 30, 20, 10, 0, 22, 12, 2, 24, 14, 4, 26, 16, 6, 28, 
            18, 8, 30, 20, 10}, {0, 23, 14, 5, 28, 19, 10, 1, 24, 15, 6, 29, 
            20, 11, 2, 25, 16, 7, 30, 21, 12, 3, 26, 17, 8, 31, 22, 13, 4, 
            27, 18, 9}, {0, 24, 16, 8, 0, 24, 16, 8, 0, 24, 16, 8, 0, 24, 16, 
            8, 0, 24, 16, 8, 0, 24, 16, 8, 0, 24, 16, 8, 0, 24, 16, 8}, {0, 
            25, 18, 11, 4, 29, 22, 15, 8, 1, 26, 19, 12, 5, 30, 23, 16, 9, 2, 
            27, 20, 13, 6, 31, 24, 17, 10, 3, 28, 21, 14, 7}, {0, 26, 20, 14, 
            8, 2, 28, 22, 16, 10, 4, 30, 24, 18, 12, 6, 0, 26, 20, 14, 8, 2, 
            28, 22, 16, 10, 4, 30, 24, 18, 12, 6}, {0, 27, 22, 17, 12, 7, 2, 
            29, 24, 19, 14, 9, 4, 31, 26, 21, 16, 11, 6, 1, 28, 23, 18, 13, 
            8, 3, 30, 25, 20, 15, 10, 5}, {0, 28, 24, 20, 16, 12, 8, 4, 0, 
            28, 24, 20, 16, 12, 8, 4, 0, 28, 24, 20, 16, 12, 8, 4, 0, 28, 24, 
            20, 16, 12, 8, 4}, {0, 29, 26, 23, 20, 17, 14, 11, 8, 5, 2, 31, 
            28, 25, 22, 19, 16, 13, 10, 7, 4, 1, 30, 27, 24, 21, 18, 15, 12, 
            9, 6, 3}, {0, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 
            4, 2, 0, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 
            2}, {0, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 
            17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 
            1}};

Displayed as density plots,

ListDensityPlot[sb2]

ListDensityPlot[sb3]

ListDensityPlot[sb4]

ListDensityPlot[sb5]

Logarithmic multiplication

Basic definitions

Since in any Galois field the non-null elements form a cyclic group with the multiplication, let us represent each element as the power of a generator. Then the field multiplication is reduced to addition modulus (2^n) - 1.

cm[i_, j_, n_] := 
      If[i == 0, 0, Mod[(i - 1)  + (j - 1), n] + 1]

cmt[i_, j_, n_] := 
      If[i ≤ j, cm[i, j, n], cm[j, i, n]]

cmgf[n_] := 
      Module[{twn}, 
twn = 
          2^n - 1; 
Table[
          cmt[i, j, twn], {i, 0, twn}, {j, 0, 
            twn}]
]

Examples

With the above defined operation we have

ub2 = {{0, 0, 0, 0}, {0, 1, 2, 3}, {0, 2, 3, 1}, {0, 3, 1, 
            2}};
ub3 = {{0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 2, 3, 4, 5, 6, 7}, {0, 2, 3, 
            4, 5, 6, 7, 1}, {0, 3, 4, 5, 6, 7, 1, 2}, {0, 4, 5, 6, 7, 1, 2, 
            3}, {0, 5, 6, 7, 1, 2, 3, 4}, {0, 6, 7, 1, 2, 3, 4, 5}, {0, 7, 1, 
            2, 3, 4, 5, 6}};
ub4 = {{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, 10, 11, 12, 13, 14, 15}, {0, 2, 3, 4, 5, 6, 7, 
            8, 9, 10, 11, 12, 13, 14, 15, 1}, {0, 3, 4, 5, 6, 7, 8, 9, 10, 
            11, 12, 13, 14, 15, 1, 2}, {0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 
            14, 15, 1, 2, 3}, {0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 
            2, 3, 4}, {0, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 2, 3, 4, 
            5}, {0, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 2, 3, 4, 5, 6}, {0, 
            8, 9, 10, 11, 12, 13, 14, 15, 1, 2, 3, 4, 5, 6, 7}, {0, 9, 10, 
            11, 12, 13, 14, 15, 1, 2, 3, 4, 5, 6, 7, 8}, {0, 10, 11, 12, 13, 
            14, 15, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {0, 11, 12, 13, 14, 15, 1, 2, 
            3, 4, 5, 6, 7, 8, 9, 10}, {0, 12, 13, 14, 15, 1, 2, 3, 4, 5, 6, 
            7, 8, 9, 10, 11}, {0, 13, 14, 15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
            11, 12}, {0, 14, 15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 
            13}, {0, 15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 
            14}};
ub5 = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 
            25, 26, 27, 28, 29, 30, 31}, {0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 
            12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 
            28, 29, 30, 31, 1}, {0, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 
            15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 
            31, 1, 2}, {0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 
            18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 1, 2, 
            3}, {0, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 
            20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 1, 2, 3, 4}, {0, 
            6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 
            23, 24, 25, 26, 27, 28, 29, 30, 31, 1, 2, 3, 4, 5}, {0, 7, 8, 9, 
            10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 
            26, 27, 28, 29, 30, 31, 1, 2, 3, 4, 5, 6}, {0, 8, 9, 10, 11, 12, 
            13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 
            29, 30, 31, 1, 2, 3, 4, 5, 6, 7}, {0, 9, 10, 11, 12, 13, 14, 15, 
            16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 
            1, 2, 3, 4, 5, 6, 7, 8}, {0, 10, 11, 12, 13, 14, 15, 16, 17, 18, 
            19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 1, 2, 3, 4, 
            5, 6, 7, 8, 9}, {0, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 
            22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 
            9, 10}, {0, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 
            25, 26, 27, 28, 29, 30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
            11}, {0, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 
            27, 28, 29, 30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, {0, 
            14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
            30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}, {0, 15, 16, 
            17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 1, 2, 
            3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}, {0, 16, 17, 18, 19, 20, 
            21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 1, 2, 3, 4, 5, 6, 7, 
            8, 9, 10, 11, 12, 13, 14, 15}, {0, 17, 18, 19, 20, 21, 22, 23, 
            24, 25, 26, 27, 28, 29, 30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
            11, 12, 13, 14, 15, 16}, {0, 18, 19, 20, 21, 22, 23, 24, 25, 26, 
            27, 28, 29, 30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 
            14, 15, 16, 17}, {0, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
            30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 
            17, 18}, {0, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 1, 
            2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 
            19}, {0, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 1, 2, 3, 4, 
            5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}, {0, 
            22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 
            9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21}, {0, 23, 24, 
            25, 26, 27, 28, 29, 30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 
            12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}, {0, 24, 25, 26, 27, 
            28, 29, 30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 
            15, 16, 17, 18, 19, 20, 21, 22, 23}, {0, 25, 26, 27, 28, 29, 30, 
            31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 
            18, 19, 20, 21, 22, 23, 24}, {0, 26, 27, 28, 29, 30, 31, 1, 2, 3, 
            4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 
            22, 23, 24, 25}, {0, 27, 28, 29, 30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 
            9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 
            25, 26}, {0, 28, 29, 30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 
            12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 
            27}, {0, 29, 30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 
            14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28}, {0, 
            30, 31, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 
            17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29}, {0, 31, 1, 
            2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 
            20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30}};

Displaying as density plots:

ListDensityPlot[ub2]

ListDensityPlot[ub3]

ListDensityPlot[ub4]

ListDensityPlot[ub5]

Exploration of field multiplication

Whenever the multiplication table tb is provided, the following procedure calculates the orbit of an element x:

orbttb[x_, tb_] := 
      Module[{n, s, x1, ls}, 
n = 
          Length[tb]; 
If[
          x ≥ n, {}, 
x1 = x + 1; s = x1; 
          ls = {x}; 
          s = tb[[s, x1]]; 
While[! MemberQ[ls, s], 
            AppendTo[ls, s]; s++; 
            s = tb[[s, 
                  x1]]]; 
ls]
]

The following procedure calculates the orbit of an element x in the multiplication group of the Galois field of degree n, with k as the second power of the irreducible polynomial:

orbt[i_, k_, n_] := 
      Module[{twn, s, ls}, 
twn = 
          2^n; 
If[
          i ≥ twn, {}, 
s = i; ls = {i}; 
          s = red[s, i, k, n]; 
While[! MemberQ[ls, s], 
            AppendTo[ls, s]; 
            s = red[s, i, k, 
                n]]; 
ls]
]

Let us make a Monte Carlo experiment to select generators in the cyclic multiplicative group of the Galois field. Obviously, it makes sense just in the case where (2^n)-1 is not a prime number. Given l, there are done l random selections of non-null elements and they ar classified according to their orbits length:

essys[l_, k_, n_] := 
      Module[{dv, elts, ctr, i, ls, lg, k1}, 
dv = {}; 
        elts = {}; 
        ctr = 0; 
Do[i = Random[Integer, {0, 2^n - 1}]; 
          ls = orbt[i, k, n]; 
lg = 
            Length[ls]; 
If[
            MemberQ[dv, lg], 
{{k1}} = 
              Position[dv, lg]; 
AppendTo[elts[[k1]], 
              i]
, 
AppendTo[dv, lg]; 
            AppendTo[
              elts, {i}]; ctr++
]
, {j, l}]; 
Table[{dv[[j]], elts[[j]]}, {j, 
            ctr}]]

Addition in the Galois field

Basic definition

The addition is bitwise xor:

addgf[i_, j_, n_] := 
      Module[{s, t}, 
s = binrep[i, n]; t = binrep[j, n]; 
        s = Mod[s + t, 2]; binrepri[s, n]
]

and the whole table calculation is

gfad[n_] := 
      Module[{twn}, 
twn = 
          2^n - 1; 
Table[
          addgf[i, j, n], {i, 0, twn}, {j, 0, 
            twn}]
]

Examples

According to the above procedure, we get

ad2 = {{0, 1, 2, 3}, {1, 0, 3, 2}, {2, 3, 0, 1}, {3, 2, 1, 
            0}};
ad3 = {{0, 1, 2, 3, 4, 5, 6, 7}, {1, 0, 3, 2, 5, 4, 7, 6}, {2, 3, 0, 
            1, 6, 7, 4, 5}, {3, 2, 1, 0, 7, 6, 5, 4}, {4, 5, 6, 7, 0, 1, 2, 
            3}, {5, 4, 7, 6, 1, 0, 3, 2}, {6, 7, 4, 5, 2, 3, 0, 1}, {7, 6, 5, 
            4, 3, 2, 1, 0}};
ad4 = {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 0, 
            3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14}, {2, 3, 0, 1, 6, 
            7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13}, {3, 2, 1, 0, 7, 6, 5, 4, 
            11, 10, 9, 8, 15, 14, 13, 12}, {4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 
            14, 15, 8, 9, 10, 11}, {5, 4, 7, 6, 1, 0, 3, 2, 13, 12, 15, 14, 
            9, 8, 11, 10}, {6, 7, 4, 5, 2, 3, 0, 1, 14, 15, 12, 13, 10, 11, 
            8, 9}, {7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 
            8}, {8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7}, {9, 
            8, 11, 10, 13, 12, 15, 14, 1, 0, 3, 2, 5, 4, 7, 6}, {10, 11, 8, 
            9, 14, 15, 12, 13, 2, 3, 0, 1, 6, 7, 4, 5}, {11, 10, 9, 8, 15, 
            14, 13, 12, 3, 2, 1, 0, 7, 6, 5, 4}, {12, 13, 14, 15, 8, 9, 10, 
            11, 4, 5, 6, 7, 0, 1, 2, 3}, {13, 12, 15, 14, 9, 8, 11, 10, 5, 4, 
            7, 6, 1, 0, 3, 2}, {14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 
            3, 0, 1}, {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 
            0}};
ad5 = {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 
            18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}, {1, 0, 
            3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14, 17, 16, 19, 18, 
            21, 20, 23, 22, 25, 24, 27, 26, 29, 28, 31, 30}, {2, 3, 0, 1, 6, 
            7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13, 18, 19, 16, 17, 22, 23, 
            20, 21, 26, 27, 24, 25, 30, 31, 28, 29}, {3, 2, 1, 0, 7, 6, 5, 4, 
            11, 10, 9, 8, 15, 14, 13, 12, 19, 18, 17, 16, 23, 22, 21, 20, 27, 
            26, 25, 24, 31, 30, 29, 28}, {4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 
            15, 8, 9, 10, 11, 20, 21, 22, 23, 16, 17, 18, 19, 28, 29, 30, 31, 
            24, 25, 26, 27}, {5, 4, 7, 6, 1, 0, 3, 2, 13, 12, 15, 14, 9, 8, 
            11, 10, 21, 20, 23, 22, 17, 16, 19, 18, 29, 28, 31, 30, 25, 24, 
            27, 26}, {6, 7, 4, 5, 2, 3, 0, 1, 14, 15, 12, 13, 10, 11, 8, 9, 
            22, 23, 20, 21, 18, 19, 16, 17, 30, 31, 28, 29, 26, 27, 24, 
            25}, {7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8, 23, 
            22, 21, 20, 19, 18, 17, 16, 31, 30, 29, 28, 27, 26, 25, 24}, {8, 
            9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 24, 25, 26, 
            27, 28, 29, 30, 31, 16, 17, 18, 19, 20, 21, 22, 23}, {9, 8, 11, 
            10, 13, 12, 15, 14, 1, 0, 3, 2, 5, 4, 7, 6, 25, 24, 27, 26, 29, 
            28, 31, 30, 17, 16, 19, 18, 21, 20, 23, 22}, {10, 11, 8, 9, 14, 
            15, 12, 13, 2, 3, 0, 1, 6, 7, 4, 5, 26, 27, 24, 25, 30, 31, 28, 
            29, 18, 19, 16, 17, 22, 23, 20, 21}, {11, 10, 9, 8, 15, 14, 13, 
            12, 3, 2, 1, 0, 7, 6, 5, 4, 27, 26, 25, 24, 31, 30, 29, 28, 19, 
            18, 17, 16, 23, 22, 21, 20}, {12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 
            6, 7, 0, 1, 2, 3, 28, 29, 30, 31, 24, 25, 26, 27, 20, 21, 22, 23, 
            16, 17, 18, 19}, {13, 12, 15, 14, 9, 8, 11, 10, 5, 4, 7, 6, 1, 0, 
            3, 2, 29, 28, 31, 30, 25, 24, 27, 26, 21, 20, 23, 22, 17, 16, 19, 
            18}, {14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1, 30, 
            31, 28, 29, 26, 27, 24, 25, 22, 23, 20, 21, 18, 19, 16, 17}, {15, 
            14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 31, 30, 29, 28, 
            27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16}, {16, 17, 18, 19, 
            20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 
            6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {17, 16, 19, 18, 21, 20, 23, 
            22, 25, 24, 27, 26, 29, 28, 31, 30, 1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 
            11, 10, 13, 12, 15, 14}, {18, 19, 16, 17, 22, 23, 20, 21, 26, 27, 
            24, 25, 30, 31, 28, 29, 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9, 14, 
            15, 12, 13}, {19, 18, 17, 16, 23, 22, 21, 20, 27, 26, 25, 24, 31, 
            30, 29, 28, 3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 
            12}, {20, 21, 22, 23, 16, 17, 18, 19, 28, 29, 30, 31, 24, 25, 26, 
            27, 4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 8, 9, 10, 11}, {21, 
            20, 23, 22, 17, 16, 19, 18, 29, 28, 31, 30, 25, 24, 27, 26, 5, 4, 
            7, 6, 1, 0, 3, 2, 13, 12, 15, 14, 9, 8, 11, 10}, {22, 23, 20, 21, 
            18, 19, 16, 17, 30, 31, 28, 29, 26, 27, 24, 25, 6, 7, 4, 5, 2, 3, 
            0, 1, 14, 15, 12, 13, 10, 11, 8, 9}, {23, 22, 21, 20, 19, 18, 17, 
            16, 31, 30, 29, 28, 27, 26, 25, 24, 7, 6, 5, 4, 3, 2, 1, 0, 15, 
            14, 13, 12, 11, 10, 9, 8}, {24, 25, 26, 27, 28, 29, 30, 31, 16, 
            17, 18, 19, 20, 21, 22, 23, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 
            2, 3, 4, 5, 6, 7}, {25, 24, 27, 26, 29, 28, 31, 30, 17, 16, 19, 
            18, 21, 20, 23, 22, 9, 8, 11, 10, 13, 12, 15, 14, 1, 0, 3, 2, 5, 
            4, 7, 6}, {26, 27, 24, 25, 30, 31, 28, 29, 18, 19, 16, 17, 22, 
            23, 20, 21, 10, 11, 8, 9, 14, 15, 12, 13, 2, 3, 0, 1, 6, 7, 4, 
            5}, {27, 26, 25, 24, 31, 30, 29, 28, 19, 18, 17, 16, 23, 22, 21, 
            20, 11, 10, 9, 8, 15, 14, 13, 12, 3, 2, 1, 0, 7, 6, 5, 4}, {28, 
            29, 30, 31, 24, 25, 26, 27, 20, 21, 22, 23, 16, 17, 18, 19, 12, 
            13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3}, {29, 28, 31, 
            30, 25, 24, 27, 26, 21, 20, 23, 22, 17, 16, 19, 18, 13, 12, 15, 
            14, 9, 8, 11, 10, 5, 4, 7, 6, 1, 0, 3, 2}, {30, 31, 28, 29, 26, 
            27, 24, 25, 22, 23, 20, 21, 18, 19, 16, 17, 14, 15, 12, 13, 10, 
            11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1}, {31, 30, 29, 28, 27, 26, 25, 
            24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 
            7, 6, 5, 4, 3, 2, 1, 0}};

In a graphical way,

ListDensityPlot[ad2]

ListDensityPlot[ad3]

ListDensityPlot[ad4]

ListDensityPlot[ad5]

Addition expressed in terms of a primitive element

Basic definitions

The following procedure calculates the orbit of k in the additive group modulus (2^n)-1

rndilg[k_, n_] := 
      Module[{twn, ls, fl, s}, 
twn = 2^n - 1; ls = {k}; 
        fl = True; 
s = k; 
While[
          fl, 
s = Mod[s  +  k, twn]; 
          fl = ! MemberQ[ls, s]; 
          If[fl, AppendTo[ls, 
              s]]
]; 
ls
]

Given i, the following procedure calculates the position of i in the orbit of k in the additive group modulus (2^n)-1, if i belongs indeed to this orbit. Otherwise, it returns the empty list.

rdl[i_, k_, n_] := 
      Module[{twn, d, rd, nt, t, i0, i1, i2}, 
twn = 
          2^n - 1; d = GCD[k, twn]; 
        rd = Mod[i, d]; 
If[
          rd == 0, 
nt = Floor[twn/k]; 
          t = k/d; 
i0 = i/d; i1 = Mod[i0, t]; 
          i2 = (i0 - i1)/t; 
i1 nt +  i2 + 
            If[i1 == 0, 0, 
              1]
, {}]
]

The addition of two elements is

adgen[i_, j_, k_, n_] := 
      Module[{i1, j1, l}, 
{i1, j1} = {i, j}; 
        If[i1 > j1, {i1, j1} = {j, i}]; 
If[i1 == 0, 
          j1, If[i1 == j1, 
            0, 
l = 
              rdl[j1 - i1, k, n]; 
Mod[n l  +  i1 - 1,  
                2^n - 1] + 1]]
]

And the whole table calculation is

gfprad[k_, n_] := 
      Module[{twn}, 
twn = 
          2^n - 1; 
Table[
          adgen[i, j, k, n], {i, 0, twn}, {j, 0, 
            twn}]
]

Examples

wb2 = {{0, 1, 2, 3}, {1, 0, 3, 2}, {2, 3, 0, 1}, {3, 2, 1, 
            0}};
wb3 = {{0, 1, 2, 3, 4, 5, 6, 7}, {1, 0, 4, 7, 3, 6, 2, 5}, {2, 4, 0, 
            5, 1, 4, 7, 3}, {3, 7, 5, 0, 6, 2, 5, 1}, {4, 3, 1, 6, 0, 7, 3, 
            6}, {5, 6, 4, 2, 7, 0, 1, 4}, {6, 2, 7, 5, 3, 1, 0, 2}, {7, 5, 3, 
            1, 6, 4, 2, 0}};
wb4 = {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 0, 
            5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12}, {2, 5, 0, 6, 10, 
            14, 3, 7, 11, 15, 4, 8, 12, 1, 5, 9}, {3, 9, 6, 0, 7, 11, 15, 4, 
            8, 12, 1, 5, 9, 13, 2, 6}, {4, 13, 10, 7, 0, 8, 12, 1, 5, 9, 13, 
            2, 6, 10, 14, 3}, {5, 2, 14, 11, 8, 0, 9, 13, 2, 6, 10, 14, 3, 7, 
            11, 15}, {6, 6, 3, 15, 12, 9, 0, 10, 14, 3, 7, 11, 15, 4, 8, 
            12}, {7, 10, 7, 4, 1, 13, 10, 0, 11, 15, 4, 8, 12, 1, 5, 9}, {8, 
            14, 11, 8, 5, 2, 14, 11, 0, 12, 1, 5, 9, 13, 2, 6}, {9, 3, 15, 
            12, 9, 6, 3, 15, 12, 0, 13, 2, 6, 10, 14, 3}, {10, 7, 4, 1, 13, 
            10, 7, 4, 1, 13, 0, 14, 3, 7, 11, 15}, {11, 11, 8, 5, 2, 14, 11, 
            8, 5, 2, 14, 0, 15, 4, 8, 12}, {12, 15, 12, 9, 6, 3, 15, 12, 9, 
            6, 3, 15, 0, 1, 5, 9}, {13, 4, 1, 13, 10, 7, 4, 1, 13, 10, 7, 4, 
            1, 0, 2, 6}, {14, 8, 5, 2, 14, 11, 8, 5, 2, 14, 11, 8, 5, 2, 0, 
            3}, {15, 12, 9, 6, 3, 15, 12, 9, 6, 3, 15, 12, 9, 6, 3, 
            0}};
wb5 = {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 
            18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}, {1, 0, 
            19, 6, 24, 11, 29, 16, 3, 21, 8, 26, 13, 31, 18, 5, 23, 10, 28, 
            15, 2, 20, 7, 25, 12, 30, 17, 4, 22, 9, 27, 14}, {2, 19, 0, 20, 
            7, 25, 12, 30, 17, 4, 22, 9, 27, 14, 1, 19, 6, 24, 11, 29, 16, 3, 
            21, 8, 26, 13, 31, 18, 5, 23, 10, 28}, {3, 6, 20, 0, 21, 8, 26, 
            13, 31, 18, 5, 23, 10, 28, 15, 2, 20, 7, 25, 12, 30, 17, 4, 22, 
            9, 27, 14, 1, 19, 6, 24, 11}, {4, 24, 7, 21, 0, 22, 9, 27, 14, 1, 
            19, 6, 24, 11, 29, 16, 3, 21, 8, 26, 13, 31, 18, 5, 23, 10, 28, 
            15, 2, 20, 7, 25}, {5, 11, 25, 8, 22, 0, 23, 10, 28, 15, 2, 20, 
            7, 25, 12, 30, 17, 4, 22, 9, 27, 14, 1, 19, 6, 24, 11, 29, 16, 3, 
            21, 8}, {6, 29, 12, 26, 9, 23, 0, 24, 11, 29, 16, 3, 21, 8, 26, 
            13, 31, 18, 5, 23, 10, 28, 15, 2, 20, 7, 25, 12, 30, 17, 4, 
            22}, {7, 16, 30, 13, 27, 10, 24, 0, 25, 12, 30, 17, 4, 22, 9, 27, 
            14, 1, 19, 6, 24, 11, 29, 16, 3, 21, 8, 26, 13, 31, 18, 5}, {8, 
            3, 17, 31, 14, 28, 11, 25, 0, 26, 13, 31, 18, 5, 23, 10, 28, 15, 
            2, 20, 7, 25, 12, 30, 17, 4, 22, 9, 27, 14, 1, 19}, {9, 21, 4, 
            18, 1, 15, 29, 12, 26, 0, 27, 14, 1, 19, 6, 24, 11, 29, 16, 3, 
            21, 8, 26, 13, 31, 18, 5, 23, 10, 28, 15, 2}, {10, 8, 22, 5, 19, 
            2, 16, 30, 13, 27, 0, 28, 15, 2, 20, 7, 25, 12, 30, 17, 4, 22, 9, 
            27, 14, 1, 19, 6, 24, 11, 29, 16}, {11, 26, 9, 23, 6, 20, 3, 17, 
            31, 14, 28, 0, 29, 16, 3, 21, 8, 26, 13, 31, 18, 5, 23, 10, 28, 
            15, 2, 20, 7, 25, 12, 30}, {12, 13, 27, 10, 24, 7, 21, 4, 18, 1, 
            15, 29, 0, 30, 17, 4, 22, 9, 27, 14, 1, 19, 6, 24, 11, 29, 16, 3, 
            21, 8, 26, 13}, {13, 31, 14, 28, 11, 25, 8, 22, 5, 19, 2, 16, 30, 
            0, 31, 18, 5, 23, 10, 28, 15, 2, 20, 7, 25, 12, 30, 17, 4, 22, 9, 
            27}, {14, 18, 1, 15, 29, 12, 26, 9, 23, 6, 20, 3, 17, 31, 0, 1, 
            19, 6, 24, 11, 29, 16, 3, 21, 8, 26, 13, 31, 18, 5, 23, 10}, {15, 
            5, 19, 2, 16, 30, 13, 27, 10, 24, 7, 21, 4, 18, 1, 0, 2, 20, 7, 
            25, 12, 30, 17, 4, 22, 9, 27, 14, 1, 19, 6, 24}, {16, 23, 6, 20, 
            3, 17, 31, 14, 28, 11, 25, 8, 22, 5, 19, 2, 0, 3, 21, 8, 26, 13, 
            31, 18, 5, 23, 10, 28, 15, 2, 20, 7}, {17, 10, 24, 7, 21, 4, 18, 
            1, 15, 29, 12, 26, 9, 23, 6, 20, 3, 0, 4, 22, 9, 27, 14, 1, 19, 
            6, 24, 11, 29, 16, 3, 21}, {18, 28, 11, 25, 8, 22, 5, 19, 2, 16, 
            30, 13, 27, 10, 24, 7, 21, 4, 0, 5, 23, 10, 28, 15, 2, 20, 7, 25, 
            12, 30, 17, 4}, {19, 15, 29, 12, 26, 9, 23, 6, 20, 3, 17, 31, 14, 
            28, 11, 25, 8, 22, 5, 0, 6, 24, 11, 29, 16, 3, 21, 8, 26, 13, 31, 
            18}, {20, 2, 16, 30, 13, 27, 10, 24, 7, 21, 4, 18, 1, 15, 29, 12, 
            26, 9, 23, 6, 0, 7, 25, 12, 30, 17, 4, 22, 9, 27, 14, 1}, {21, 
            20, 3, 17, 31, 14, 28, 11, 25, 8, 22, 5, 19, 2, 16, 30, 13, 27, 
            10, 24, 7, 0, 8, 26, 13, 31, 18, 5, 23, 10, 28, 15}, {22, 7, 21, 
            4, 18, 1, 15, 29, 12, 26, 9, 23, 6, 20, 3, 17, 31, 14, 28, 11, 
            25, 8, 0, 9, 27, 14, 1, 19, 6, 24, 11, 29}, {23, 25, 8, 22, 5, 
            19, 2, 16, 30, 13, 27, 10, 24, 7, 21, 4, 18, 1, 15, 29, 12, 26, 
            9, 0, 10, 28, 15, 2, 20, 7, 25, 12}, {24, 12, 26, 9, 23, 6, 20, 
            3, 17, 31, 14, 28, 11, 25, 8, 22, 5, 19, 2, 16, 30, 13, 27, 10, 
            0, 11, 29, 16, 3, 21, 8, 26}, {25, 30, 13, 27, 10, 24, 7, 21, 4, 
            18, 1, 15, 29, 12, 26, 9, 23, 6, 20, 3, 17, 31, 14, 28, 11, 0, 
            12, 30, 17, 4, 22, 9}, {26, 17, 31, 14, 28, 11, 25, 8, 22, 5, 19, 
            2, 16, 30, 13, 27, 10, 24, 7, 21, 4, 18, 1, 15, 29, 12, 0, 13, 
            31, 18, 5, 23}, {27, 4, 18, 1, 15, 29, 12, 26, 9, 23, 6, 20, 3, 
            17, 31, 14, 28, 11, 25, 8, 22, 5, 19, 2, 16, 30, 13, 0, 14, 1, 
            19, 6}, {28, 22, 5, 19, 2, 16, 30, 13, 27, 10, 24, 7, 21, 4, 18, 
            1, 15, 29, 12, 26, 9, 23, 6, 20, 3, 17, 31, 14, 0, 15, 2, 
            20}, {29, 9, 23, 6, 20, 3, 17, 31, 14, 28, 11, 25, 8, 22, 5, 19, 
            2, 16, 30, 13, 27, 10, 24, 7, 21, 4, 18, 1, 15, 0, 16, 3}, {30, 
            27, 10, 24, 7, 21, 4, 18, 1, 15, 29, 12, 26, 9, 23, 6, 20, 3, 17, 
            31, 14, 28, 11, 25, 8, 22, 5, 19, 2, 16, 0, 17}, {31, 14, 28, 11, 
            25, 8, 22, 5, 19, 2, 16, 30, 13, 27, 10, 24, 7, 21, 4, 18, 1, 15, 
            29, 12, 26, 9, 23, 6, 20, 3, 17, 0}};

Graphically,

ListDensityPlot[wb2]

ListDensityPlot[wb3]

ListDensityPlot[wb4]

ListDensityPlot[wb5]