18
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Not $\alpha^n+\beta^n$, but $(\alpha^n-\beta^n)/(\alpha-\beta)$. $\endgroup$
    – Fedor Petrov
    Commented Dec 2, 2017 at 7:16
  • 1
    $\begingroup$ What do you get for the question, given $k$ and $m$, decide whether there exists $n$ such that $2^n\equiv k\bmod m$? $\endgroup$
    – Gerry Myerson
    Commented Dec 2, 2017 at 11:28
  • $\begingroup$ @GerryMyerson -- I don't know, it's a good question. But I am specifically interested in the Fibonacci case. $\endgroup$
    – Igor Pak
    Commented Dec 6, 2017 at 3:48
  • 3
    $\begingroup$ 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). $\endgroup$
    – Gjergji Zaimi
    Commented Dec 7, 2017 at 6:02
  • 1
    $\begingroup$ 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! $\endgroup$
    – Victor Protsak
    Commented Dec 11, 2017 at 6:59

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .