Bressoud & Wagon define MatrixPowerMod on page 34 of their book, A Course in Computational Number Theory.

    MatrixPowerMod[a_, n_, m_] :=
       Block[{b = a, d = IntegerDigits[n, 2]},
             Do[
                b = Mod[b.b, m];
                If[d[[i]] == 1, b = Mod[b.a, m]],
                {i, 2, Length[d]}];
             b]

An example involving Fibonacci numbers is the following

    AbsoluteTiming[MatrixPowerMod[{{0, 1}, {1, 1}}, 10^8, 10^10]]
    (* {0.005576, {{1300390626, 7760546875}, {7760546875, 9060937501}}} *)