Sin( x y ) Image Border.

COMPUTING PRIMITIVE POLYNOMIALS

Overview

We present C++ software for a program which generates a primitive polynomial of degree n modulo p. You can optionally find all primitive polynomials.

A sample run from the command line:

$ pp 13 10

Primpoly Version 5.3 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2008 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 13 of degree 10

x ^ 10 + 2 x ^ 2 + 2 x + 2

Features

Clean implementation of the method of Alanen and Knuth with enhancements due to Sugimoto.
A technical memo with a detailed discussion of the theory behind the algorithms used.
Fast algorithm: runs in under one second for finding a 60th degree polynomial modulo 2 on a slow 120MHz Pentium PC.

Download

The C++ version seems to be working now. I'm currently debugging it more thoroughly and optimizing it for speed. The C version below is stable.

Source code and executables are distributed under the terms of the GNU General Public License Current version is 8.0

I have an in-depth explanation of the software design of this program and the theory behind the algorithms used. See also the examples and test cases. to verify if the program is working correctly.

Click on the to view and download.
Primpoly.cpp	Main program.
Primpoly.h	Header file containing parameters and constants.
ppArith.cpp	Modulo p integer arithmetic.
ppArith.h	Modulo p integer arithmetic class.
ppFactor.cpp	Factoring into primes and primality testing.
ppFactor.h	Factoring into primes and primality testing class.
ppParser.cpp	Polynomial I/O. I took the liberty of using my own LALR(1) parser generator on a simple polynomial grammar to automatically generate the parser. Here is the grammar and its LALR(1) parse tables. The C++ LR parser isn't hard to implement using STL vectors and the automatically generated parse tables above.
ppParser.h	Polynomial I/O.
ppPolynomial.cpp	Polynomial arithmetic.
ppPolynomial.h	Polynomial arithmetic class.
BigInt.cpp	Multiple precision integer arithmetic.
BigInt.h	Multiple precision integer arithmetic class.
ppUnitTest.cpp	Unit test function for all the classes and their member functions. Runs always and prints to a log file.
makefile	Makefile for Unix systems and Windows systems running Cygwin.

Download C Version

It does have limits on the size of p and n since it uses integer arithmetic. See the documentation for more details. For p=2 we can go as high as n=62.

Source code and executables are distributed under the terms of the GNU General Public License Current version is 5.3

Click on the to view and download
Primpoly.c	This is the main program.
Primpoly.h	This is the header file containing parameters and constants.
ppHelperFunc.c	High level helper functions.
ppArith.c	Modulo p integer arithmetic, primitive root testing.
ppFactor.c	Factoring into primes and primality testing.
ppIO.c	Polynomial I/O.
ppPolyArith.c	Polynomial arithmetic.
ppOrder.c	Polynomial order testing.
makefile	Makefile for Unix systems and Windows systems running Cygwin.

Install and Run

On Mac OS X, I also use the Xcode IDE. On a Windows XP PC system, I use the GNU Cygwin toolset for command line compiling and debugging. On Unix systems, including Mac OS X, I use the built-in gcc compiler and gdb debugger. For details on the C++ language, see Bjarne Stroustrup's Page and C++ FAQ Lite and the Standard Template Library.

Uses for Primitive Polynomials:

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

Acknowledgements

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 recent work on Conway Polynomials which are a special class of primitive polynomial used to represent finite fields.
Thanks to Eric W. Weisstein's World of Mathematics for referencing this web page under primitive polynomials.

Home