Search code examples
mapleexponentiation

Fast modular exponentiation in Maple

What is the fast way to compute a power of a matrix of integers modulo a given integer?

I tried:

> M := Matrix([[1,1],[1,0]]); M ^ (10 ^ 12) mod 73;

but this was very slow, most probably Maple tried to to compute the power first (with huge numbers), and only then take the the modulo 73. How can I convince it to do the modulo for each multiplication?

Solution 
  • restart:

M := Matrix([[1,1],[1,0]]):

str:=time[real]():

LinearAlgebra:-Modular:-MatrixPower(73, M, 10^12);

                              [46  46]
                              [      ]
                              [46   0]

time[real]()-str;

                                0.040