🚀 go-pugleaf

 In <C0Jtyt.3HH@chinet.chi.il.us> schneier@chinet.chi.il.us
 (Bruce Schneier) writes:

>I have two questions about primitive polynomials (mod 2):
>
>1)  I was under the impression that if the feedback sequence of a LFSR is
>a primitive polynomial (mod 2), then the period of the LFSR is 2^n - 1, where
>n is the degree of the polynomial.  I recently got a copy of Zierler and
>Brillhart's paper:  "On Primitive Trinomials (mod 2)," Information and
>Control, 13 (1968), 541-554.  The article implies that this is not the case:
>"Those n where 2^n - 1 is completely factored, but for which the periods of
>the irreducable T_n,k(x) have not as yet been determined...."

 Basically, "irreducible" <> "primitive."


 Your quote comes from Z&B at the bottom of p. 554; at the bottom of
 p. 553 we see:

      "Of the 703 irreducible trinomials that were investigated,
 433 turned out to be primitive, which is about 62%."


 Also, in the Introduction:

 "...f(x) of degree n is irreducible...."  "In case the period of f
 is 2^n  - 1, f is said to be primitive."


 For most degrees n, some irreducibles are primitive, and some are
 not.  We find out which is which by determining their periods
 under multiplication (modulo the polynomial).  [When we have
 an irreducible, we have a finite field, so it is inevitable that
 a cycle of some length will occur.]

 A primitive will generate a single "maximal length" cycle with
 period 2^n - 1 (plus a degenerate cycle from value zero); non-
 primitive irreducibles will generate multiple cycles of lesser
 period, but those periods will divide 2^n - 1 [1:308].  So, to
 certify a primitive, we start with a known value x (this is
 x^1) and generate the various powers of that value (x^2 mod p,
 x^4 mod p, etc.) (p the irreducible being checked) for powers
 which are factors of 2^n - 1.  The last value before we step to
 the original value (thus closing a cycle) will be 1, so if we
 manage to produce value 1 for some non-trivial factor of 2^n - 1,
 we have found a "short" cycle, and know that the irreducible
 is not primitive.

 (This same structure pretty much applies to integers mod n: RSA.
 RSA inherently creates cycles under multiplication (length phi),
 and if we could find the length of those cycles (since we know
 the encryption power) we could decipher RSA without factoring n.
 But in RSA n is not prime (not "irreducible"), and it is not known
 (at least to me) how we could find the length of RSA cycles.)

 When the factorization of 2^n - 1 is known the primitive check is
 relatively easy (because we have fast powering algorithms, when we
 know exactly what powers we need to check), but the testing still
 must be performed.  Apparently, Z&B just did not get around to
 testing some particular polys.

 For polys of large degree, knowing the factors of 2^n - 1 is a big
 problem, but we can instead use degrees which are Mersenne primes,
 in which case every irreducible is primitive, and then we only
 need find an irreducible.


>2)  Near as I can tell, if x^p + x^q + 1 is a primitive trinomial (mod 2), then
>so is x^p + x^(p-q) + 1.  Does this property extend to polynomials with more
>coefficients?

 Yes.  The binary bit-pattern is simply reversed, or "flopped
 over," left-to-right.

 Schroeder [2:261-262] calls these "reciprocal" polynomials, and
 remarks [2:265] that they produce sequences which are "mirror
 images of each other (reflected in 'time')."

 This property has been used to check the CRC of data on magnetic
 tape when the tape is read "in reverse."  (The reciprocal poly is
 used instead of the original.)


>Assuming that x^p + x^q + x^r + 1 is primitive, what other
>polynomial is necessarily primitive?

 Assuming that, then x^p + x^(p-r) + x^(p-q) + 1.

 Note that p, q, r, need not be primes.


>Assuming that x^p + x^q + x^r + x^s + 1
>is primitive, what other polynomial is necessarily primitive?

 x^p + x^(p-s) + x^(p-r) + x^(p-q) + 1.

 Note that x^p and x^0 are always present:  For any irreducible
 mod 2, the top and bottom bits are always '1'.  A degree-p
 mod 2 polynomial has p+1 bits.


 References:

 [1]  Alanen, J. and D. Knuth.  1964.  Tables of Finite Fields.
      Sankhya, The Indian Journal of Statistics.  Series A.
      26: 305-328.

 [2]  Schroeder, M.  1986.  Number Theory in Science and
      Communication.  Springer-Verlag.

 ---
 Terry Ritter   ritter@cactus.org