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 13.0 - A Program for Computing Primitive Polynomials. Copyright (C) 1999-2016 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.5 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: 18.5 seconds.

Features

RunningTimeVsDegree.png
Running time on MacBookPro

Download

Primpoly Version 13.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 function for all the classes and their member functions. Runs always and prints to a log file. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
ppUnitTest.h Unit test function. Eye icon for source code viewing. View     Compact disk icon for source code download. Download
makefile Makefile for Macs, Unix systems and Windows systems running 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 Mac OS X El Capitan 10.11.3. Compact disk icon for source code download. Download
Primpoly.exe.cygwin.bin Executable for Windows 7 64 bit/Cygwin (64-bit). 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 13.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 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, Unix systems and Windows systems running 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 Mac OS X El Capitan 10.11.3. Compact disk icon for source code download. Download
PrimpolyC.exe.cygwin.bin Executable for Windows 7 64 bit/Cygwin (64-bit). Compact disk icon for source code download. Download

Install and Run

The source builds on both Mac and Windows platforms.

On Mac OS X, I build with clang and make. I use the Xcode IDE for debugging Apple Mac Development Environment and profiling Apple Mac Development Profiling

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

For online C++ language tutorials, books and references, see links to C++ documentation.

Windows Development System.

Uses for Primitive Polynomials:

Acknowledgements


Copyright © 1986-2016 by Sean Erik O'Connor. All Rights Reserved.     last updated 19 Nov 16.