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)
 ppsearch128 ppsearch1408 ppsearch2688 ppsearch3968 ppsearch5248 ppsearch256 ppsearch1536 ppsearch2816 ppsearch4096 ppsearch5376 ppsearch384 ppsearch1664 ppsearch2944 ppsearch4224 ppsearch5504 ppsearch512 ppsearch1792 ppsearch3072 ppsearch4352 ppsearch5632 ppsearch640 ppsearch1920 ppsearch3200 ppsearch4480 ppsearch5760 ppsearch768 ppsearch2048 ppsearch3328 ppsearch4608 ppsearch5888 ppsearch896 ppsearch2176 ppsearch3456 ppsearch4736 ppsearch6016 ppsearch1024 ppsearch2304 ppsearch3584 ppsearch4864 ppsearch6144 ppsearch1152 ppsearch2432 ppsearch3712 ppsearch4992 ppsearch6272 ppsearch1280 ppsearch2560 ppsearch3840 ppsearch5120 ppsearch6400
Executables (Athlon, Pentium II)
 ppsearch128 ppsearch1408 ppsearch2688 ppsearch3968 ppsearch5248 ppsearch256 ppsearch1536 ppsearch2816 ppsearch4096 ppsearch5376 ppsearch384 ppsearch1664 ppsearch2944 ppsearch4224 ppsearch5504 ppsearch512 ppsearch1792 ppsearch3072 ppsearch4352 ppsearch5632 ppsearch640 ppsearch1920 ppsearch3200 ppsearch4480 ppsearch5760 ppsearch768 ppsearch2048 ppsearch3328 ppsearch4608 ppsearch5888 ppsearch896 ppsearch2176 ppsearch3456 ppsearch4736 ppsearch6016 ppsearch1024 ppsearch2304 ppsearch3584 ppsearch4864 ppsearch6144 ppsearch1152 ppsearch2432 ppsearch3712 ppsearch4992 ppsearch6272 ppsearch1280 ppsearch2560 ppsearch3840 ppsearch5120 ppsearch6400
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