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-2018 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.
Primpoly Version 13.0 Source code and executables are distributed under the terms of the GNU General Public License.
Primpoly.cpp | Main program. | View Download |
Primpoly.h | Header file containing parameters and constants. | View Download |
ppArith.cpp | Modulo p integer arithmetic. | View Download |
ppArith.h | Modulo p integer arithmetic class. | View Download |
ppFactor.cpp | Factoring into primes and primality testing. | View Download |
ppFactor.h | Factoring into primes and primality testing class. | View Download |
ppOperationCount.cpp | OperationCount collection. | View Download |
ppOperationCount.h | OperationCount class. | View 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. | View Download |
ppParser.h | Classes for the parser. | View Download |
ppPolynomial.cpp | Polynomial arithmetic. | View Download |
ppPolynomial.h | Polynomial arithmetic class. | View Download |
ppBigInt.cpp | Multiple precision integer arithmetic for non-negative numbers. | View Download |
ppBigInt.h | Multiple precision integer arithmetic class. | View Download |
ppUnitTest.cpp | Unit test function for all the classes and their member functions. Runs always and prints to a log file. | View Download |
ppUnitTest.h | Unit test function. | View Download |
makefile | Makefile for Macs, Ubuntu Linux, and Windows/Cygwin. | View Download |
knownGood.txt | Known good test results for automated unit test in makefile. | View Download |
Primpoly.exe.mac.bin | Executable for Mac OS X El Capitan 10.11.3. | Download |
Primpoly.exe.cygwin.bin | Executable for Windows 7 64 bit/Cygwin (64-bit). | Download |
c02minus.txt | Prime factorization tables for 2^{n}-1. | View Download |
c03minus.txt | Prime factorization tables for 3^{n}-1. | View Download |
c05minus.txt | Prime factorization tables for 5^{n}-1. | View Download |
c07minus.txt | Prime factorization tables for 7^{n}-1. | View Download |
c11minus.txt | Prime factorization tables for 11^{n}-1. | View Download |
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. | View Download |
Primpoly.h | Header file containing parameters and constants. | View Download |
ppHelperFunc.c | High level helper functions. | View Download |
ppArith.c | Factoring into primes and primality testing. | View Download |
ppIO.c | Polynomial I/O. | View Download |
ppPolyArith.c | Polynomial arithmetic. | View Download |
ppOrder.c | Polynomial order testing. | View Download |
makefile | Makefile for Macs, Ubuntu Linux and Windows/Cygwin. | View Download |
knownGoodC.txt | Known good test results for automated unit test in makefile. | View Download |
PrimpolyC.exe.mac.bin | Executable for Mac OS X El Capitan 10.11.3. | Download |
PrimpolyC.exe.cygwin.bin | Executable for Windows 7 64 bit/Cygwin (64-bit). | Download |
The source builds on Mac, Ubuntu Linux and Windows platforms.
On Mac OS X, I build with make and compile with clang. I use the Xcode IDE for debugging and profiling
On Ubuntu Linux, I build with make and compile with clang.
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.
Copyright © 1986-2018 by Sean Erik O'Connor. All Rights Reserved. last updated 18 Feb 18.