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 12.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2015 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: 7.9 seconds on my MacBook Pro (17-inch, Early 2009).

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: 4.2 seconds.

Interestingly, the running times almost doubled going from Snow Leopard Mac OS X 10.6 to Yosemite Mac OS X 10.10.

Features

What's Coming in Future?

RunningTimeVsDegree.png

Running time on MacBookPro

Download

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

Click on the Compact disk icon for source code download. to view and download.
Compact disk icon for source code download. Primpoly.cpp Main program.
Compact disk icon for source code download. Primpoly.h Header file containing parameters and constants.
Compact disk icon for source code download. ppArith.cpp Modulo p integer arithmetic.
Compact disk icon for source code download. ppArith.h Modulo p integer arithmetic class.
Compact disk icon for source code download. ppFactor.cpp Factoring into primes and primality testing.
Compact disk icon for source code download. ppFactor.h Factoring into primes and primality testing class.
Compact disk icon for source code download. ppOperationCount.cpp OperationCount collection.
Compact disk icon for source code download. ppOperationCount.h OperationCount class.
Compact disk icon for source code download. 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.
Compact disk icon for source code download. ppParser.h Polynomial I/O.
Compact disk icon for source code download. ppPolynomial.cpp Polynomial arithmetic.
Compact disk icon for source code download. ppPolynomial.h Polynomial arithmetic class.
Compact disk icon for source code download. ppBigInt.cpp Multiple precision integer arithmetic for non-negative numbers.
Compact disk icon for source code download. ppBigInt.h Multiple precision integer arithmetic class.
Compact disk icon for source code download. ppUnitTest.cpp Unit test function for all the classes and their member functions. Runs always and prints to a log file.
Compact disk icon for source code download. ppUnitTest.h Unit test function.
Compact disk icon for source code download. makefile Makefile for Macs, Unix systems and Windows systems running Cygwin.
Compact disk icon for source code download. knownGood.txt Known good test results for automated unit test in makefile
Compact disk icon for source code download. Primpoly.exe.mac.bin Primpoly.exe.cygwin.bin Primpoly.exe.vcpp.bin Executables for Mac OS X Yosemite 10.10.2/XCode 6.2 and Windows 7 64 bit/Cygwin (64-bit).

Download C Version

Primpoly Version 12.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.

Click on the Compact disk icon for source code download. to view and download
Compact disk icon for source code download. Primpoly.c This is the main program.
Compact disk icon for source code download. Primpoly.h This is the header file containing parameters and constants.
Compact disk icon for source code download. ppHelperFunc.c High level helper functions.
Compact disk icon for source code download. ppArith.c Modulo p integer arithmetic, primitive root testing.
Compact disk icon for source code download. ppFactor.c Factoring into primes and primality testing.
Compact disk icon for source code download. ppIO.c Polynomial I/O.
Compact disk icon for source code download. ppPolyArith.c Polynomial arithmetic.
Compact disk icon for source code download. ppOrder.c Polynomial order testing.
Compact disk icon for source code download. makefile Makefile for Macs, Unix systems and Windows systems running Cygwin.
Compact disk icon for source code download. knownGoodC.txt Known good test results for automated unit test in makefile
Compact disk icon for source code download. PrimpolyC.exe.mac.bin PrimpolyC.exe.cygwin.bin Executables for Mac OS X Yosemite 10.10.2/XCode 6.2 and Windows XP SP3 (Cygwin, 64-bit).

Install and Run

The source builds on both Mac and Windows platforms.

Apple Mac Development Environment

On Mac OS X, I use the built-in clang compiler and debugger. Mostly I build using make.

But I use the Xcode IDE for debugging, analyzing the code for dead code and uninitialized values, etc., and for profiling the code.

Windows Development System.

On Windows platforms, I use the GNU Cygwin toolset for command line compiling and debugging.

I also use Microsoft Visual C++ 2008 For online C++ language tutorials, books and references, see links to C++ documentation.

Uses for Primitive Polynomials:

Acknowledgements


Copyright © 1986-2015 by Sean Erik O'Connor. All Rights Reserved.     last updated 04 Mar 15.