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.
 A: 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$.

As for references:
Lucas sequences have been previously adopted for the needs of cryptography, providing an alternative to modular exponentiation, which most notably resulted in the LUC cryptosystem. It was however shown that many of the supposed security advantages of LUC over cryptosystems based on modular exponentiation are either not present, or not as substantial as claimed. You can find corresponding references in Wikipedia.
For a general theory of linear recurrences over rings, see

V. L. Kurakin, A. S. Kuzmin, A. V. Mikhalev, and A. A. Nechaev. Linear recurring sequences over rings and modules. Journal of Mathematical Sciences 76:6 (1995), 2793-2915.

