枫树中的快速模幂

Question

计算给定整数矩阵的幂的快速方法是什么？

我试过：

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

但这是非常缓慢的，很可能枫树试图先计算功率(用巨大的数字)，然后才取模块73。我如何说服它为每一个乘法做模运算？

Answer 1

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