Computational Complexity of Modular Exponentiation and Matrix Modular Exponentiation

Question

Hi i need help with the complexity of this algorithms

Based on the algorithm of [Cor 2009], to calculate a ^ b mod n, where a, b and n are positive integers:

https://ibb.co/mFFk2m

1) What is the Complexity Complexity of this algorithm?

2) Write an algorithm where "a" is a square matrix ( Matrix_ModExp(Matrix a, int b, int c) ) and calculate the complexity of this algorithm

3) How Matrix Modular Exponentiation can be used to calculate the Fibonacci sequence when:

https://ibb.co/eRahF6

thx for any help, Regards

Answer 1

Well to answer your first question, the optimal input for 'b' would be a number that is a power of 2, in which case, the computational complexity would be $O(\log_2b)$. Your worst case is if 'b' is 1 less than a power of 2. In which case, you would subtract 1, divide by 2, subtract 1, divide by 2, etc. So it would still be $O(\log_2b)$, it's just that this time it's taking twice the amount of iterations so it'll be $O(2\log_2b)$.