# Complexity of a Fibonacci numbers discrete log variation

In my work I encountered the following

FIBMOD PROBLEM:
Given $k,m$ in binary, decide if there exists $n$ such that $\, F_n = k \,$ (mod $m$).
Here $F_n$ is a Fibonacci number.

This is a variation on the discrete log problem, but in a larger field. For example, let $m=p$ be a large prime. Then the problem is asking if there exists $n$ such that $\alpha^n + \beta^n = k$ (mod $p$), where $\alpha$ and $\beta$ are the roots of $\, x^2 - x - 1$. Note, however, that discrete log asks also to find $n$ which is potentially harder.

Questions:
0) Are there any references on this problem?
1) Is this problem in NP $\cap$ co-NP?
2) Is this problem in BQP?
3) Is there a reason to believe that FIBMOD is hard? For example is there a way to show that FIBMOD is DISCRETE-LOG - hard?

Note: Fibonacci numbers mod $m$ are periodic with period $\le 6 m$, as explained in this Pisano period Wikipedia article. Recall that Fibonacci numbers can be computed by taking powers of the matrix: $$\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix}$$ Using the Chinese Remainder Theorem this implies that FIBMOD is in NP.

• Not $\alpha^n+\beta^n$, but $(\alpha^n-\beta^n)/(\alpha-\beta)$. Dec 2, 2017 at 7:16
• What do you get for the question, given $k$ and $m$, decide whether there exists $n$ such that $2^n\equiv k\bmod m$? Dec 2, 2017 at 11:28
• @GerryMyerson -- I don't know, it's a good question. But I am specifically interested in the Fibonacci case. Dec 6, 2017 at 3:48
• Over the integers Fibonacci numbers are characterized as those $n$ for which $5a^2+4$ or $5a^2-4$ is a perfect square. Alternatively, those $a$ for which $a^2-ab-b^2=\pm1$ is solvable in integers. If we had similar characterizations (mod m), then Fibmod could be reduced to "quadratic residuosity" (asking whether something is a square mod m), which in turn is believed to be as hard as factoring (I believe it's only known that QR<Factoring). Dec 7, 2017 at 6:02
• Gjergji, this is an interesting idea. Looking at it the other way, if m=p is prime, such a characterization based on quadratic residuosity would imply that the problem is easy! Dec 11, 2017 at 6:59

The Binet formula for Fibonacci numbers is $$F_n = \frac{\phi^n - (-\phi)^{-n}}{\phi - (-\phi)^{-1}},\qquad\text{where}\ \phi:=\frac{1+\sqrt{5}}2.$$
Then the congruence $$F_n\equiv k\pmod{m}$$ reduces to a pair of quadratic equations (indexed by the parity of $$n$$): $$z^2 - k(\phi - (-\phi)^{-1})z - (-1)^n \equiv 0\pmod{m}$$ with respect to $$z:=\phi^n$$. So, if we can solve these quadratic equations (which is easy if $$m$$ is prime), then the problem reduces to the classic discrete log problem base $$\phi$$ modulo $$m$$.