GF(2ⁿ) (a Galois Field using 2ⁿ elements) is useful for computer data. It defines + and * and /, so you can do things like Gaussian elimination, but instead of being defined on all integers or a field with a prime number of elements, GF(2⁸) is defined on 2⁸=256 elements, so you can conveniently represent any byte value as one element in GF(2⁸). GF(2ⁿ) defines "+" as XOR, rather than the normal integer addition. "*" and "/" are not the normal integer times and divide, they have even stranger definitions than "+".

When working with GF(2ⁿ), you need to have primitive polynomials before you can do anything. For example, in GF(2⁴), there are two primitive polynomials: 19 and 25 (in hex, 0x13 and 0x19, or in binary, 10011 and 11001). For example, if you are using 0x13 (binary 10011, low bits on the right) as the primitive polynomial, repeatedly multiplying by 2 gives you:

        0001 = 0x1 = 2^^0 mod 0x13
        0010 = 0x2 = 2^^1 mod 0x13
        0100 = 0x4 = 2^^2 mod 0x13
        1000 = 0x8 = 2^^3 mod 0x13
        0011 = 0x3 = 2^^4 mod 0x13
        0110 = 0x6 = 2^^5 mod 0x13
        1100 = 0xc = 2^^6 mod 0x13
        1011 = 0xb = 2^^7 mod 0x13
        0101 = 0x5 = 2^^8 mod 0x13
        1010 = 0xa = 2^^9 mod 0x13
        0111 = 0x7 = 2^^10 mod 0x13
        1110 = 0xe = 2^^11 mod 0x13
        1111 = 0xf = 2^^12 mod 0x13
        1101 = 0xd = 2^^13 mod 0x13
        1001 = 0x9 = 2^^14 mod 0x13
        0001 = 0x1 = 2^^15 mod 0x13 = 2^^0 mod 0x13
  

This defines a logarithm base 2, for example 3 is 0011 is 2⁴. So 3x3 = 2⁴⁺⁴ = 2⁸ = 0101 is 5. You can also do that bitwise: 3 is 2+1, (2 xor 1)x(2 xor 1) = 4 xor 2 xor 2 xor 1 = 4 xor 1 = 5. You can do inverses with multiplication with the logarithms too. Since x¹⁵ = 1 for all x in 1..15, and x is x¹, you know x¹*x¹⁴ = 1, so x¹⁴ is the inverse of x. If x is 2^m, 1/x is 2^15-m. Division, x/y, is x*(1/y). Alternatively, if multiplication is pow(log(x)+log(y)), then division is pow(log(x)-log(y)).

When working with GF(2ⁿ), you need to find a primitive polynomial before you can do much of anything else. I have a program that finds the first 16 primitive polynomials for each GF(2ⁿ) for n in 1..64, where 2 is a primitive root. I don't know if there are additional ones where 2 is not a primitive root.

Primitive polynomials are always 2ⁿ + stuff. This gives only the stuff. Remember to add the 2ⁿ.

n=1
1 
n=2
3 
n=3
3 5 
n=4
3 9 
n=5
5 9 f 17 1b 1d 
n=6
3 1b 21 27 2d 33 
n=7
3 9 f 11 1d 27 2b 39 3f 41 4b 53 55 65 6f 71 
n=8
1d 2b 2d 4d 5f 63 65 69 71 87 8d a9 c3 cf e7 f5 
n=9
11 1b 21 2d 33 59 5f 69 6f 77 7d 87 95 a3 a5 af 
n=10
9 1b 27 2d 65 6f 81 8b c5 d7 e7 f3 ff 10d 119 123 
n=11
5 17 2b 2d 47 63 65 71 7b 8d 95 9f a9 b1 cf d1 
n=12
53 69 7b 7d 99 d1 eb 107 11f 123 13b 14f 157 161 16b 185 
n=13
1b 27 35 53 65 6f 8b 8d 9f a5 af bb bd c3 c9 e1 
n=14
2b 39 53 5f 7b a9 af bb bd cf eb f3 10d 113 13b 143 
n=15
3 11 17 2d 35 5f 77 81 87 93 a5 c3 cf dd e7 f5 
n=16
2d 39 3f 53 bd d7 12f 13d 14f 15d 197 1a1 1ad 1bf 1c7 215 
n=17
9 f 21 2d 33 3f 41 55 69 7b 8d 99 a3 af bb c5 
n=18
27 3f 4d 7b 81 db e7 ed 107 14f 191 1e3 1e9 1ef 20b 213 
n=19
27 3f 47 53 59 63 6f 7d 93 af e1 143 161 16b 175 185 
n=20
9 53 65 69 7b f3 167 16d 17f 18f 1bf 223 229 231 2b9 333 
n=21
5 27 3f 65 6f 7b 7d 93 b7 107 11f 13b 149 14f 16d 173 
n=22
3 39 bd c3 129 161 173 18f 1b3 1f1 223 267 2ad 2b5 305 311 
n=23
21 2b 2d 33 3f 4d 65 77 87 8b 99 a3 bd c5 f3 f9 
n=24
1b 87 b1 db f5 125 17f 1b5 1cb 225 251 257 26d 363 369 3af 
n=25
9 f 2d 81 93 c5 ff 10d 13d 145 173 197 1a1 1ad 1b9 1d3 
n=26
47 4d b1 e1 f5 119 13b 16d 17f 183 189 1bf 1e3 213 23b 245 
n=27
27 d1 e7 eb 129 131 15d 16d 179 183 1e3 225 229 237 251 289 
n=28
9 53 77 e1 167 173 1df 201 223 2b3 2d9 321 339 359 371 3b1 
n=29
5 17 1d 8d c3 f9 119 13b 13d 173 189 191 1ab 1bf 207 215 
n=30
53 af bd 113 149 1d9 23d 291 29d 2c1 2e5 2f7 317 3cf 3d7 483 
n=31
9 f 2d 35 41 47 55 81 8b a9 bb ff 11f 12f 145 15d 
n=32
af c5 f5 125 173 175 20d 229 25b 29d 2d9 33f 34d 3e7 41f 599 
n=33
53 69 87 99 a3 dd ed f5 107 123 131 14f 16d 179 183 1c7 
n=34
e7 119 11f 175 18f 1b3 1d3 1e5 223 251 2bf 2e5 31d 347 38d 395 
n=35
5 5f 9f af 13d 16d 183 19d 1b9 1e3 1e5 207 245 24f 26b 279 
n=36
77 7b f9 16b 183 1ef 219 23b 267 283 2ad 2d3 2e3 321 371 3c5 
n=37
3f 53 71 b7 c9 d1 f5 13d 15d 189 1c7 1cd 1d3 1f1 207 219 
n=38
63 a3 d7 143 173 1ab 1f1 1f7 20d 2c7 309 333 365 369 41f 473 
n=39
11 93 dd 101 149 1c7 1e3 20b 20d 22f 243 25b 261 275 27f 29d 
n=40
39 d7 13b 13d 1a1 20b 251 34b 369 3bb 533 5c5 5e1 6dd 78f 79d 
n=41
9 f 1b 2d 47 8b 9f dd e7 119 11f 1c7 1e3 1fd 213 229 
n=42
3f 6f 77 99 a5 c9 157 22f 2f1 2fd 399 419 45b 4b5 539 699 
n=43
59 63 71 8d c3 185 1b3 1b9 1c1 1d3 1d5 1f1 1fb 23d 26b 2b5 
n=44
65 69 8d bb e1 eb 16d 173 19b 1b9 1d9 1e3 311 44f 46b 509 
n=45
1b 35 53 b7 db 11f 183 1b5 225 25b 267 28f 2ad 355 37b 3a9 
n=46
12f 16b 19d 1c1 20b 231 243 2b5 30f 321 36f 37b 3db 3dd 40d 443 
n=47
21 33 69 8b 99 bd d1 10b 13b 149 17f 189 1c7 1d9 237 2a1 
n=48
b7 17f 1a7 1e3 291 2c7 2cb 2d5 2fd 341 49b 4cb 51d 533 54b 587 
n=49
71 bb e7 13d 19b 1d5 201 20b 249 2cb 303 321 327 395 3a3 419 
n=50
1d 4d 71 f5 119 19d 1cb 229 245 25b 261 2b9 2c7 2cd 2fd 359 
n=51
4b 69 7d eb 16b 17f 185 1d9 1e3 2d5 2f1 3cf 431 44f 451 467 
n=52
9 4b 157 1e5 321 3b1 3ff 483 517 587 5cf 64d 65f 773 785 797 
n=53
47 71 8d 95 eb 137 145 151 18f 19d 1ab 1ef 215 279 32d 341 
n=54
7d bd 137 13b 149 14f 1c7 273 28f 333 339 34d 3eb 483 4ad 503 
n=55
47 bd 10d 119 13b 145 19d 1df 231 25b 27f 29b 2ef 31d 3f9 40b 
n=56
95 10d 19b 2c7 393 395 40d 49d 4f1 50f 57d 67b 69f 6c5 73d 7b3 
n=57
2d 81 14f 185 18f 1b9 22f 283 2a7 2fd 317 321 363 399 3af 3f9 
n=58
63 77 1ad 2a7 363 387 3d7 3f9 429 4b5 51d 547 58b 5af 61b 64b 
n=59
7b 95 c5 149 1b9 1d5 1ef 261 291 327 369 3a5 3bd 3eb 467 4c1 
n=60
3 35 243 273 2c1 309 3bd 485 527 5c9 655 7a1 801 993 9e7 a47 
n=61
27 3f 93 185 1bf 1c7 1df 25d 2b5 2fb 327 3ed 40d 42f 461 4d3 
n=62
69 af bb 19d 1b5 1c1 2a1 311 5db 605 64b 65f 6a9 6f3 749 779 
n=63
3 21 33 5f 6f 20b 22f 257 291 2ab 2c7 33f 3b1 419 479 4a1
n=64
1b 1d f5 175 1a1 1df 251 2cb 347 3c9 3cf 3f3 425 533 779 77f
  

You also need to be able to do multiplication modulo those primitive polynomials. Here's some public domain code for that, at least for GF(2³²). It precalculates the inverse of the primitive polynomial, well really 2²ⁿ/primitivePolynomial, then makes use of an x86 intrinsic carryless multiply instruction. 2²ⁿ/poly is used for multiplication ... for GF(2^19)..GF(2^64), for all primitive polynomials listed, 2²ⁿ/poly == poly. With g++ I needed -mpclmul and -msse4.1 in order to get it to compile.

#include <emmintrin.h>
#include <tmmintrin.h>
#define zSet(a,b) _mm_set_epi32(0,0,a,b)
#define zXor(a,b) _mm_xor_si128(a,b)
#define zMult(a,b) _mm_clmulepi64_si128(a,b,0)
#define zRight(a,s) _mm_srli_si128(a,s)
      
typedef  unsigned int  u4;  // 4 byte unsigned
static const int sc_bits = 32;

    u4 Mult(u4 x, u4 y) const
    {
        // calculate the full z=x*y, not mod anything
        __m128i poly = zSet(1,0xaf);
        __m128i invPoly = zSet(1,0xaf); // inv==poly often but not always
        __m128i xx = zSet(0,x);
        __m128i yy = zSet(0,y);
        __m128i zz = zMult(xx,yy);

        // Poly is 2^^n ^ (something small).
        // We want z mod poly.  So we want r in (q,r) where q*poly ^ r = z where r < 2^^n.
        // We precalculated invPoly = (2^^(2n))/poly, which isn't exact, there was a remainder.
        // Typically poly is 2^^n ^ (some small stuff) and invPoly is 2^^n ^ (other small stuff).
        //               (invPoly*poly) == 2^^(2n) + stuff, where stuff < 2^^n
        //           (invPoly*poly)>>2n == 1, since stuff>>2n == 0
        //         (z*invPoly*poly)>>2n == z, since stuff>>n == 0
        //         (z*invPoly*poly)>>2n == q*poly ^ r, where r < 2^^n
        //              (z*invPoly)>>2n == q  (Since poly > r, r/poly == 0.)
        //       ((z*invPoly)>>2n)*poly == q*poly
        //   z ^ ((z*invPoly)>>2n)*poly == r, which is z mod poly, since z ^ q*poly = r.
        // The implementation below is just that last line of algebra.
        __m128i zi = zMult(zz, invPoly);
        __m128i q = zRight(zi, 2*sc_bits/8);
        __m128i qp = zMult(q, poly);
        __m128i rsl = zXor(zz, qp);
        return  ((u4 *)&rsl)[0];
    }

1/x is 2^2n-2. You can calculate 2²ⁱ relatively quickly by squaring: 2 = 2¹, 4 = 2*2 = 2², 16 = 4*4 = 2⁴, et cetera. Given m, the bits set in m tell you which 2²ⁱ to multiply together to get 2^m. Given inverse, division (x/y) is x*(1/y). Inverse can also be done with a table of inverses for the 2ⁿ elements, but that takes too much computer memory beyond about n=24.

Large EC codes with m data blocks need to work on large GF(2ⁿ), where typically m > 2n. x/y computed by x*(1/y) where 1/y is y^2n-2 accomplishes a division in about the cost of 2n multiplications, which is less m. Computing coefficients for data recovery involves Gaussian elimination of m by m matrices with elements in GF(2ⁿ). These call for m divisions and around m³ multiplications. So the cost for Gaussian elimination will be around m³ multiplications (for the multiplications) plus around m² multiplications (for the divisions). Multiplications already dominate. So a faster division would be nice, but for the purpose of EC codes, doing x/y by x*(1/y) where 1/y is computed by y^2n-2 is good enough.

It may be faster to do inverse and division by using extension subfields, but I haven't understood how those work yet. Wikipedia and research articles and my old textbooks say it can be done, but I haven't followed what they are saying yet. Especially for GF(2²⁴) and bigger it would be important to have faster division, so that Gaussian elimination on large matrices of values from these fields can be done quickly. Here's what I've understood about that so far.

GF(2ⁿ) has that property that any nonzero element raised to the 2ⁿ-1 power is 1. If n is even, there is a subfield of size 2^n/2 consisting of the (2^n/2-1)th roots of 1, plus the element 0. These roots exist because 2ⁿ-1 = (2^n/2-1)(2^n/2+1). 2^2n/2+1 is one such root. Call that subfield (which is equivalent to GF(2^n/2)) F, and call the original GF(2ⁿ) G.

In the special case of G=GF(2⁴), that subfield F is {0, 2⁵, 2¹⁰, and 2¹⁵=1}. With polynomial 0x13 those are {0, 6, 7, 1}. With polynomial 0x19 those are {0, 7, 6, 1}. They are closed under XOR, but I don't know why, or if that is coincidence. They can be mapped to GF(2²). There is only one primitive polynomial for GF(2²), so I don't have to worry about which primitive polynomial to choose. I hear they are all isomorphic anyhow, so no matter which primitive polynomial you choose for GF(2^n/2) you can choose a mapping to F (whose elements are in GF(2ⁿ)) that will make it work.

Further, you can represent elements of G as vectors x XOR yu, where x and y come from F, and u is some element of G not in F. There may be further restrictions on u, but in the special case of GF(2⁴), every nonelement of F works. Why that would successfully map (x,y) from F to elements of G uniquely, I don't know. It may not work in general. But for GF(2⁴) it does indeed work. Given an element e of G, figuring out (x,y) from F such that x+yu=e, I don't know how to do that either.

And once I answer those questions, there's a claim that using inverse in F lets you find inverses in G: inv_G(e) is inv_F(x) XOR inv_F(y)*u. Or maybe inv_G(u). Or maybe some more complicated formula. I don't know why it would be true. I am probably not interpreting that claim correctly.

There are some special non-F elements of G: these are the (2^n/2+1)th roots of 1, an example of which is 2^2n/2-1. I don't know if they are important in any way.

Hash functions and block ciphers
A recipe for finding pentagons that tile the plane
Table of Contents