| <<< Note 1706.0 by SSAG::LARY "Laughter & hope & a sock in the eye" >>>
-< Looking for a Polynomial >-
I have a practical use for the irreducible polynomial of order 64 over GF(2)
which has the smallest numerical value when you write it as a string of ones
and zeros (the coefficients, highest coefficient on the left). Actually, it
would suffice to have any one of the irreducible polynomials of that order with
the largest gap between the x^64 term and the next lowest term. (In fact, I
would settle for any irreducible polynomial of that order with a "very big"
gap between those terms, but why set my sights low?)
Here's an example:
X^64 + X^4 + X^3 + X + 1
And if you need a degree 128 example:
X^128 + x^29 + X^27 + X^2 + 1
Unfortunately, the "standard" book I have on error correction (Pedersen &
Weldon) only lists (primitive) polynomials up to order 34. The brute-force
way of finding the answer computationally appears to require about two billion
polynomial divides (each a set of 64 shift-test-XOR operations) per candidate,
which could take quite a while. So, I'm looking for a better book reference
or a better algorithm to determine irreducibility...
A paper which lists primitive trinomials (or weight 5 polynomials
if no trinomial is found) up to degree 168 is
W. Stahnke _Primitive Binary Polynomials_
Mathematics of Computation 27 No 124 October 1973 pp 977-980
To test for primitivity, it's enough to raise X to the 2^N'th
power by successive squaring modulo the polynomial and see if
the remainder is equal to X. If it is, the period of the shift
register sequence divides 2^N-1. Next, if 2^N-1 is not prime
(not a Mersenne prime) you have to double check that X^K where
K = (2^N-1)/Q for each prime factor Q of 2^N-1 is *not* equal to
X. This ensures that the period is maximum, not terminating
early; it can be done by binary powering the usual way.
The nuisance is factoring 2^N-1 for large N... I have some programs
that hardcoded a table of these factors to test this.
FWIW, Pederson does have a feasable algorthm (based on successive
squaring) in the appendix that lists the polynomials. You don't
have to cycle thru billions of states.
- Jim
|