For a given value of $n$ and $m$, find $\text{fib}(n)$ $\text{mod } m$ where $n$ is very huge. (Pisano Period) [closed]

Question

Input

Integers $'n'$ (up to $10^{14}$) and $'m'$(up to $10^3$)

Output

$\text{Fib}(n)$ $\text{modulo}$ $m$

My questions

For example : Why $\text{fib}(n=2015)$ $\text{mod}$ $3$ is equivalent to $\text{fib}(7)$ $\text{mod } 3$? (for $𝑚 = 3$ the period is $01120221$ and has length $8$ and $2015=251*8 + 7$)

In general, after getting the remainder sequence, how (mathematical proof) it is used for computing $\text{Fib}(n)$ $\text{mod } m$?

Answer 1

The wikipedia article is quite enlightening on the Pisano period, but from the algorithmic viewpoint, it shows that you only need to compute the period for $n$ a prime power $p^k,$, and in that case it divides either $p^{k-1}(p-1)$ or $p^{k-1}2(p+1).$ For your range of $n$ brute force will tell you the period quickly, by computing the multiplicative order of $\begin{pmatrix}0&1\\1&1\end{pmatrix}$ modulo $n.$

Answer 2

From an algorithmic viewpoint, you can compute $F_n\bmod m$ efficiently in time $\tilde O\bigl((\log n)(\log m))$ [or $O\bigl((\log n)(\log m)^2)$ when employing a naive schoolbook multiplication algorithm] by computing

$$\begin{pmatrix}1&1\\1&0\end{pmatrix}^n\begin{pmatrix}1\\0\end{pmatrix}\bmod m$$

where the matrix power is evaluated by repeated squaring modulo $m$. Stated in a different way, this amounts to using the recurrences

$$\begin{align*} F_{2n-1}&=F_n^2 + F_{n-1}^2,\\ F_{2n}&=(2F_{n-1}+F_n)F_n \end{align*}$$

modulo $m$.

In contrast, I don’t think there is any known method to compute the Pisano period faster than factorizing $m$ (which takes exponential time $O\bigl(2^{(\log m)^\alpha}\bigr)$ for some $\alpha>0$).