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.

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

1 AnswersSince 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

2 Asked on November 3, 2021 by james_t

calculus of variations fa functional analysis integral operators integral transforms integration

1 Asked on November 3, 2021

1 Asked on November 3, 2021

differential equations fa functional analysis fixed point theorems periodic functions

2 Asked on November 3, 2021 by user158636

ag algebraic geometry algebraic surfaces arithmetic geometry

0 Asked on November 3, 2021

0 Asked on November 3, 2021 by qixiao

1 Asked on November 3, 2021

0 Asked on March 4, 2021 by matt-roberts

5 Asked on February 28, 2021 by wanderer

0 Asked on February 25, 2021 by user_501

4 Asked on February 25, 2021 by alexandre-eremenko

1 Asked on February 23, 2021 by rori

3 Asked on February 22, 2021 by penelope-benenati

co combinatorics combinatorial optimization mg metric geometry pr probability

1 Asked on February 21, 2021 by user163784

3 Asked on February 21, 2021 by madeleine-birchfield

axioms ct category theory foundations groupoids higher category theory

0 Asked on February 21, 2021 by ivo-terek

0 Asked on February 21, 2021 by vidit-nanda

ct category theory equivariant homotopy group actions higher category theory

2 Asked on February 20, 2021 by edwin-beggs

1 Asked on February 20, 2021 by sascha

almost periodic function ca classical analysis and odes ergodic theory fourier analysis real analysis

1 Asked on February 18, 2021 by mikhail-tikhomirov

Get help from others!

Recent Answers

- DMGregory on MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Justin Markwell on Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- kjetil b halvorsen on How to test consistency of responses?
- eric_kernfeld on How to test consistency of responses?
- Philipp on How do i draw a ray in unity

Recent Questions

- MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- How do i draw a ray in unity
- How to test consistency of responses?
- How can I understand these variograms?

© 2022 AnswerBun.com. All rights reserved.