🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: sci.crypt
Article #2999

Primitive Polynomials (Mod 2)

#2999
From: Bruce Schneier
Date: Fri, 08 Jan 1993 18:56
17 lines
1376 bytes
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
Technical Details
Message-ID: <C0Jtyt.3HH@chinet.chi.il.us>
Path: arc1-ca.pugleaf.net!sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!mcdchg!chinet!schneier

Show Full Headers
Complete Article Headers
Newsgroups: sci.crypt
Path: arc1-ca.pugleaf.net!sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!mcdchg!chinet!schneier
From: schneier@chinet.chi.il.us (Bruce Schneier)
Subject: Primitive Polynomials (Mod 2)
Message-ID: <C0Jtyt.3HH@chinet.chi.il.us>
Keywords: Primitive Polynomials (Mod 2)
Organization: Chinet - Public Access UNIX
Date: Fri, 8 Jan 1993 18:56:52 GMT
Lines: 17