I got curious about the design of a puzzle a few weeks back using \(GF(5)\), or more specifically, the extension field \(GF(5^2)\). I was hoping that I could find pre-computed examples and while I found many examples of lectures discussing \(GF(5)\), I didn’t find anything with extension fields of it. So I wrote a quick program to find primitive polynomials of degree 2 over \(GF(5)\). For what I had in mind I needed 6 primitive polynomials which could be selected for construction of this field but sadly that was not the case. Since I went through the work to find all possible polynomials and I didn’t find anyone else that had done so, I decided I’d make a blog post of them in case it’s useful to someone else.
The Field
While this may seem obvious, I’ll explicitly define what I used for \(GF(5)\). I chose the integers \([0, 4]\) with \(+\) and \(•\) being addition and multiplication \(\mod 5\). This makes \(0\) the additive identity and \(1\) the multiplicative identity. Basically, what you would expect one to use for \(GF(5)\).
In my search for primitive polynomials, I only searched polynomials with a coefficient of \(1\) for the \(x^2\) component. This is because every polynomial with a different non-zero coefficient is just a scalar multiple of one with a coefficient of \(1\).
The Reducible Polynomials
Every story must have rising action and so next comes the failures of the polynomials which couldn’t make the cut. In the heat of the battle, these were the cannon fodder. The reducible polynomials of degree 2 over \(GF(5)\).
- \(x^2 = x•x\)
- \(x^2+1 = (x+2)•(x+3)\)
- \(x^2+4 = (x+1)•(x+4)\)
- \(x^2+x = x(x+1)\)
- \(x^2+x+3 = (x+2)•(x+4)\)
- \(x^2+x+4 = (x+3)•(x+3)\)
- \(x^2+2x = x(x+2)\)
- \(x^2+2x+1 = (x+1)•(x+1)\)
- \(x^2+2x+2 = (x+3)•(x+4)\)
- \(x^2+3x = x(x+3)\)
- \(x^2+3x+1 = (x+4)•(x+4)\)
- \(x^2+3x+2 = (x+1)•(x+2)\)
- \(x^2+4x = x(x+4)\)
- \(x^2+4x+3 = (x+1)•(x+3)\)
- \(x^2+4x+4 = (x+2)•(x+2)\)
The Non-primitive Polynomials
Then these polynomials managed to pass the first test only to fail in another. An n-degree primitive polynomial over \(GF(p)\) must not divide \(x^m-1\) for any \(m<p^n-1\). In this case that means it must not divide \(x^m+4\) for any \(m<24\). So these polynomials fail that test; they got in a few licks before falling but ultimately didn’t make it.
- \(x^2+2\) divides \(x^m+4\) for \(m=8,16\)
- \(x^2+3\) divides \(x^m+4\) for \(m=8,16\)
- \(x^2+x+1\) divides \(x^m+4\) for \(m=3,6,9,12,15,18,21\)
- \(x^2+2x+4\) divides \(x^{12}+4\)
- \(x^2+3x+4\) divides \(x^{12}+4\)
- \(x^2+4x+1\) divides \(x^m+4\) for \(m=6,12,18\)
The Primitive Polynomials
Now we finally reach the victors, the primitive polynomials. There are 4 of these and for each I’ll list the powers of \(\alpha\) in vector notation starting with \(\alpha^0\)
- \(x^2+x+2\) or \(x^2=4x+3\)
- 01, 10, 43, 42, 32, 44, 02, 20, 31, 34, 14, 33, 04, 40, 12, 13, 23, 11, 03, 30, 24, 21, 41, 22
- \(x^2+2x+3\) or \(x^2=3x+2\)
- 01, 10, 32, 11, 42, 43, 03, 30, 41, 33, 21, 24, 04, 40, 23, 44, 13, 12, 02, 20, 14, 22, 34, 31
- \(x^2+3x+3\) or \(x^2=2x+2\)
- 01, 10, 22, 14, 12, 42, 03, 30, 11, 32, 31, 21, 04, 40, 33, 41, 43, 13, 02, 20, 44, 23, 24, 34
- \(x^2+4x+2\) or \(x^2=x+3\)
- 01, 10, 13, 43, 22, 41, 02, 20, 21, 31, 44, 32, 04, 40, 42, 12, 33, 14, 03, 30, 34, 24, 11, 23
And those are the primitive polynomials to construct \(GF(5^2)\). Hope you had as much fun going through these results as I did finding them.