home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / crypt / 6695 < prev    next >
Encoding:
Text File  |  1993-01-12  |  4.7 KB  |  126 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!cs.utexas.edu!milano!cactus.org!ritter
  3. From: ritter@cactus.org (Terry Ritter)
  4. Subject: Re: Primitive Polynomials (Mod 2)
  5. Message-ID: <1993Jan12.092909.19209@cactus.org>
  6. Keywords: Primitive Polynomials (Mod 2)
  7. Organization: Capital Area Central Texas UNIX Society, Austin, Tx
  8. References: <C0Jtyt.3HH@chinet.chi.il.us>
  9. Date: Tue, 12 Jan 1993 09:29:09 GMT
  10. Lines: 114
  11.  
  12.  
  13.  In <C0Jtyt.3HH@chinet.chi.il.us> schneier@chinet.chi.il.us
  14.  (Bruce Schneier) writes:
  15.  
  16. >I have two questions about primitive polynomials (mod 2):
  17. >
  18. >1)  I was under the impression that if the feedback sequence of a LFSR is
  19. >a primitive polynomial (mod 2), then the period of the LFSR is 2^n - 1, where
  20. >n is the degree of the polynomial.  I recently got a copy of Zierler and
  21. >Brillhart's paper:  "On Primitive Trinomials (mod 2)," Information and
  22. >Control, 13 (1968), 541-554.  The article implies that this is not the case:
  23. >"Those n where 2^n - 1 is completely factored, but for which the periods of
  24. >the irreducable T_n,k(x) have not as yet been determined...."
  25.  
  26.  Basically, "irreducible" <> "primitive."
  27.  
  28.  
  29.  Your quote comes from Z&B at the bottom of p. 554; at the bottom of
  30.  p. 553 we see:
  31.  
  32.       "Of the 703 irreducible trinomials that were investigated,
  33.  433 turned out to be primitive, which is about 62%."
  34.  
  35.  
  36.  Also, in the Introduction:
  37.  
  38.  "...f(x) of degree n is irreducible...."  "In case the period of f
  39.  is 2^n  - 1, f is said to be primitive."
  40.  
  41.  
  42.  For most degrees n, some irreducibles are primitive, and some are
  43.  not.  We find out which is which by determining their periods
  44.  under multiplication (modulo the polynomial).  [When we have
  45.  an irreducible, we have a finite field, so it is inevitable that
  46.  a cycle of some length will occur.]
  47.  
  48.  A primitive will generate a single "maximal length" cycle with
  49.  period 2^n - 1 (plus a degenerate cycle from value zero); non-
  50.  primitive irreducibles will generate multiple cycles of lesser
  51.  period, but those periods will divide 2^n - 1 [1:308].  So, to
  52.  certify a primitive, we start with a known value x (this is
  53.  x^1) and generate the various powers of that value (x^2 mod p,
  54.  x^4 mod p, etc.) (p the irreducible being checked) for powers
  55.  which are factors of 2^n - 1.  The last value before we step to
  56.  the original value (thus closing a cycle) will be 1, so if we
  57.  manage to produce value 1 for some non-trivial factor of 2^n - 1,
  58.  we have found a "short" cycle, and know that the irreducible
  59.  is not primitive.
  60.  
  61.  (This same structure pretty much applies to integers mod n: RSA.
  62.  RSA inherently creates cycles under multiplication (length phi),
  63.  and if we could find the length of those cycles (since we know
  64.  the encryption power) we could decipher RSA without factoring n.
  65.  But in RSA n is not prime (not "irreducible"), and it is not known
  66.  (at least to me) how we could find the length of RSA cycles.)
  67.  
  68.  When the factorization of 2^n - 1 is known the primitive check is
  69.  relatively easy (because we have fast powering algorithms, when we
  70.  know exactly what powers we need to check), but the testing still
  71.  must be performed.  Apparently, Z&B just did not get around to
  72.  testing some particular polys.
  73.  
  74.  For polys of large degree, knowing the factors of 2^n - 1 is a big
  75.  problem, but we can instead use degrees which are Mersenne primes,
  76.  in which case every irreducible is primitive, and then we only
  77.  need find an irreducible.
  78.  
  79.  
  80. >2)  Near as I can tell, if x^p + x^q + 1 is a primitive trinomial (mod 2), then
  81. >so is x^p + x^(p-q) + 1.  Does this property extend to polynomials with more
  82. >coefficients?
  83.  
  84.  Yes.  The binary bit-pattern is simply reversed, or "flopped
  85.  over," left-to-right.
  86.  
  87.  Schroeder [2:261-262] calls these "reciprocal" polynomials, and
  88.  remarks [2:265] that they produce sequences which are "mirror
  89.  images of each other (reflected in 'time')."
  90.  
  91.  This property has been used to check the CRC of data on magnetic
  92.  tape when the tape is read "in reverse."  (The reciprocal poly is
  93.  used instead of the original.)
  94.  
  95.  
  96. >Assuming that x^p + x^q + x^r + 1 is primitive, what other
  97. >polynomial is necessarily primitive?
  98.  
  99.  Assuming that, then x^p + x^(p-r) + x^(p-q) + 1.
  100.  
  101.  Note that p, q, r, need not be primes.
  102.  
  103.  
  104. >Assuming that x^p + x^q + x^r + x^s + 1
  105. >is primitive, what other polynomial is necessarily primitive?
  106.  
  107.  x^p + x^(p-s) + x^(p-r) + x^(p-q) + 1.
  108.  
  109.  Note that x^p and x^0 are always present:  For any irreducible
  110.  mod 2, the top and bottom bits are always '1'.  A degree-p
  111.  mod 2 polynomial has p+1 bits.
  112.  
  113.  
  114.  References:
  115.  
  116.  [1]  Alanen, J. and D. Knuth.  1964.  Tables of Finite Fields.
  117.       Sankhya, The Indian Journal of Statistics.  Series A.
  118.       26: 305-328.
  119.  
  120.  [2]  Schroeder, M.  1986.  Number Theory in Science and
  121.       Communication.  Springer-Verlag.
  122.  
  123.  ---
  124.  Terry Ritter   ritter@cactus.org
  125.  
  126.