[engnr567]

The matrix exponentiation algorithm in the link you sent is O(log(n)). Yes, this might seem strange because the output (F_n) itself has n bits. But in practice most of the implementations would use long integers for output, so log(F_n) < 64 for these implementations.

[cousin_it]

The article I linked has code examples in four languages, all use bigints, not longs.