Finding where I am in a linear recurrence relation

Question

Suppose I have a linear recurrence relation $$a(n) = c_1 a(n-1) + \dots + c_k a(n-k) + d,$$ where the constants $c_1,\dots,c_k,d$ are given and the initial values $a(0),\dots,a(k-1)$ are given as well. Assume that all arithmetic is done over some finite field, say $GF(p)$ where $p$ is a large prime (i.e., everything is done modulo $p$).

Suppose I am given the value of $a(n)$, where $n$ is unknown. Can I efficiently recover $n$? Or, more precisely, suppose I am given $b$, with the promise that there exists some $n$ such that $b=a(n)$. Can I efficiently find some positive integer $n$ such that $b=a(n)$? (Any integer will do.)

Effectively, if you're given a value from somewhere in the sequence given by this recurrence relation, is there an efficient algorithm to recover the index of that element in the sequence? By efficient, you can substitute "polynomial time" or "feasible in practice" or something like that.

How does the complexity of this problem relate to the complexity of the discrete log problem? Are they of equivalent hardness? Can I use an algorithm for the discrete log problem to solve this problem, or might this problem be harder?

I know the answer will depend upon the particular recurrence chosen: for some it will be easy, for others it will be hard. Is there any way to characterize or classify for which recurrences this problem is hard? Maybe some criterion on $c_1,\dots,c_k,d$?

---

Note that the discrete log problem is a special case of this recurrence relation problem. In the discrete log problem, we are given $x,y$ where $y=x^n$, and the problem is to find $n$. This is an instance of the above recurrence relation problem, where the recurrence is $a(n)=x \cdot a(n-1)$, $a(0)=1$. Given $y$, asking for an index $n$ such that $y=a(n)$ is equivalent to asking for an integer $n$ such that $y=x^n$. So, the recurrence relation problem I'm asking about is in some sense a generalization of the discrete log problem. (Also, this implies that there exist recurrences where this problem is as hard as the discrete log, but it does not immediately suggest criteria for when that happens, nor whether there might be any case where this problem is harder than the standard discrete log.)

Answer 1

First of all, your linear recurrence relation is not exactly linear, it is affine. However, in general, it is not difficult to get rid of the constant term $d$.

To do this, define $A(n)=a(n)+t$, and choose $t$ to make sure that the constant term vanishes. This requires $t=(c_1+...+c_k)t+d$, clearly, this can be done unless $c_1+...+c_k=1$.

From now on, I assume that we have no constant term $d$. You want to recover a possible $n$ from a single value $a(n)$. As far as I know, there is no direct relation between this and discrete logarithms.

However, there is a direct relation to the discrete logarithm problem for a simple variant of your question, i.e. given $a(n), a(n-1), ..., a(n-k+1)$ recover $n$.

This variant is a classical question about LFSR (linear feedback shift register). Usually, people consider LFSRs modulo 2, but it is also possible to consider them modulo $p$ and this is precisely what we are doing here.

To the recurrence formula, you can associate a polynomial $P(x)=x^n-(c_n\cdot x^{(n-1)}+...+c_2\cdot x+c_1)$. If you associate to a state $a(1),...,a(n)$ the polynomial $a(1)+a(2)\cdot x+...+a(n)\cdot x^{n-1}$ then updating a state is simply multiplication by $x$ modulo $p$. If this polynomial is irreducible, then finding the correct power of $x$ is simply a discrete logarithm problem in $GF(p^n)$.

When $P(x)$ is not irreducible, you are in fact simultaneously computing the values modulo several irreducible polynomials (and the results are pasted together using the Chinese Remainder Theorem), so you can solve it by computing discrete logarithms in smaller fields.

Coming back to your original question, a equivalent formulation in terms of discrete logarithms is: given $x$ an integer modulo $p$ and an extension field $GF(p^n)$ find an arbitrary element $X$ in $GF(p^n)$ represented by a polynomial whose constant term is $x$, together with a logarithm of $X$.