MatrixPower with Modulus

Using an undocumented function:

Algebra`MatrixPowerMod[{{2, 3, 1}, {5, 2, 4}, {0, 3, 2}}, 4, 6]

{{1, 0, 5}, {1, 1, 5}, {3, 3, 4}}

Mod[MatrixPower[{{2, 3, 1}, {5, 2, 4}, {0, 3, 2}}, 4], 6]

{{1, 0, 5}, {1, 1, 5}, {3, 3, 4}}

Unfortunately, the undocumented function does not support the action form of MatrixPower[].

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}}} *)