12
$\begingroup$

I have a matrix that will be multiplied with itself by an extremely large amount of times under $Z/pZ$. The matrix itself contains small numbers, so MatrixPower[Mod[mat, p], pow, vec] won't work; and taking $\bmod$ after calculation is infeasible since the result is extremely large. Can I have similar functionality like some other function's Modulus -> p with MatrixPower?

$\endgroup$

2 Answers 2

13
$\begingroup$

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[].

$\endgroup$
4
  • $\begingroup$ This is exactly what I want, PE502 part 2 solved:) $\endgroup$
    – vapor
    Aug 5, 2016 at 13:10
  • $\begingroup$ Another one for (805). @happyfish There are over 500 PE problems now? That's a lot to work through! I stopped when there were only 330 or so, and I was getting repeatedly stumped by ones in the 130's. How many have you solved? $\endgroup$
    – Mr.Wizard
    Aug 5, 2016 at 13:26
  • 2
    $\begingroup$ @Mr.Wizard I have done nearly 200, most of them are simple ones. But 502 is on the top of their difficulty list and I am nearly done :) $\endgroup$
    – vapor
    Aug 5, 2016 at 16:29
  • 1
    $\begingroup$ This function also support negative exponent (modular inverse). $\endgroup$
    – user202729
    Jan 2, 2020 at 1:53
5
$\begingroup$

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}}} *)
$\endgroup$
1
  • 2
    $\begingroup$ This is, of course, the "Russian peasant" algorithm for exponentiation. Here is a compact implementation: Fold[Mod[If[#2 == 1, a.#, #].#, m] &, a, Rest[IntegerDigits[n, 2]]]. $\endgroup$ Aug 6, 2016 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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