Bit complexity of $n$-th Fibonacci number using matrix multiplication
Let us recall that
$$
F_n
=
\begin{pmatrix} 0 &amp; 1 \end{pmatrix}
\begin{pmatrix}
1 &amp; 1 \\
1 &amp; 0
\end{pmatrix}^n
\begin{pmatrix}
1 \\ 0 \end{pmatrix}.
$$
We compute the $n$-th Fibonacci number using the method of repeated squaring, applied to the $2\times 2$ matrix. The matrices encountered during this process are all of the form
$$
A_m = \begin{pmatrix} 1 &amp; 1 \\ 1 &amp; 0 \end{pmatrix}^m =
\begin{pmatrix}
F_{m+1} &amp; F_m \\ F_m &amp; F_{m-1}
\end{pmatrix}.
$$
Repeated squaring runs in $\ell \approx \log n$ steps. In the $t$-th step, we square a matrix $A_m$ with $m = \Theta(2^t)$, and possibly multiply it by the base matrix. Since the entries of $A_m$ are $\Theta(m)$ bits long, squaring takes $\Theta(m\log m) = \Theta(2^tt)$ bit operations, and this is the dominant operation in the $t$-th step. The overall bit complexity is thus proportional to
$$
\sum_{t=1}^{\ell} 2^tt = \Theta(2^\ell \ell) = \Theta(n\log n).
$$