Constant time fibonacci is derived as an example for linear basis change in the superb book "Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach".

It's all contained in the sample pages http://matrixeditions.com/VC5.Chap2.219-221.pdf

However, even though the formula is O(1), the runtime of the algorithm might be larger.

Simply because a standard 64bit integer might be too small. And the BigNum implementation needs more time to multiply all the bits.