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 also test a given polynomial for primitivity and find all primitive polynomials.

A sample run from the command line:

$ Primpoly 2 200

Primpoly Version 11.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2013 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: 5.3 seconds on my MacBook Pro.

Features

Finds primitive polynomials modulo p of degree n. No limit on n, but the program will start to slow for high degree due to the difficulty of factoring (pⁿ-1)/(p-1). The prime modulus p < 2^{m/2 - 1} where m = number of bits in the computer's integer type (defined in Primpoly.h). On most machines this will be 64 bits: p < 2147483648. For 32 bit systems, p < 32768.
Fast, clean implementation of the method of Alanen and Knuth with enhancements due to Sugimoto.

Running time vs degree for modulo 2

MacBookPro 2.4GHz Intel Core 2 Duo 2GB 667MHz DDR2 SDRAM.
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.

What's Coming in Future?

Use of tables of factored integers to speed up the algorithm.

Better random number generator for primality testing.

Download

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

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.
ppOperationCount.cpp	OperationCount collection.
ppOperationCount.h	OperationCount 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.
ppBigInt.cpp	Multiple precision integer arithmetic for non-negative numbers.
ppBigInt.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.
ppUnitTest.h	Unit test function.
makefile	Makefile for Macs, Unix systems and Windows systems running Cygwin.
knownGood.txt	Known good test results for automated unit test in makefile
Primpoly.exe.mac.bin Primpoly.exe.vcpp.bin	Executables for Mac OS X 10.6/XCode 4 and Windows 7 32 bit/Visual C++ 2008.

Download C Version

Primpoly Version 11.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.28 sec for the C++ version above and 0.18 sec for the C version. For p=2 and n=30, the C++ version takes 0.128 sec but the C version clock in at 0.027 sec.

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 Macs, Unix systems and Windows systems running Cygwin.
knownGoodC.txt	Known good test results for automated unit test in makefile
PrimpolyC.exe.mac.bin PrimpolyC.exe.cygwin.bin	Executables for Mac OS X 10.6 and Windows XP SP3 (Cygwin, 32-bit).

Install and Run

On Mac OS X, I use the built-in gcc compiler and gdb debugger and also Xcode IDE; on Windows platforms, I use the GNU Cygwin toolset for command line compiling and debugging. But the optimizing compiler of Microsoft Visual C++ 2008 generates a runtime executable running faster than the Cygwin (comperable in speed to Mac OS X/gcc). For online C++ language tutorials, books and references, see links to C++ documentation.

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.
And finally, thanks to Eric W. Weisstein's World of Mathematics for referencing this web page under primitive polynomials.

Home