🚀 go-pugleaf

In article <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...."
>
>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?  Assuming that x^p + x^q + x^r + 1 is primitive, what other
>polynomial is necessarily primitive?  Assuming that x^p + x^q + x^r + x^s + 1
>is primitive, what other polynomial is necessarily primitive?
>
>Bruce

As for (1), I don't have a copy of Zierler & Brillhart, but what you
quote is not a contradiction.

A primitive polynomial p over a ring R is an irreducible polynomial
the root of which is a primitive element in the extension field, i.e.,
the root \alpha has the property that R[x]/(p)=R(\alpha).

This property is important to LFSRs because of what we get when we
take R=Z_2 and look at the sequence 1, x, x^2, ..., x^k, ..., etc, all
modulo p.  Since in extension fields we identify the indeterminate x
with \alpha, we see that the sequence is exactly what \alpha will
generate, which is the entire field when E=Z_2[x]/(p), p a primitive
polyn.  Since we know that [E:Z_2] = n = deg(p), E has 2^n elements in
it.  Excluding the zero polyn, we see that the period must be 2^n-1 --
the sequence must cycle through all elements of E except for 0 (x^m
can not be 0, because otherwise x=\alpha would be a zero divisor,
contradicting the fact that E is a field).  An LFSR generates just the
coefficient to the x^0 term of this sequence.

Does anyone know if there's a proof that the low coefficient of this
2^n-1 period sequence also has the same period?

If T_{n,k}(x) are just irreducible but not nec'y primitive, then we
don't know the period of the LFSR -- that would depend on the initial
conditions, since there is more than one cycle.

Dunno about (2).

-bsy

ps: while this is not (yet) a cryptography question, at least it's not
patent flamage or some such, and the mathematics can have
cryptographic applications.  The signal-to-noise of sci.crypt has been
really low lately....

-- 
Bennet S. Yee		Phone: +1 412 268-7571		Email: bsy+@cs.cmu.edu
School of Computer Science, Carnegie Mellon, Pittsburgh, PA 15213-3890