Discrete logarithm for polynomials

Since you bring up binary linear feedback shift registers at the end, I feel that it may be of interest to describe a relevant simple special case I once worked out when a slightly perpelexed colleague (a telcomm engineer) asked me about it. Just to get the ball rolling. If you have seen this much, then I apologize for wasting your time. Alas, this answer does not cover an awful lot of ground.

This is about the very special case $p=2$, $Q=S^k$, $k=2^ell$. In other words, the multiplicity of the irreducible polynomial $S$ as a factor is a power of $p$.

Let $L$ be the order of $X$ in the ring $Bbb{F}_2[X]/S$. Then $L$ is also the period of the LFSR-sequence gotten with feedback polynomial $S$. The starting point is the simple observation that as $$ X^Lequiv1pmod S, $$ freshman's dream then implies that $X^{2L}+1=(X^L+1)^2$ is divisible by $S^2$. Repeating the dose, we see that $X^{2^jL}+1$ is divisible by $S^k$ for all $kle 2^j$. In other words, if $j$ is the smallest natural number such that $2^jge k$ it easily follows that the smallest period of the LFSR sequence generated by $S^k$ is $2^jL$. We know that the multiplicity of zeros of $X^{2^jL}+1$ in $overline{Bbb{F}_2}$ is exactly $2^j$, so a proper factor won't do.

This means that among the remainders of $X^i$ modulo $S^k$, $iinBbb{N}$, each coset modulo $S$ appears only $2^j$ times. The possibilities are thus severely limited.

Next I restrict myself to the case $k=2^j$. Let's take a look at a small case $k=4$, $S=X^2+X+1$, $L=3$, to see what's going on. We have $S^4=X^8+X^4+1$, so the cyclic subgroup generated by $X$ modulo $S^4$ contains the following $12$ cosets. $${1,X,X^2,X^3,X^4,X^5,X^6,X^7,X^4+1,X^5+X,X^6+X^2,X^7+X^3}.$$ You see that all the elements only contain terms of degrees in a single residue class modulo $4$. As $S(X)^4=S(X^4)$ a moments reflection shows that this must always be the case.

In terms of a linear feedback shift register this means that we really should view the register of 8 bits consisting of four parts (or blocks) of bits at positions $B_i:={i,i+4}, i=0,1,2,3$. A single clock tick moves the contents of $B_i, i=0,1,2,$ to the block $B_{i+1}$, but the contents of the block $B_3$ become the new content of the block $B_0$ only after being exposed to the LFSR with feedback polynomial $S$.

Viewed differently, if we run the clock four ticks, multiplying the coset by $X^4$, then each block is mapped back to its own position, but all four of them took turns getting exposed to the feedback polynomial $S$.

I'm sure this point of view let's you solve the discrete logarithm problem modulo $S^{2^j}$ if you can solve it modulo $S$. I'm afraid I don't remember what can be said about the cases when the exponent is not a power of $p$. I will add more, if I can think of something.

Notice that similar partitioning of the shift register may take place with certain other feedback polynomials also. For example the ninth cyclotomic polynomial $Phi_9(X)=X^6+X^3+1$ remains irreducible modulo $2$. It is highly non-primitive as $L=9$ instead of the primitive case $2^6-1=63$. Anyway, the shift register of six bits is partitioned into three parts of the form $B_i={i,i+3}, i=0,1,2,$ with similar behavior.