Pisano Period of Large Numbers

Revision en1, by neverblunder, 2020-10-10 20:10:00

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 \leq n \leq 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 (but 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, there said that this algorithm may fail with specific prime numbers. So, my question is does there exist a precise method to calculate the pisano period of large number \geq 10^{9} ? Thanks in advance for your responses, I will really appreciate your helps.

Tags #math, fibonacci, pisano

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English neverblunder 2020-10-10 21:28:16 4 Tiny change: 'r helps.\n**Update' -> 'r helps.\n\n\n**Update'
en6 English neverblunder 2020-10-10 21:27:38 195
en5 English neverblunder 2020-10-10 20:25:50 15 Small grammatical changes
en4 English neverblunder 2020-10-10 20:25:06 5 Tiny change: 'eger), there said that' -> 'eger), the writer said that'
en3 English neverblunder 2020-10-10 20:17:14 2 Tiny change: 'd an `O(m^{2})` algorit' -> 'd an `O(m^2)` algorit'
en2 English neverblunder 2020-10-10 20:13:32 44 Tiny change: 'Hi, hope y' -> '``Hi, hope y' (published)
en1 English neverblunder 2020-10-10 20:10:00 1096 Initial revision (saved to drafts)