| A Primitive Polynomial Search Program | |
| Motivation | |
| I recently ran across Scott Nelson's primitive polynomial search program and was impressed because it was the first such program I have seen on the web that can easily produce tables more extensive than those found in textbooks. The algorithm is described in simple terms without advanced mathematics. I decided to try to optimize for more performance, because as good as it is, it falls short of the search results produced by Andreas Rieke. | |
| The Primitivity Test Algorithm | |
| I spent some time studying Scott Nelson's algorithm to understand it in the context finite field math. It appears that Scott's program uses the same basic algorithm as Andreas Rieke. The primitivity test consists of verifying that order of a primitive element is 2^n - 1. This is accomplished by confirming that when the primitive element is raised to the power 2^n - 1, modulo the primitive polynomial, the value one is produced. Here is an example of what that looks like. But that is not enough, if 2^n - 1 is not prime. The order of the primitive element candidate could have a prime factor in common with 2^n - 1. Additional tests are made to handle this situation. Here is an example of such a polynomial. Scott Nelson's modular polynomial exponentiation algorithm employs the common square and multiply algorithm. His polynomial modular multiply algorithm is a matrix method that can be found in textbooks. But it is inefficient, in part because memory usage is high. I kept the square and multiply approach, with some minor optimizations, but replaced the matrix modular multiply with a shift and XOR type. | |
| Performance | |
| The performance of the new program is
surprisingly good, and the results match those of Andreas Rieke exactly.
On a Pentium III 500,
these results were duplicated through degree 1023 in less than 2
hours. The program compares favorable to the online primitivity
test. For example, the new test confirms x^1047 + x^10 + 1 in about
4 seconds, while the online version takes longer.
The performance of the new test benefits greatly from the new Intel SIMD instructions, formerly known as KNI (Katmai New Instructions). The XOR routine for example, looks like this. The routine is completely inline. The shift left once code looks like this. |
|
| Building | |
| The program currently is running on
Microsoft Windows 2000. Other Windows versions probably work too. The
code assumes Intel Pentium III instruction set. Both Microsoft and Intel
compilers work. See the source code for
details. For maximum performance, the math is coded for fixed length
polynomials and several executables are built. Each of the n executables
handles polynomials of length 128*n. The best performance results from
using the executable with just enough capacity to handle polynomial
being tested. I used this Visual C6 makefile
and defined MAXBITS 128, 256, etc.
Some helper files are needed at runtime. Put irreducables.bin in the current working directory. This file is used during a partial check for irreducibility. Also, make a subdirectory called factor2n-1and in it place Andreas Rieke's factorizations. They are here, but for convenience are available in a single zip file here. |
|
| Executables (Pentium III) | |
| Executables (Athlon, Pentium II) | |
| Searching for one polynomial of each degree | |
| For the fastest search, put text like this into a batch file. Here are the results of Andreas Rieke extended to limit of his factorizations. | |
| Searching for trinomials | |
| The program has the ability to search for polynomials of a certain weight. To search for trinomials, use the command line switch "-weight=3". Here are the trinomial results of Andreas Rieke extended to the limit of his factorizations. | |
| Searching for dense primitive polynomials | |
| The -weight command line switch
can also be used to find dense primitive polynomials (polynomials with
many non-zero coefficients). For example,
ppsearch128 weight=19 bits=20 binary search=999 100111111111111111111 111111111110011111111 111010111111111111111 111111110111101111111 111100111111111111111 111111111011101111111 111011101111111111111 111111111110101111111 111111001111111111111 111111111111100111111 111101111011111111111 111111111110111101111 111111101011111111111 111111111111111001111 111111110011111111111 111111111011111110111 111011111110111111111 111111111111101110111 111111101110111111111 111111111111111010111 111111101111011111111 111111111111111111001 |
|
| Primitivity testing | |
| Here is an example command line for doing a primitivity test: ppsearch1152 search=1 verbose poly="x^1047 + x^10 + 1" Note the use of double quotes. |
|
| Primitive polynomials with coefficients from fields other than GF(2) | |
This software only addresses polynomials with coefficients from GF(2). This is a unique case because modern computers have native hardware support for parallel operations with these numbers (XOR). To find primitive polynomials in other fields, use Sean O'Connor's program. |
|
| Contact Info | |
|
scott.duplichan#hp.com |
|