Discrete logarithm for polynomials

Let $$p$$ be a fixed small prime (I’m particularly interested in $$p = 2$$), and let $$Q, R in mathbb{F}_p[X]$$ be polynomials.

Consider the problem of determining the set of $$n in mathbb{N}$$ such that $$X^n equiv R$$ in the ring $$mathbb{F}_p[X] / Q$$. It is easy to see that this is either the empty set $$emptyset$$, or a singleton set $${ a }$$, or an arithmetic progression $${ a + cm : m in mathbb{N} }$$.

In the special case where $$Q$$ is a primitive polynomial, $$mathbb{F}_p[X] / Q$$ is a finite field and this is just the ordinary discrete logarithm problem, and there’s an efficient quasi-polynomial-time algorithm for solving this: https://eprint.iacr.org/2013/400.pdf

What about when $$Q$$ is not a primitive polynomial? Can this more general problem be reduced to solving instances of the ordinary discrete logarithm, and therefore also be solved in quasi-polynomial time?

By the structure theorem for finitely-generated modules over a PID, we can factor $$mathbb{F}_p[X]/Q$$ as the direct sum of rings of the form $$mathbb{F}_p[X]/S^k$$, where $$S$$ is an irreducible polynomial. If we could solve the discrete logarithm problem in each of these direct summands, then the Chinese Remainder Theorem would determine the solution in the original ring. Hence, it suffices to consider the case where $$Q$$ is the power of an irreducible polynomial. But I can’t see how to proceed any further, because ‘power of an irreducible polynomial’ is not the same thing as ‘primitive polynomial’.

Motivation: when $$p = 2$$, this is equivalent to efficiently searching the output of a linear feedback shift register PRNG to determine where (if at all) a specific bit-string arises.

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.

Answered by Jyrki Lahtonen on January 4, 2021

Related Questions

Conditions for continuity of an integral functional

2  Asked on November 3, 2021 by james_t

Best-approximation with tensors of rank $ge2$

1  Asked on November 3, 2021

$x ‘(t) + g (x (t)) = f (t),quad forall tin mathbb R$ have periodic solution $iff; frac 1T int_0 ^ T f (t) dt in g (mathbb R)$

1  Asked on November 3, 2021

Smooth projective surface with geometrically integral reduction

2  Asked on November 3, 2021 by user158636

On the difference between Malliavin derivative and Gross-Sobolev derivative

0  Asked on November 3, 2021

Equivalent characterization of ordinary $F$-crystals

0  Asked on November 3, 2021 by qixiao

What subsystem of second-order arithmetic is needed for the recursion theorem?

1  Asked on November 3, 2021

How to calculate possible arrangements of hexagons?

0  Asked on March 4, 2021 by matt-roberts

Open affine subscheme of affine scheme which is not principal

5  Asked on February 28, 2021 by wanderer

Simple examples of equivariant cobordism

0  Asked on February 25, 2021 by user_501

Examples of plane algebraic curves

4  Asked on February 25, 2021 by alexandre-eremenko

Why believe Kontsevich cosheaf conjecture?

1  Asked on February 23, 2021 by rori

Geometric probabilistic problem on triangles on a plane

3  Asked on February 22, 2021 by penelope-benenati

Best texts on Lie groups for number theorists

1  Asked on February 21, 2021 by user163784

Geometric interpretation for conformally symmetric manifolds

0  Asked on February 21, 2021 by ivo-terek

Is there a 2-categorical, equivariant version of Quillen’s Theorem A?

0  Asked on February 21, 2021 by vidit-nanda

Positive maps on finite group algebras and group homomorphisms

2  Asked on February 20, 2021 by edwin-beggs

Does such a function exist?

1  Asked on February 20, 2021 by sascha

Making graphs isomorphic with edge additions/removals

1  Asked on February 18, 2021 by mikhail-tikhomirov