home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18855 < prev    next >
Encoding:
Text File  |  1993-01-29  |  1.3 KB  |  44 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!math.fu-berlin.de!ira.uka.de!gmd.de!newsserver.jvnc.net!louie!udel!gatech!ukma!mont!mont!stephen
  3. From: stephen@mont.cs.missouri.edu (Stephen Montgomery-Smith)
  4. Subject: Polynomials modulo 2
  5. Message-ID: <stephen.728236166@mont>
  6. Keywords: polynomials, division, modular arithmetic
  7. Organization: University of Missouri
  8. Date: 28 Jan 93 15:49:26 GMT
  9. Lines: 33
  10.  
  11. Dear All, 
  12.  
  13. A friend gave me a polynomial p, whose coefficients come from the field
  14. of order two.  His question was, is there an n such that p divides
  15. 1 + x^n, and if so, what is the smallest positive n.  (All division is
  16. modulo 2).
  17.  
  18. I deduced that the answer is yes --- there is such an n.  To find it, there
  19. is the following algorithm.  The polynomials are represented by binary
  20. numbers:
  21.   a_0 + a_1 x + a_2 x^2 + ... + a_n x^n 
  22. is represented by the binary number a_n ... a_1 a_0.
  23.  
  24. input(p);
  25. n = 0;
  26. q = 1;
  27. repeat
  28.   if (bit 0 of q = 1) then q = q xor p;
  29.   shift q one place to right;
  30.   n = n+1;
  31. until q = 1;
  32. output(n);
  33.  
  34. The algorithm is based on synthetic division.
  35.  
  36. So, here is my question.  Has this been done before (I think yes) and
  37. if so, what is a good reference?  Also, has anyone come up with a better
  38. algorithm than the one I presented here?  
  39.  
  40. Thanks in advance,
  41.  
  42. Stephen Montgomery-Smith
  43.  
  44.