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

Can you clarify your question, please. Currently it appears you are asking about the history of this algorithm, but it is unclear what you want to know about it. — BDN, Jun 25 '18 at 11:10
@BDN, I thought someone found it already through research, can anyone mention it? If no, there must be a correctness proof of this algorithm, isn't there? Hopefully, someone can also mention the compact analysis of this algorithm ;) — satriahrh, Jun 25 '18 at 11:19

score 1 · Answer 1 · answered Jun 25 '18 at 13:37

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.

answered Jun 25 '18 at 13:37

gammatester

18,827

I understand the $A^n$ when $n$ is odd, but how about $n$ is even? – satriahrh Jun 28 '18 at 08:55
If $n$ is even, then $\frac{n}{2}$ is an integer and therefore $$A^{n} = A^{(\frac{n}{2} + \frac{n}{2})} = A^{\frac{n}{2}} \cdot A^{\frac{n}{2}} $$ – gammatester Jun 28 '18 at 09:26
@ gammatester Ok I just realized how stupid I am. Thanks – satriahrh Jun 28 '18 at 10:21

Analysis of Modular Matrix Exponentiation

1 Answers1