# 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:

#### 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.1 - 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 and 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.

### 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 Tielin Liang for pointing out a mistake in one of my Lemmas in the theoretical section.
• Thanks to Majid Bakhtiari for pointing out that Mersenne primes are an important special case for which we can quickly find extremely high degree polynomials.
• 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.
• Thanks to Tony Freitas for pointing out two compile errors and how to fix them in Visual Studio 2017 (Microsoft Windows).
• Thanks to Martin Dowd for pointing out methods for finding all primitive polynomials given a single primitive polynomial.
• Thanks to Max-Julian Jakobitsch for pointing out MathJax rendering was broken and how to fix it.
• And finally, thanks to Eric W. Weisstein's World of Mathematics for referencing this web page under primitive polynomials.