Skip to main content
2 of 2
please link to actual Wikipedia, not to third-party rip-offs
Emil Jeřábek
  • 47.3k
  • 4
  • 150
  • 209

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

Igor Rivin
  • 96.4k
  • 11
  • 153
  • 366