Lets start with the understanding that Fn = Fn-1 + Fn-2
Consider this beautiful matrix
Lets multiply it with a matrix and see what we get. Here x, y, z are three consecutive fibonacci numbers such that z > y > z.
|z y| |1 1|
|y x| |1 0|
The resulting matrix is
| x+y y+0|
Here z+y is the newest addition to the series! Note that, x+y = z. We have basically created a new matrix but with the same quality of three consecutive fibonaccis.
Considering first three fibs are 0,1,1 - we just need to multiply following matrix as many times as needed with itself to get our result:
Square it and we get 4th fib. Cube it and we get 5th fib.
Now suppose you want me to find out the fib number 36. How much effort will I take?
Matrix square will give me 4th fib.
The above matrix square gives power of 4 -> 6th fib.
The above matrix square will give power of 8 -> 10th fib.
Square of above will give power of 16 -> 18th fib
Square of above will give power of 32 -> 34th fib.
Multiply above with what we got in step number 2 i.e. power of 34 -> 36th fib.
This happens in just 6 steps!
The compexity is visibly O(logn)
Hope it helps!