Fibonacci sequence digits

Question

We define the Fibonacci sequence by $F_{n+2}=F_{n+1}+F_{n}$, with $F_0=0$ and $F_1=1$.
How to compute the last $30$ digits of $F_{2^{200}}$ for instance? can we use Python?how?

Answer 1

We may use the Chinese remainder theorem and compute $F_{2^{100}}\pmod{5^{30}}$ and $F_{2^{100}}\pmod{2^{30}}$ by exploiting the properties of the associated Pisano periods (for instance, the period of the Fibonacci sequence $\pmod{5^n}$ is just $4\cdot 5^n$) or consider that it is simple to compute $(F_{2k},L_{2k})$ from $(F_k,L_k)$, since:

$$ F_{2k} = F_k L_k, \qquad L_{2k}=5 F_k^2+ 4(-1)^k. \tag{1}$$ $(1)$ gives that we just need to perform $200$ multiplications in $\mathbb{Z}/(10^{30}\mathbb{Z})$ to recover the last $30$ digits of $F_{2^{100}}$.