COMPUTING PRIMITIVE POLYNOMIALS


Overview

We present C++ software for a program which generates a primitive polynomial of degree n modulo p. You can also test a given polynomial for primitivity and find all primitive polynomials.

A sample run from the command line:

$ Primpoly 2 200

Primpoly Version 16.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2020 by Sean Erik O'Connor. All Rights Reserved. Primpoly comes with ABSOLUTELY NO WARRANTY; for details see the GNU General Public License. This is free software, and you are welcome to redistribute it under certain conditions; see the GNU General Public License for details.

Primitive polynomial modulo 2 of degree 200

Self-check passes...

x ^ 200 + x ^ 5 + x ^ 3 + x ^ 2 + 1, 2

Total time: 4.7 seconds on my MacBook Pro.

Now we try a prime modulus p > 2,

Primpoly 337 10

Primitive polynomial modulo 337 of degree 10

x ^ 10 + x + 10, 337

Total time: 20.8 seconds.

Features

  • Finds primitive polynomials modulo p of degree n.
  • The prime modulus p < 2147483648 for 64-bit machines; p < 32768 for 32-bit machines. In general, p < 2m/2 - 1 where m = number of bits in the computer's integer type (defined in Primpoly.h).
  • No limit on n, but the program will start to slow for high degree due to the difficulty of factoring large numbers (pn-1)/(p-1) when not using factor tables. Factor tables are available for p = 2, 3, 5, 7, 11, courtesy of Tim's Cunningham Numbers
  • Fast, clean implementation of the method of Alanen and Knuth with enhancements due to Sugimoto.
  • Please read the user manual which describes all the command line settings, points out some limits in the algorithm and has a detailed example of how to debug the source code.
  • Detailed technical memo explaining the theory behind the algorithms.
RunningTimeVsDegree.jpg
Running time on MacBookPro

Download

Primpoly Version 16.0 Source code and executables are distributed under the terms of the GNU General Public License.

Primpoly.cpp Main program. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
Primpoly.h Header file containing parameters and constants. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppArith.cpp Modulo p integer arithmetic. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppArith.h Modulo p integer arithmetic class. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppFactor.cpp Factoring into primes and primality testing. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppFactor.h Factoring into primes and primality testing class. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppOperationCount.cpp OperationCount collection. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppOperationCount.h OperationCount class. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppParser.cpp Polynomial I/O and factor table I/O. I took the liberty of using my own LALR(1) parser generator for the polynomial input parser and the factor table parser. Here is the polynomial grammar and its LALR(1) parse tables. And here is the factor table grammar and the factor table parse tables The C++ LR parser isn't hard to implement using STL vectors and the automatically generated parse tables above. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppParser.h Classes for the parser. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppPolynomial.cpp Polynomial arithmetic. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppPolynomial.h Polynomial arithmetic class. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppBigInt.cpp Multiple precision integer arithmetic for non-negative numbers. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppBigInt.h Multiple precision integer arithmetic class. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppUnitTest.cpp Unit test for doing a self-check every time we run. Prints to a log file. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppUnitTest.h Unit test class. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
makefile Makefile for Macs, Ubuntu Linux, and Windows/Cygwin. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
knownGood.txt Known good test results for automated unit test in makefile. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
Primpoly.exe.mac.bin Executable for macOS Catalina 10.15.4 You'll need to download the prime factorization tables below and put them in the same directory as the executable. Compact disk icon for source code download. Download
c02minus.txt Prime factorization tables for 2n-1. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
c03minus.txt Prime factorization tables for 3n-1. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
c05minus.txt Prime factorization tables for 5n-1. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
c07minus.txt Prime factorization tables for 7n-1. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
c11minus.txt Prime factorization tables for 11n-1. Eye icon for source code viewing. View     Compact disk icon for source code download. Download

Download C Version

Primpoly Version 16.0 Source code and executables are distributed under the terms of the GNU General Public License.

This C language version is faster but has limits on the size of p and n since it uses native integer arithmetic. See the user manual for more details. For p=2 we can go as high as n=62. On my MacBook Pro, the time for p=2 and n=62 is 0.38 sec for the C++ version above and 0.002 sec for the C version. For p=2 and n=30, the C++ version takes 0.17 sec but the C version clocks in at 0.02 sec.

Primpoly.c Main program. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
Primpoly.h Header file containing parameters and constants. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppHelperFunc.c High level helper functions. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppArith.c Integer arithmetic modulo p. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppFactor.c Factoring into primes and primality testing. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppIO.c Polynomial I/O. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppPolyArith.c Polynomial arithmetic. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppOrder.c Polynomial order testing. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
makefile Makefile for Macs, Ubuntu Linux and Windows/Cygwin. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
knownGoodC.txt Known good test results for automated unit test in makefile. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
PrimpolyC.exe.mac.bin Executable for macOS Catalina 10.15.4 Compact disk icon for source code download. Download

Install and Run

The source builds on Mac, Ubuntu Linux and Windows platforms.

Source Code Setup

First of all, after downloading the source files, strip off the prefix. For example, this download will give you the file Project_SourceCode_PrimpolyC_Primpoly.c. Strip off the prefix and rename the file to Primpoly.c Primpoly Download

Next, in order for the makefile to run properly, the directories must be organized in a certain way. For example, let's say the parent directory is /Users/seanoconnor/Desktop/Sean/WebSite/ Mathematics/AbstractAlgebra/PrimitivePolynomials/Project and that we are in it right now.

Let's look at what the subdirectories must be:

pwd /Users/seanoconnor/Desktop/Sean/WebSite/Mathematics/AbstractAlgebra/PrimitivePolynomials/Project ls Build Bin knownGoodC.txt BinC makefile knownGood.txt ls Build/Bin ls Build/BinC ls SourceCode Primpoly PrimpolyC ls SourceCode/Primpoly FactorTables ppArith.cpp ppFactor.h ppPolynomial.cpp Primpoly.cpp ppBigInt.h ppParser.cpp ppUnitTest.h ppArith.h ppOperationCount.cpp ppPolynomial.h Primpoly.h ppFactor.cpp ppParser.h ppBigInt.cpp ppOperationCount.h ppUnitTest.cpp ls SourceCode/Primpoly/FactorTables c02minus.txt c03minus.txt c05minus.txt c06minus.txt c07minus.txt c10minus.txt c11minus.txt c12minus.txt c02plus.txt c03plus.txt c05plus.txt c06plus.txt c07plus.txt c10plus.txt c11plus.txt c12plus.txt ls SourceCode/PrimpolyC Primpoly.c Primpoly.h ppArith.c ppFactor.c ppHelperFunc.c ppIO.c ppOrder.c ppPolyArith.c

You also need to put the hostname of your computer into the makefile so it can build under the correct operating system. For example, on my MacBook Pro running Ubuntu Linux (Bionic Beaver) here is my hostname,

hostname Gauss

So in the makefile, I need this entry which tells the build is for a Linux machine:

ifeq ($(HOSTNAME), Gauss) PLATFORM = linux endif

Factor Tables (Primpoly C++ Version Only)

You'll need to have the factor tables in the same directory as the executable or in a subdirectory.

cd ~/PrimitivePolynomials/Project/Build/Bin ls Primpoly.exe* c02minus.txt* c03minus.txt* c05minus.txt* c07minus.txt* c11minus.txt*

If you run the program and it can't find the factor tables, it will fail the self check and tell you what happened in the unitTest.log file.

cd .. Bin/Primpoly.exe 2 4 Primpoly Version 16.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2020 by Sean Erik O'Connor. All Rights Reserved. Primpoly comes with ABSOLUTELY NO WARRANTY; for details see the GNU General Public License. This is free software, and you are welcome to redistribute it under certain conditions; see the GNU General Public License for details. Top Level Error: [ Self-check failed! ] Dear User, Sorry you got an error message. Please email the author at seanerikoconnor!AT!gmail!DOT!com with !DOT! replaced by . and the !AT! replaced by @ Please send me all console output from this program. Attach the unitTest.log file which should be located in the current directory. However, if the self-check failed, there won't be a log file. Thanks for your help, Sean E. O'Connor tail unitTest.log TEST: isAlmostSurelyPrime on the 10000th prime number 104729 of ppuint type.........PASS! TEST: Factor table method used on unsigned int 3^20 - 1 = 3486784400 = 2^4 5^2 11^2 61 1181.........FAIL! caught FactorError: [ Missing the factor table for p = 3 named c03minus.txt Please copy it into the current directory /Users/seanoconnor/Desktop/Sean/WebSite/Mathematics/AbstractAlgebra/ PrimitivePolynomials/Project/Build which contains the executable! in file ../SourceCode/Primpoly/ppFactor.cpp at line 158 ] End unit testing... SORRY. One or more unit tests failed!

Source Level Debugging and Profiling

On Mac OS X, I use the Xcode IDE for debugging Apple Mac Development Environment and profiling Apple Mac Development Profiling

On Ubuntu Linux, I build with make and compile with clang and use the command line debugger lldb.

On Windows platforms, I use the GNU Cygwin toolset for command line compiling with g++ I use Microsoft Visual Studio. for debugging.

Windows Development System.

Uses for Primitive Polynomials:

  • Generating pseudonoise (PN) sequences for spread spectrum communications and chip fault testing.
  • Generating Sobol sequences for high dimensional numerical integration
  • Generating CRC and Hamming codes.
  • Generating Galois (finite) fields for use in implementing Reed-Solomon and BCH error correcting codes.

Acknowledgements

  • Thanks to Martin Becker for pointing out a bug when trying to do the primitive polynomial search on p = 65003, n = 2 where the multiple precision arithmetic base is exceeded and also for pointing out a bug in computing Euler Phi for the number of polynomials when p > 2.
  • Thanks to K. Jambunathan of the Indian Statistical Institute, Calcutta, India for first suggesting that I increase the numeric precision of the calculations, allowing higher degree polynomials to be generated.
  • Thanks to Ted Ford of Hampshire, Britain for extending the program to print all primitive polynomials, for suggesting I replace the stored table of primitive roots with an algorithmic test, and many interesting observations on maximal length sequences.
  • Thanks to Alan Meghrigian for suggesting valuable corrections to the notes.
  • Thanks to John McKay for mentioning Conway polynomials which are a special class of primitive polynomial used to represent finite fields.
  • Thanks to Sid Paral for pointing out bugs in array bounds checking in the polynomial parser.
  • Thanks to Subrata Nandi for pointing out that I need instructions on how to set up the source code in the proper directory organization to so that the makefile will build properly.
  • And finally, thanks to Eric W. Weisstein's World of Mathematics for referencing this web page under primitive polynomials.