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
-
Fib (pisano of p/1 ) mod P. Eq1
-
Fib (pisano of p/2 ) mod P. Eq2
-
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
Best Answer
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$.