9
$\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$
11
$\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$
  • $\begingroup$ This is exactly what I want, PE502 part 2 solved:) $\endgroup$ – happy fish Aug 5 '16 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 '16 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$ – happy fish Aug 5 '16 at 16:29
4
$\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
    $\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$ – J. M. is away Aug 6 '16 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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