# Fibonocci

First check that -
$$
\begin{bmatrix}
F_{i}\\
F_{i-1}
\end{bmatrix}=\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}\begin{bmatrix}
F_{i-1}\\
F_{i-2}
\end{bmatrix}
$$

Hence,

$$
\begin{bmatrix}
F_{i}\\
F_{i-1}
\end{bmatrix}=\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^i
\begin{bmatrix}
F_{0}\\
F_{-1}
\end{bmatrix}
$$

Now, notice that if $F_1=F_2=1$, then $F_0=0$ and $F_{-1}=1$.

Compute $\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^i \ mod \ 2^{128}$ using exponentiation by squaring. This can be done reading the input $i$ from the most significant bit to the least significant bit. Then do the matrix multiplication mod $2^{128}$. Hence the complexity is $O(n)$