费马定理在矩阵幂运算中的应用

Question

就像我们在模指数运算中使用费马小定理一样，我想知道是否有一种类似的方法可以用于快速矩阵指数运算？我们可以将费马定理用于矩阵指数运算吗？如果不行，那么是否存在比指数的分治方法更快的方法？

- SlashGeek

---

实际上这是一个不错的编程算法问题。 - Miguel

Answer 1

我会查找 GNU Octave 的实现。 在那里，它会给出一些参考资料。 这里是一些链接：

• http://epubs.siam.org/doi/abs/10.1137/1020098
• http://www.cs.cornell.edu/cv/researchpdf/19ways+.pdf

- Miguel

---

我认为你误解了，OP并不是在询问如何计算exp(M)，而是在询问如何计算对某个整数取模的M^e。 - Daniel Fischer

正如DanielFischer所指出的那样，在模运算结果的上下文中，exp(M)似乎并不是太有用。 - user85109

实际上，这是Wikipedia文章中简单方法的一部分，但是是的，我误解了它。 :p - Miguel