Analysis of Modular Matrix Exponentiation

Question

I found this algorithm on Wikipedia

function Matrix_ModExp(Matrix A, int b, int c)
    if (b == 0):
        return I  // The identity matrix
    if (b mod 2 == 1):
        return (A * Matrix_ModExp(A, b - 1, c)) mod c 
    Matrix D := Matrix_ModExp(A, b / 2, c)
    return (D * D) mod c

Can anyone explain to me the correctness proof and its time complexity? Thanks

Answer 1

I do not know who first wrote this down, but: The algorithm uses simply the following properties of the power operation:

$$A^{0} = I$$ $$A^{n} = A\cdot A^{n-1}, \quad n \text{ odd}$$ $$A^{n} = A^{n/2} \cdot A^{n/2}, \quad n \text{ even} $$ The $\bmod c$ operation is defined element-wise.