5
$\begingroup$

Order of fibinacci modulo p, where p is a prime number 1 < p < 10^18.

What is most efficient way to find the Order of Fibonacci number modulo prime. I have come up with an algorithm which can find the Order of Fibonacci modulo P in efficient way.

My algorithm is based on below facts.

The Fibonacci Sequence Modulo m

• The Fibonacci sequence mod m will always contain 1, 2, or 4 zeros, no matter what the modulus is.

• So first find the Pisano period of the given prime and check the below conditions

  1. Fib (pisano of p/1 ) mod P. Eq1

  2. Fib (pisano of p/2 ) mod P. Eq2

  3. Fib (pisano of p/4 ) mod P. Eq3

So the answer will be MAX of (1,2,4) for which Value of above Equations are 0.

With above algorithm I can find the Order efficiently for 1 < P < 10^18, but is there any way we can find Order of Fibonacci for 1 < p < 10^100.

This is the problem I am talking about, which I have solved Z124 - Zeros in Fibonacci period

$\endgroup$
  • $\begingroup$ If you yourself have come up with an efficient algorithm for Fibonacci numbers modulo primes, what is your question, then? $\endgroup$ – Alex M. Aug 1 '16 at 16:15
  • $\begingroup$ @Alex M my algorithm works for p < 10^18. Here I am looking for an algorithm which works for large p < 10^100 $\endgroup$ – Lakshman Aug 1 '16 at 19:33
  • $\begingroup$ Since I find the question a bit confusing, let me see if I have understood it correctly: you do not want to compute $F_n \pmod p$, you want to compute the order of $F_n \pmod p$ in $\Bbb Z _p$. Is my understanding correct? $\endgroup$ – Alex M. Aug 1 '16 at 20:18
  • $\begingroup$ Yes, that is what I want. $\endgroup$ – Lakshman Aug 2 '16 at 1:16
  • 1
    $\begingroup$ Given that the discrete logarithm problem, i.e. finding the order of $a (\mod p)$ for some given $a$, is computationally hard, I wonder if the Fibonacci problem is not harder? $\endgroup$ – John M Aug 4 '16 at 5:45
1
$\begingroup$

The comment of user John M is exactly right. Any linear recurrence sequence $\{a_n\}$, i.e. a sequence satisfying for some fixed numbers $c_1,\ldots,c_k$ and some starting values $a_0,\ldots,a_{k-1}$ the relation $$a_n=c_{1}a_{n-1}+\cdots+c_ka_{n-k}$$ is periodic modulo $m$ for any natural number $m$ (it is easy to see this from the pigeonhole principle).

Finding the discrete logarithm of some fixed number $c$ modulo $p$ is the same thing as finding the period length of the sequence defined by $a_0=1$ and $$a_n=ca_{n-1}$$ Finding the so-called "Pisano period" of the Fibonacci numbers modulo $p$ is finding the period length of the sequence defined by $a_0=0$, $a_1=1$ and $$a_n=a_{n-1}+a_{n-2}$$ They are exactly the same class of problem.


In fact, since the Fibonacci numbers satisfy $$F_n=\frac{1}{\sqrt{5}}\left(\phi^n-\tau^n\right)\qquad \phi=\frac{1+\sqrt{5}}{2}\qquad \tau=\frac{1-\sqrt{5}}{2}$$ finding the period of the Fibonacci numbers modulo $p$ boils down to

  • determining whether $5$ is a quadratic residue modulo $p$ (and thereby finding whether $\sqrt{5}$ already exists in the finite field $\mathbb{F}_p$ or whether one must go to the finite field $\mathbb{F}_{p^2}$)

  • finding the order of $\phi$ and $\tau$ in the multiplicative group of that finite field (which are closely related since $\phi\tau=-1$)

which illustrates how it's even more closely related to the discrete logarithm problem that it may seem at first glance.


Fermat's little theorem really can be seen as saying $$a_{p-1}\equiv a_0\bmod p$$ for the sequence $a_0=1$, $a_n=ca_{n-1}$ (when $c\not\equiv 0\bmod p$), from which it follows as a consequence that the order of $c$ modulo $p$ must divide $p-1$. Analogously, it is a theorem that for the Fibonacci sequence $a_0=0$, $a_1=1$, and $a_n=a_{n-1}+a_{n-2}$, $$a_{p-\left(\frac{p}{5}\right)}\equiv a_0\bmod p$$ where $\left(\frac{p}{5}\right)$ is a Legendre symbol. This is a lemma that eventually leads to the conclusion that the period of the Fibonacci numbers modulo $p$ either divides $p-1$ when $p\equiv \pm1\bmod 10$ or divides $2p+2$ when $p\equiv \pm3\bmod 10$ (with $2$ and $5$ being special cases, as one can expect). However, just as with Fermat's little theorem and the discrete logarithm problem, knowing these divisibility facts doesn't help much in actually finding the period modulo $p$.


Summary: It is extremely reasonable to predict that for any linear recurrence whatsoever, there is no good algorithm, much less formula, for finding its period modulo $p$.

$\endgroup$
  • $\begingroup$ This is a nice exposition. $\endgroup$ – John M Aug 8 '16 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.