• Home
  • Programming

Record and Reverie

General things I find interesting

Feed on
Posts
Comments
« The Appearance of Truth
Using Netflix DVDs to Measure The Post Office Decline »

GF(5^2)

Aug 17th, 2021 by Graham Booker

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.

Posted in General

Comments are closed.

  • Recent Posts

    • GF(5^2)
    • The Appearance of Truth
  • Archives

    2022
    April 2022 (1)
    2021
    May 2021 (1)August 2021 (1)
    2020
    March 2020 (1)
    2019
    November 2019 (1)
    2018
    June 2018 (1)July 2018 (1)December 2018 (1)
    2017
    January 2017 (2)June 2017 (1)August 2017 (1)
    2016
    June 2016 (1)August 2016 (1)
    2015
    January 2015 (1)February 2015 (1)December 2015 (1)
    2014
    June 2014 (1)July 2014 (1)August 2014 (2)
    2013
    February 2013 (2)March 2013 (1)April 2013 (1)June 2013 (1)November 2013 (1)
    2012
    April 2012 (2)May 2012 (1)June 2012 (1)November 2012 (1)
    2011
    January 2011 (1)October 2011 (1)November 2011 (1)December 2011 (1)
    2010
    February 2010 (2)April 2010 (1)June 2010 (1)July 2010 (1)August 2010 (1)September 2010 (1)October 2010 (2)December 2010 (3)
    2009
    January 2009 (1)February 2009 (1)March 2009 (2)May 2009 (1)July 2009 (3)September 2009 (1)
    2008
    January 2008 (1)February 2008 (4)March 2008 (1)April 2008 (6)May 2008 (1)June 2008 (3)August 2008 (1)September 2008 (2)October 2008 (2)December 2008 (1)
    2007
    January 2007 (1)February 2007 (4)March 2007 (5)April 2007 (4)May 2007 (1)June 2007 (6)August 2007 (3)September 2007 (3)November 2007 (3)December 2007 (4)
    2006
    January 2006 (4)February 2006 (10)March 2006 (4)April 2006 (6)May 2006 (2)June 2006 (4)July 2006 (1)August 2006 (1)September 2006 (4)October 2006 (6)November 2006 (3)December 2006 (3)
    2005
    October 2005 (6)November 2005 (13)December 2005 (1)
    2004
    February 2004 (2)March 2004 (1)April 2004 (1)May 2004 (6)June 2004 (6)July 2004 (3)August 2004 (2)September 2004 (1)November 2004 (5)
    2003
    September 2003 (1)October 2003 (3)November 2003 (1)December 2003 (1)
  • Categories

    • Breakaway (5)
    • Family (4)
    • Friends (2)
    • General (151)
    • Nature Pictures (8)
    • Politics (2)
    • Programming (41)
    • School (11)
    • SysAdmin (8)
    • Teaching (2)
  • Tags

    AC3 Ads Code Frontrow Java Objective-C Open Source Perian Perl permissions plex plugin RSS Sapphire School Servers ZFS

  • Pages

    • Programming
      • Fire Development
      • Kyocera Ringtone Converter for the Mac
      • Perian
      • Text Compression

Record and Reverie © 2022 All Rights Reserved.

WordPress Themes | Web Hosting Bluebook