The number of bits in Fib(n) is O(n), not O(log n).
Put differently, Fib(n) grows exponentially.
To be precise, Fib(n) = (phi^n - (-phi)^(-n)) / sqrt(5).
So the complexity to compute Fib(n) is O(n) time (or slower).
And one algorithm that runs this fast is to compute the n-th
power of [[1,1],[1,0]] (using repeated squaring and large integer arithmetic).