Skip to main content
added 88 characters in body
Source Link
Emil Jeřábek
  • 47.3k
  • 4
  • 150
  • 209

From an algorithmic viewpoint, you can compute $F_n\bmod m$ efficiently in time $\tilde O\bigl((\log n)(\log m))$ (or[or $O\bigl((\log n)(\log m)^2)$ when employing a naive schoolbook multiplication algorithm)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 using subexponentialfaster than factorizing $m$ (which takes exponential time $O\bigl(2^{(\log m)^\alpha}\bigr)$ for some $\alpha>0$).

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 using subexponential time.

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

Source Link
Emil Jeřábek
  • 47.3k
  • 4
  • 150
  • 209

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 using subexponential time.