fibonacci series mod a number - MathOverflow

fibonacci series mod a number

2010-10-02T05:18:35Z

I'm trying to write a program with an input of numbers $n$ and $k$ (where $n<10^{1000}$ and $k<10^9$), where I compute fib[n] % k. What is a good FAST way of computing this?

I realize that the resulting series is periodic, just not sure how to find it efficiently.

Answer by Robin Chapman for fibonacci series mod a number

2010-10-02T06:51:18Z

This is really just an expansion of Gerhard's comment. One has the matrix formula $$\begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}^n= \begin{pmatrix} F_{n+1}&F_n\\ F_n&F_{n-1} \end{pmatrix} $$ so the problem reduces to computing $A^n$ modulo $k$ where $$A=\begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}.$$ This can be done by the repeated squaring method often used in modular exponentiation. The idea is to compute $A^n$ recursively either as $(A^m)^2$ or $A(A^m)^2$ according to whether $n=2m$ or $n=2m+1$.

Answer by Andreas Rüdinger for fibonacci series mod a number

2010-11-07T17:19:14Z

Perhaps Elsenhans, Jahnel, "The Fibonacci sequence modulo $p^2$ – An investigation by computer for $p < 10^{14}$" http://www.uni-math.gwdg.de/tschinkel/gauss/Fibon.pdf will be interesting for you. There are sections about the algorithm.