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:


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:


thx for any help, Regards


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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.