home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / crypt / 6657 < prev    next >
Encoding:
Internet Message Format  |  1993-01-11  |  3.3 KB
  1. Path: sparky!uunet!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!PLAY.TRUST.CS.CMU.EDU!bsy
  2. From: bsy+@CS.CMU.EDU (Bennet Yee)
  3. Newsgroups: sci.crypt
  4. Subject: Re: Primitive Polynomials (Mod 2)
  5. Keywords: Primitive Polynomials (Mod 2)
  6. Message-ID: <C0pnDp.KLD.2@cs.cmu.edu>
  7. Date: 11 Jan 93 22:20:07 GMT
  8. Article-I.D.: cs.C0pnDp.KLD.2
  9. References: <C0Jtyt.3HH@chinet.chi.il.us>
  10. Sender: news@cs.cmu.edu (Usenet News System)
  11. Reply-To: bsy+@cs.cmu.edu
  12. Organization: Cranberry Melon, School of Cucumber Science
  13. Lines: 57
  14. Nntp-Posting-Host: play.trust.cs.cmu.edu
  15.  
  16. In article <C0Jtyt.3HH@chinet.chi.il.us>, schneier@chinet.chi.il.us (Bruce Schneier) writes:
  17. >I have two questions about primitive polynomials (mod 2):
  18. >
  19. >1)  I was under the impression that if the feedback sequence of a LFSR is
  20. >a primitive polynomial (mod 2), then the period of the LFSR is 2^n - 1, where
  21. >n is the degree of the polynomial.  I recently got a copy of Zierler and
  22. >Brillhart's paper:  "On Primitive Trinomials (mod 2)," Information and 
  23. >Control, 13 (1968), 541-554.  The article implies that this is not the case:
  24. >"Those n where 2^n - 1 is completely factored, but for which the periods of
  25. >the irreducable T_n,k(x) have not as yet been determined...."
  26. >
  27. >2)  Near as I can tell, if x^p + x^q + 1 is a primitive trinomial (mod 2), then
  28. >so is x^p + x^(p-q) + 1.  Does this property extend to polynomials with more
  29. >coefficients?  Assuming that x^p + x^q + x^r + 1 is primitive, what other
  30. >polynomial is necessarily primitive?  Assuming that x^p + x^q + x^r + x^s + 1
  31. >is primitive, what other polynomial is necessarily primitive?
  32. >
  33. >Bruce
  34.  
  35. As for (1), I don't have a copy of Zierler & Brillhart, but what you
  36. quote is not a contradiction.
  37.  
  38. A primitive polynomial p over a ring R is an irreducible polynomial
  39. the root of which is a primitive element in the extension field, i.e.,
  40. the root \alpha has the property that R[x]/(p)=R(\alpha).
  41.  
  42. This property is important to LFSRs because of what we get when we
  43. take R=Z_2 and look at the sequence 1, x, x^2, ..., x^k, ..., etc, all
  44. modulo p.  Since in extension fields we identify the indeterminate x
  45. with \alpha, we see that the sequence is exactly what \alpha will
  46. generate, which is the entire field when E=Z_2[x]/(p), p a primitive
  47. polyn.  Since we know that [E:Z_2] = n = deg(p), E has 2^n elements in
  48. it.  Excluding the zero polyn, we see that the period must be 2^n-1 --
  49. the sequence must cycle through all elements of E except for 0 (x^m
  50. can not be 0, because otherwise x=\alpha would be a zero divisor,
  51. contradicting the fact that E is a field).  An LFSR generates just the
  52. coefficient to the x^0 term of this sequence.
  53.  
  54. Does anyone know if there's a proof that the low coefficient of this
  55. 2^n-1 period sequence also has the same period?
  56.  
  57. If T_{n,k}(x) are just irreducible but not nec'y primitive, then we
  58. don't know the period of the LFSR -- that would depend on the initial
  59. conditions, since there is more than one cycle.
  60.  
  61. Dunno about (2).
  62.  
  63. -bsy
  64.  
  65. ps: while this is not (yet) a cryptography question, at least it's not
  66. patent flamage or some such, and the mathematics can have
  67. cryptographic applications.  The signal-to-noise of sci.crypt has been
  68. really low lately....
  69.  
  70. -- 
  71. Bennet S. Yee        Phone: +1 412 268-7571        Email: bsy+@cs.cmu.edu
  72. School of Computer Science, Carnegie Mellon, Pittsburgh, PA 15213-3890
  73.