MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## fibonacci series mod a number

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.

-
If k has no large prime or large prime power factors, then brute force combined with the Chinese Remainder Theorem will get you somewhere quickly. Otherwise use recursions to do the Fibonacci series mod k, to compute e.g. F(2j) and F(2j+1) mod k from F(j) and f(j+1) mod k. If n and k satisfy the bounds you say, a reasonably coded laptop can give you the answer in seconds or less. Gerhard "Ask Me About System Design" Paseman, 2010.10.01 – Gerhard Paseman Oct 2 2010 at 6:11
The Fibonacci entry in wikipedia has this identity : $F_{lk+c} = \sum_{i=0}^l {l\choose i} F_{c-i} F_k^i F_{k+1}^{l-i}$. It definitely seems to be relevant in your case, where write $n=lk+c$ and then you have to know $F_j$ mod $k$ for $j=1,\ldots,k+1$ as well as ${l\choose i}$ mod $k$. I don't know if this is efficient enough. – Somnath Basu Oct 2 2010 at 6:19

-