COMPUTING PRIMITIVE POLYNOMIALS - SOFTWARE DESIGN

Sean E. O'Connor

Introduction

We discuss some topics in the software design of this program.

There are two versions. The object oriented C++ version has no limit to on the degree of the polynomial, except system memory, though it will slow down for very high degree. The C version uses the built-in integer type on the CPU which limits the degree of the polynomial.

Program Settings

Setting the print statistics flag -s on the command line shows the progress of the program while it is finding a primitive polynomial. Default is off.

Setting check flag -c on the command line runs an independent check on the primitive polynomial after it is found to confirm it is primitive. Default is off, because this test can take practically forever for large values of pⁿ: using the definition of primitive polynomial, we simply check x^k(mod f(x), p) is not equal to 1 for 1 ≤ k ≤ pⁿ-2, but that x^k(mod f(x), p) = 1 for k = pⁿ - 1. This flag is useful for debugging purposes.

To find and list all primitive polynomials, use the -a flag.

Multiple Precision Integer Arithmetic C++ version

The largest integer which needs to be computed anywhere in the program is pⁿ. Variables in the program which require extra precision are defined to be of BigInt type. We use multiple precision integer arithmetic.

Given p and n, we can find the maximum number of digits m and base b for our multiple precision integer arithmetic.

First, the base b. Let N = number of bits in an integer type which we will use for our digits. The maximum unsigned integer is 2^N-1. The largest number which is computed in the multiple precision integer arithmetic algorithms is b². So if we let b = 2^{N/2 - 1}, we'll guarantee b² < 2^N-1. and b will be a power of 2, an N/2 digit binary number, which is needed to efficiently implement shifting and masking operations.

The maximum integer which needs to be computed is pⁿ = b^{m - 1}. So pⁿ + 1 = b^m. A bound is then pⁿ < b^m, or n lg p < m lg b or (n lg p) / (lg b) < m or m = ⌈ (n lg p) / lg b ⌉

Lower Bounds for pⁿ

They are p ≥ 2, n ≥ 2.

Limit on the Sizes of p and n: C Version

Since we use the system hardware integer arithmetic, there are internal limits within program which restrict the size of the largest primitive polynomial which may be computed. We discuss bounds on various internal integer variables below. Most bounds are set in the source file pp.h and tested in pp.c.

Upper Bound on Size of Internal Integer Computations

The largest integer which needs to be computed anywhere in the program is pⁿ. Variables in the program which require this extra precision are defined to be of Bigint type.

This should be an unsigned integer type, since all computations with Bigint involve multiplication, division, modulo, masking and decrement by 1, so we don't use negative numbers. The alternative is to use a signed integer type, but reduce the number of bits used by 1, to avoid overflowing into the sign bit.

For the Windows/Intel platform, the largest integer type in the Microsoft Visual C++ 6.0 SP3 compiler is the signed 64-bit __int64. For a Mac OS X, PC/cygwin or other Unix platform which uses the GNU C compiler 4.0, we use the 64-bit long long type. We play it safe and assume this is also a signed type. Thus we need to set the maximum size of pⁿ to 2^64-1-1. So, for example, when p = 2, the highest polynomial degree is n = 62.

Extensions beyond 64 bit precision require multiple precision arithmetic.

A Bound for pⁿ (MAXPTON)

The basic bounds are p ≤ 2, n ≥ 2 and pⁿ ≤ MAXPTON All other bounds are derived from these.

A Bound for r

r = (pⁿ - 1) / (p - 1) so the upper bound is r (pⁿ - 1) / (2 - 1) = pⁿ - 1 ≤ pⁿ ≤ MAXPTON. And the lower bound is r = p^n-1 + p^n-2 + ... + p + 1 ≥ p + 1 ≥ 3.

A Bound for the Number of Prime Factors (MAXNUMPRIMEFACTORS)

This is used for sizing the array containing the prime factors of r and their multiplicities. r = p₁^e₁ ... p_k^e_k ≥ 2 ... 2 = 2^k. r = p₁ ... p_k ≥ 2 ... 2 = 2^k. Since the p_i ≥ 2 are primes. Since r ≥ 3 from above, we must have at least one prime factor, and so k ≥ 1. Thus 2^k ≤ r or k ≤ lg r where lg is log₂. Then k ≤ lg MAXPTON. We need an integer value for the upper bound, so we play it safe and round up to MAXNUMPRIMEFACTORS = 1 + floor( lg MAXPTON ).

This is also used for the array containing the prime factors of p-1. As above, the maximum number of prime factors of p-1 < max. num. prime factors of p < < max. num. prime factors of pⁿ. So the upper bound above should work fine.

A Bound for n. (MAXDEGPOLY)

2ⁿ ≤ pⁿ ≤ MAXPTON, so n ≤ lg MAXPTON. Again, to play it safe, we chop this bound to MAXDEGPOLY = floor( lg MAXPTON ). The bound is exact when p = 2.

Number of trials for probabilistic primality testing. (NUM_PRIME_TEST_TRIALS)

We error check the input parameter p, to see if it is prime. Our probabilistic primality test has the failure probabilities, P( test says p is not prime | p is prime ) ≤ (1/4)^{NUM_PRIME_TEST_TRIALS}. Defaulted to 25. The test always succeeds in detecting if p is composite (non-prime). This depends somewhat on the quality of the system random number generator, rand().

Home