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.

1more comment