Compute the Googolplex-th Fibonacci number modulo $10^9+7$

Question

Is it possible to find this in a reasonable amount of time? The best theoretical approach that I’m aware of is using the Fibonacci Matrices, but even at a complexity of $O(\log n)$, the logarithm of a googolplex is already huge. Is there a more efficient algorithm to solve this? Can Binet's formula be used in some manner?

Answer 1

Since $5$ is not a square mod $p = 10^9 + 7$, the Pisano period of $p$ must be a divisor of $p^2 - 1$. By factoring $$p^2 - 1 = \left(2\right)^{4} \left(3\right)^{2} \left(7\right) \left(109\right)^{2} \left(167\right) \left(500000003\right)$$ and computing $$ \pmatrix{1 & 1\cr 1 & 0}^k \mod p$$ for various factors, we find that the Pisano period is $(p^2-1)/500000003 = 2000000016$, call this $q$. Now a googolplex is $10^{10^{100}}$, and $10^{10^{100}} \mod q = 408188512$. Thus $$F_{googolplex} \equiv F_{408188512} \equiv 719159693 \mod p$$