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: 5.4 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: 2.8 seconds.
What's Coming in Future?
Primpoly Version 12.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.cygwin.bin Primpoly.exe.vcpp.bin | Executables for Mac OS X Yosemite 10.10.5/XCode 6.2 and Windows 7 64 bit/Cygwin (64-bit). |
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 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 Yosemite 10.10.2/XCode 6.2 and Windows XP SP3 (Cygwin, 64-bit). |
The source builds on both Mac and Windows platforms.
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.
On Windows platforms, I use the GNU Cygwin toolset for command line compiling and debugging. I also use Microsoft Visual Studio. For online C++ language tutorials, books and references, see links to C++ documentation.
Copyright © 1986-2015 by Sean Erik O'Connor. All Rights Reserved. last updated 03 Nov 15.