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:

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.

MathOverflow Asked by Adam P. Goucher on January 4, 2021

1 Answers

One Answer

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

Add your own answers!

Related Questions

How to calculate possible arrangements of hexagons?

0  Asked on March 4, 2021 by matt-roberts


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


Ask a Question

Get help from others!

© 2022 All rights reserved.