home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / crypt / 6548 < prev    next >
Encoding:
Text File  |  1993-01-08  |  1.3 KB  |  28 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!mcdchg!chinet!schneier
  3. From: schneier@chinet.chi.il.us (Bruce Schneier)
  4. Subject: Primitive Polynomials (Mod 2)
  5. Message-ID: <C0Jtyt.3HH@chinet.chi.il.us>
  6. Keywords: Primitive Polynomials (Mod 2)
  7. Organization: Chinet - Public Access UNIX
  8. Date: Fri, 8 Jan 1993 18:56:52 GMT
  9. Lines: 17
  10.  
  11. I have two questions about primitive polynomials (mod 2):
  12.  
  13. 1)  I was under the impression that if the feedback sequence of a LFSR is
  14. a primitive polynomial (mod 2), then the period of the LFSR is 2^n - 1, where
  15. n is the degree of the polynomial.  I recently got a copy of Zierler and
  16. Brillhart's paper:  "On Primitive Trinomials (mod 2)," Information and 
  17. Control, 13 (1968), 541-554.  The article implies that this is not the case:
  18. "Those n where 2^n - 1 is completely factored, but for which the periods of
  19. the irreducable T_n,k(x) have not as yet been determined...."
  20.  
  21. 2)  Near as I can tell, if x^p + x^q + 1 is a primitive trinomial (mod 2), then
  22. so is x^p + x^(p-q) + 1.  Does this property extend to polynomials with more
  23. coefficients?  Assuming that x^p + x^q + x^r + 1 is primitive, what other
  24. polynomial is necessarily primitive?  Assuming that x^p + x^q + x^r + x^s + 1
  25. is primitive, what other polynomial is necessarily primitive?
  26.  
  27. Bruce
  28.