Fast exponentiation

Modulo Fibonacci numbers To efficiently find the Fibonacci number, we use matrix multiplication, more details here. Knowing that \(F_{n+m} = F_m F_{n+1} + F_{m-1} F_n\), write the recurrence relation for matrix product: • if \(m = n\) then \(F_{2n} = F_n F_{n+1} + F_ {n-1} F_n\); • if \(m = n + 1\) then \(F_{2n+1} = F_{n+1 } F_{n+1} + F_n F_n\). Training problem **Fibonacci numbers modulo (C++)

To efficiently find the Fibonacci number, we use matrix multiplication, more details here.

Knowing that

\(F_{n+m} = F_m F_{n+1} + F_{m-1} F_n\), write the recurrence relation for matrix product:

• if \(m = n\) then \(F_{2n} = F_n F_{n+1} + F_ {n-1} F_n\);

• if \(m = n + 1\) then \(F_{2n+1} = F_{n+1 } F_{n+1} + F_n F_n\).