order of $x \operatorname{mod} p(x)$ in $\mathbb Z_2$

Question

I am writing a software that analyze the behavior of an LFSR given its feedback polynomial. At some point, I need to compute the order of $x \operatorname{mod} p(x)$ in $\mathbb Z_2$. In mathematical terms I am looking for the smallest positive integer $k$ such that $x^k\equiv 1\pmod {p(x)}$. $p(x)$ being a given polynomial with coeficient in $\mathbb Z_2$ ($0$ or $1$).

Some naive questions about that:

• what is $k$ for $p(x)=0, 1$ or $x$ ? any convention on those cases ?
• Is there a well known, efficient algorithm for that ?
• Is there a software that I can use to generate test vectors (testing against an exhaustive search does not scale very well...)

Answer 1

1. Special cases:
   As stated by Jyrki, the order of x is not defined for polynomials p(x) of degree 0 or degree >= 1 if p(0)=0.
   
   

2. Algorithm:
   After spending a fair amount of time searching, I think the best algorithm to compute the order of x is given in "Finite Fields" by Lidl & Niederreiter.
   It says the following:
   
   let f be a reducible polynomial: f = f1^b1 * ... * fk^bk
   Then ord(f)=e * 2^t
   With e=lcm(ord(f1),...,ord(fk)) and t smallest integer such that 2^t>=max(b1,...bk)
   
   To compute the order of x for irreducible polynomials, it gives the following algorithm:
   let m be the degree of an irreducible polynomial p(x)
   if p(x) is primitive, ord(p) = (2^m)-1.
   Otherwise, let n = (2^m)-1 = (p1 ^r1) * ... * (pk^rk)
   

   set ordx = 1
   For each factor pi:
       set t = ri
       set divider = pi
       while(t>1)
           set exp = n/divider (should always be an integer division since divider is always a factor of n.)
           if x^exp mod p(x) != 1
               ordx = ordx * pi^t
               t=0 (break the loop to look at next pi)
           else
               t = t - 1
               divider = divider * pi
       end while
   end foreach
   

   
   result is ordx
   As indicated by Jyrki, one can discard some of the factors before going through the main loop, see his first comment on the original question.
   
   

3. Software
   I did not find any software which compute the order of x out of the box (well I looked only at what can be evaluated free of charge). My implementation of the algorithm presented above is available here: http://www.nimp.co.uk/software/z2PolyAnalysis.zip (I tested it as hard as I could, still I would not call that a reference, if you get some different result with another tool, please let me know!)