Given a prime $p$ and a Fibonacci number $(F_n \bmod{p})$, how fast can you find $n$?
- Obvious Answers
- If you are given $F_n$ without reducing $(\bmod{p})$ you can solve the problem in O(log n).
- The "bruteforce" solution is as hard as computing the discrete logarithm in $\mathbb{F}_p$.
- Further Assumptions
- We can assume that $n$ is smaller than the Pisano period.
- We can assume that $x^2-x-1$ has roots in $\mathbb{F}_p$ and the Pisano period is known.
- We can assume that $F_{n+1}$ is given, too.
- We can reduce the problem to any of the following decision problems:
- Given that $n$ is even, is $n$ divisible by $4$?
- Is $n<\frac{p}{2}$ ?