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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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[].
answered Aug 5, 2016 at 13:04
J. M.'s missing motivation♦J. M.'s missing motivation
125k11 gold badges407 silver badges581 bronze badges
-
$\begingroup$ This is exactly what I want, PE502 part 2 solved:) $\endgroup$– vaporCommented Aug 5, 2016 at 13:10
-
-
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$– vaporCommented Aug 5, 2016 at 16:29
-
1$\begingroup$ This function also support negative exponent (modular inverse). $\endgroup$ Commented Jan 2, 2020 at 1:53
$\begingroup$
$\endgroup$
1
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}}} *)
-
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$ Commented Aug 6, 2016 at 15:21