Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
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

1 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$.

share|improve this answer
    
Thinking again about the constant term removal issue, it appears that it can also be done when c1+...+ck=1 For this, define A(n)=a(n)+t1 n+t0 and choose t1 and t0 to make the constant d vanish. –  minar Jul 4 '13 at 4:38
    
Why there is a need to recover $d$ ? $d$ is already given –  curious Aug 1 '13 at 13:07
    
@curious The need is to remove $d$ to make the equation linear (not to recover $d$ it is indeed already known). –  minar Aug 1 '13 at 15:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.