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.



fibonacci series mod a number
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](http://en.wikipedia.org/wiki/Exponentiation_by_squaring) method often used in
[modular exponentiation](http://en.wikipedia.org/wiki/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$.


