伽罗瓦域的快速求幂

Question

我希望能够计算

g^x = g * g * g * ... * g     (x times)

其中 g 位于有限域 GF(2^m) 中。这里 m 相当大，m = 256、384、512 等，因此查找表不是解决方案。我知道有类似想法的快速算法，modpow for Z/nZ（参见HAC第 619-620 页）。

1. 什么是快速、非基于表格的计算周期的方法（即 g^x）？
2. 这绝对是一个一厢情愿的问题，但问题来了：蒙哥马利乘法/求幂的想法可以“回收”到伽罗瓦域吗？我想这样认为，因为同构特性，但我真的不知道。

备注：这是我在 math.stackoverflow.com 上的帖子，我认为这是提出这个问题的最佳社区。

Answer 1

在math stackexchange社区，我有两个人建议Binary Exponentiaion。维基百科将递归称为递归算法。它可以更改为迭代算法，如 Wiki 的伪代码所示。

一开始我对这个想法感到皱眉，但我进行了更多研究，发现两篇论文（1、2 ）可以帮助在使用蒙哥马利乘法的伽罗瓦域中实现二进制求幂。

此外，Jyrki Lahtonen建议使用普通碱基（或当 m =/= 256,384、512 等最佳普通碱基）来加速乘法。这种乘法方法的算法可以在本文中找到。

感谢 sarnold 的意见。