# Finding where I am in a linear recurrence relation

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.)

-
 Some ideas I've thought about that don't seem to lead anywhere: write a matrix that expresses $x(n)=(a(n),\dots,a(n-k+1),1)$ in terms of $x(n-1)$, then reduce to a previous question I asked about matrices; compute the characteristic polynomial $p(t)$, then try working in $GF(p)(t)/(p(t))$; write a generating function for $a(\cdot)$, and use the characteristic polynomial $p(t)$ to express $a(n)$ as a weighted sum of $\alpha_i^n$, for some $\alpha_1,\dots,\alpha_k$ (if $p(t)$ has no repeated roots). None of these seem to get me anywhere. Any ideas? – D.W. Oct 24 '12 at 20:21