那么就可以通过多次对 加上 的倍数来降低 的次数

那么就可以通过多次对 加上 的倍数来降低 的次数。

问题转化成了快速地求 ，只要将 普通快速幂 中的乘法与取模换成 多项式乘法 与 多项式取模 就可以在 的时间复杂度内解决这个问题了。

发现若能将两边的 消去后得到多项式 满足 其中 为一个 的零矩阵。

假设我们要求 可以构造多项式 那么 ，而现在我们可将 写成 而其中零矩阵是没有贡献的，那么 。

但是注意矩阵乘法不满足消去律，此处我们定义矩阵 的特征多项式为 ，其中 为一个 的单位矩阵。Cayley-Hamilton 定理指出 ，我们观察 的形式较为特殊，为下 Hessenberg 矩阵，其特征多项式比起一般矩阵更容易计算。

我们关注 的第一行就是 已知，那么 可在 时间简单得到。求出 则可用快速幂和多项式取模与上述解释是一样的。该算法常数较大，使用生成函数可以得到一个常数更小的算法，见 一种新的线性递推计算方法。