Question

Suppose you want to compute the nth Fibonacci number ${\mathbf{F}}_n$ , modulo an integer $\mathbf{p}$. Can you find an efficient way to do this?

Short answer

The final running time after computing each step of $\mathrm{fib}3$is $\mathrm{O}(\log \left(\mathrm{n}\right)*\mathrm{M}\left(\mathrm{logp}\right)).$

Step-by-step solution

Introduction

Fibonacci Series – This series can be defined as every element of the series is the sum of two previous number of the series. Series will start from $0\mathrm{and}1$.

nth Fibonacci number formulae

Matrix multiplication for ${\mathrm{n}}^{\mathrm{th}}$Fibonacci number is

$\left[\begin{array}{c}\mathrm{Fn}\\ \mathrm{Fn}+1\end{array}\right]={\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]}^{\mathrm{n}}\left[\begin{array}{c}\mathrm{F}0\\ \mathrm{F}1\end{array}\right]$

Let’s assume that the running time for multiplying matrix of $\mathrm{n}$-bit numbers is $\mathrm{x}\left(\mathrm{n}\right).$

By problem$0.4,\mathrm{fib}3$ involves$\mathrm{O}\left(\log \mathrm{n}\right)$ arithmetic operations for multiplication.

So,

For every arithmetic operation with $\mathrm{mod}\mathrm{p}$, then the answer of the final step is long as$\log \mathrm{p}$ bits.

Therefore, the final running time after computing each step of$\mathrm{fib}3$ is $\mathrm{O}(\log \left(\mathrm{n}\right)*\mathrm{M}\left(\mathrm{logp}\right)).$