10
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 6
    $\begingroup$ I think you can first solve in $\mathbb F_p[X]/S$, and then lift to higher powers $\mathbb F_p[X]/S^k$ inductively using some version of Hensel's lemma, or for faster convergence, Newton iteration. $\endgroup$ Commented Nov 2, 2020 at 15:16
  • $\begingroup$ I have a somewhat different impression than @JoeSilverman. Correct me if I'm wrong, but I think this is somewhat analogous to the following situation in the $p$-adic domain. If $\mathcal{O}$ is the ring of integers in an unramified extension of $\Bbb{Q}_p$, residue class field $\Bbb{F}_q$, then the unit group of $\mathcal{O}/(p^2)$ is isomorphic to a direct product of $\Bbb{F}_q^*$ and an elementary abelian $p$-group of $1+p\mathcal{O}$ modulo $p^2$. Increasing the exponent of $p$ complicates matters a bit, but $1+p\mathcal{O}$ modulo $p^\ell, \ell>2$ is still an abelian $p$-group, no? $\endgroup$ Commented Nov 5, 2020 at 14:03
  • $\begingroup$ @JyrkiLahtonen Thanks for the correction. I think that you're right, It's a lifting problem in the multiplicative group $(\mathbb F_p[X]/S^k)^*$, not in the additive group $\mathbb F_p[X]/S^k$ as I had indicated. But we seem to be in agreement that one should be able to lift the initial solution inductively. And of course, not only is $1+p\mathcal O$ modulo $p^\ell$ an abelian $p$-group, but once $\ell$ is large enough, it has a large cyclic piece that's isomorphic to an additive group. $\endgroup$ Commented Nov 5, 2020 at 14:56

1 Answer 1

Reset to default
4
$\begingroup$

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^L\equiv1\pmod 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 $k\le 2^j$. In other words, if $j$ is the smallest natural number such that $2^j\ge 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$, $i\in\Bbb{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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I suppose you meant "shift"... xd $\endgroup$ Commented Nov 7, 2020 at 23:45
  • $\begingroup$ OMG. Thanks @EFinat-S $\endgroup$ Commented Nov 8, 2020 at 5:21

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.