1
$\begingroup$

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$?

$\endgroup$
0
$\begingroup$

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.$

$\endgroup$
6
  • $\begingroup$ Thanks! @Igor, I had figured how to compute "period" but I have difficulties on how to use period length to get fib(n) mod m. Also, I am not able to understand the relation between fib(n) and n (as mentioned in the question I don't understand why fib(2015) mod 3 = fib(7) mod 3 ). More code-oriented question is on StackOverflow(stackoverflow.com/questions/61706899/…) $\endgroup$
    – hack3r_0m
    May 10 '20 at 6:03
  • $\begingroup$ Wikiwand looks attractive but is it secure? When I attempted to add wikiwand to Chrome then I got a confusing message about wikiwand changing my data, etc. Does it do so under my control or without it? $\endgroup$
    – Wlod AA
    May 10 '20 at 8:24
  • $\begingroup$ Don’t use wikiwand. Not only is it unethical to drive traffic to a website that (albeit legally) just republishes content created by others with a dubious facelift instead of to the originating website, but more importantly, it defeats one of the major purposes of Wikipedia, “the free encyclopedia that anyone can edit”: no one cannot edit the copies at wikiwand. $\endgroup$ May 10 '20 at 8:58
  • $\begingroup$ @EmilJeřábek You are wrong. If you hover on "Wikipedia Tools" in the top right, one of these tools is "Edit". Clicking on it sends you to the standard Wikipedia editor. As for "unethical", I would like you to apologize - Wikiwand clearly makes no money, and neither do I. $\endgroup$
    – Igor Rivin
    May 10 '20 at 15:26
  • $\begingroup$ All right, so they do provide links to edit pages on Wikipedia. However, my first point stands. Wikiwand is a private for-profit company that (apart from angel investors) makes money from advertising on content they copy wholesale from Wikipedia (with which they are unaffiliated). I have nothing to appologize for. $\endgroup$ May 10 '20 at 19:15
0
$\begingroup$

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$).

$\endgroup$
3
  • $\begingroup$ Thanks, @Emil, I have computed period and length of period, as question says, how can I find fib(n) mod m using that period? and why fib(2015) mod 3 = fib(7) mod 3(for m=3 the period is 01120221 and has length 8 and 2015=251∗8+7)? $\endgroup$
    – hack3r_0m
    May 10 '20 at 7:00
  • $\begingroup$ I can read myself, thank you. I am telling you it is more efficient to not compute the period. $\endgroup$ May 10 '20 at 7:02
  • $\begingroup$ your answer doesn't explain why fib(2015) mod 3 = fib(7) mod 3(for m=3 the period is 01120221 and has length 8 and 2015=251∗8+7) $\endgroup$
    – hack3r_0m
    May 10 '20 at 7:04

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