Fibonacci series mod a number I'm trying to write a program with an input of numbers $n$ and $k$ (where $n<10^{20}$ and $k<10^9$), where I compute fib[n] % k.
What is a good FAST way of computing this? 
I have read many articles on this topic. At first I wanted to use a Pisano period. However, there is no formula to calculate the Pisano period.
Then I wanted to calculate Fibonacci number. However, it does not fit into any type of standard data type (Fibo(1000000000000000000) has about 208987640249978720 decimal). 
I see this 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}
$$
However, according to the second issue, I can not save the result. 
I feel that I am missing some theory. I'll be glad for any help.
 A: The fastest way is somewhere around $O(\log^2 n)$. It is highly related to the matrix, but uses a little "recycling". This examples how to find $F_k$ I will explain the modding last.
Take note of these basic properties of Fibonacci numbers:


*

*$F_{2k+1} = 4F_k^2 - F_{k-1}^2 + 2(-1)^k$

*$F_{2k-1} = F_k^2 + F_{k-1}^2$

*$F_{2k} = F_{2k+1} - F_{2k-1}$


With these properties we can double the position of a Fibonacci number's index, instead of going one by one, which makes it so much faster.
Steps:


*

*Convert the $n$ (as in $F_n$) to binary. Ex: The $11th$ Fibonacci number, so $11$ in binary is $1011_2$ 

*Have $F_0 = 0$ and $F_1 = 1$, and let $k = 1$ to start. Lastly start from the $2nd$ binary digit place from the left. In this case it is the $0$.

*Calculate $(F_{2k-1}, F_{2k},F_{2k+1})$ using the formulas listed above.

*If the digit place is $0$ use $(F_{2k-1}, F_{2k})$, if it is odd use $(F_{2k},F_{2k+1})$ for the next values you substitute for $(F_{k-1},F_k)$. Now shift the digit place one to the right.

*Repeat steps 3-4 until all the digits places are gone, and you will get your final Fibonacci number which will end up being whatever value you end up for your next $F_k$.


Example:


*

*To find $F_{13}$, $n = 13$ in binary is $1101_2$

*Starting from $(F_0,F_1) = (0,1)$, the next value sets are: $(1^2+0^2,F_{2k+1}-F_{2k-1},4(1)^2-0^2-2) = (1, 2-1, 2) = (1,1,2)$

*Because the $2nd$ digit from the left is a $1$, we will use $(1,2)$ for our next values.

*Next values: $(5,8,13)$. $3rd$ digit from the left is a $0$ so we use (5,8).

*Next values: $(89,144,233)$. $4th$ digit form the left is a $1$ so we use $(144,233)$, but that was the last digit place, so our answer is $F_k$, which is $233$.


Optimizations: 


*

*Calculate $F_k^2$ and $F_{k-1}^2$ first. Perform the mod after calculating them, then recycle them when
calculating $F_{2k+1}$ and $F_{2k-1}$. This ensures that multiplication is at most $\log_2 m + 2$ digits long. Where $m$ is the modulus.

*Because $2(-1)^k$ is $-2$ when $k$ is odd, and $+2$ when $k$ is even, Whatever digit place read to determine what values to use for $(F_{k-1},F_k$), also predicts which $+2$ or $-2$ to use. So in our example because we read a $1$ in the $2nd$ place, we would use $-2$ for the next $2(-1)^k$. And because we read a $0$ in the $3rd$ place, we would use $+2$ for the $2(-1)^k$ after. So use a $+2$ if you read a $0$, and use $-2$ if you read a $1$.

