Hi, hope you all have a good day (or a good night, it's midnight in my area lol). Recently I came across a problem, which takes two integers — n and m — as input, with 3 <= n, m <= 10^9. The problem asks for the value of F(F(i)) mod m, with F(i) denoting the i-th Fibonacci number. I'm not sure if this question has been asked before on any platform (though I'm pretty sure no one has asked about it on English Competitive Programming Forums), but this seems to be a direct application of the Pisano Period. However, I am only able to find an O(m^2) algorithm, which does not suffice the condition of this problem. Even though there seems to be a fast enough algorithm on mathoverflow, the writer explicitly stated that this algorithm may fail with specific prime numbers. So, my question is does there exist a precise method of calculating the pisano period of large number >= 10^9 ? Thanks in advance for your responses, I will really appreciate your helps.
Update: The problem of precisely calculating the pisano period for every number is in fact unsolved, since the existence of numbers that potentially break the properties are not yet proved.
Auto comment: topic has been updated by neverblunder (previous revision, new revision, compare).
There are two things that make this problem much simpler than answers on mathoverflow make it appear to be.
The first one is that you don't need to know the exact Pisano period $$$k(m)$$$, only something that is divisible by it. The following facts are well-known and give a simple algorithm that finds a small multiple of $$$k(m)$$$:
If $$$m$$$ and $$$n$$$ are coprime, then $$$k(mn) = \mathrm{lcm}(k(m), k(n))$$$
If $$$p$$$ is a prime, then $$$k(p^n)$$$ is a divisor of $$$p^{n - 1} \cdot k(p)$$$.
If $$$p > 5$$$ is a prime and $$$p \equiv \pm 1 \pmod 5$$$, then $$$k(p)$$$ is a divisor of $$$p - 1$$$.
If $$$p > 5$$$ is a prime and $$$p \equiv \pm 2 \pmod 5$$$, then $$$k(p)$$$ is a divisor of $$$2(p + 1)$$$.
Secondly, for small enough $$$m$$$, even finding $$$k(m)$$$ is not much of a problem. We already have a small multiple $$$\ell$$$ of $$$k(m)$$$. The Pisano period of $$$m$$$ is the smallest divisor $$$d$$$ of number $$$\ell$$$, such that $$$F_d \equiv F_0 \pmod m$$$ and $$$F_{d + 1} \equiv F_1 \pmod m$$$. This works as long as factoring $$$\ell$$$ and iterating over its divisors is fast enough, which is true for $$$m \leqslant 10^9$$$.
Thank you so much for your answer. The facts you provided are really helpful and sufficient that I got Accepted on the problem I was asking for :) This answer mentions that these facts will fail for Wall-Sun-Sun prime numbers, but according to Wikipedia, in reality no one has ever found any such number, and the existence of Wall-Sun-Sun prime numbers is in fact, as I understand, an unsolved problem in mathematics. So, I think I'd better just accept the facts and use them for the future :D
All the above facts are true for all primes uncoditionally, no strings attached. What is wrong for Wall-Sun-Sun primes (whose existence is unknown), is that $$$k(p^n)$$$ is exactly equal to $$$p^{n - 1} \cdot k(p)$$$. $$$k(p^n)$$$ being a divisor of $$$p^{n - 1} \cdot k(p)$$$ is true uncoditionally.
Yes, indeed. These properties should be enough on the basis of Competitive Programming, which doesn't require everything to be exact and precise (what I mean is that we don't even need to know the exact value of the Pisano period to be able to solve CP problems on this number). Even if Wall-Sun-Sun numbers do exist (which is completely out of my knowledge bound), the facts provided would be sufficient to solve problems relating to this field anyways :D Thanks for your time responding to this blog !
There is https://www.spoj.com/problems/PISANO/, which is solvable by simply implementing what's written in "Properties" section in Wikipedia.
Yes, indeed. But I think that since the existence of Wall-Sun-Sun prime numbers are unproven, these properties are not guaranteed to be precise for every number :D Anyways, I'm sorry for asking an unsolved problem here. I should have done more research :)
We are already more or less in the area where the theoretical lower bound for potential Wall-Sun-Sun primes is getting high enough to make them irrelevant for the version of the problem that you may face in competitive programming.
Also, like Kaban-5 pointed above, not relying on this property only adds a bit of complexity to the solution, but doesn't really make things change drastically.