multiplication - 伽罗瓦域的快速求幂

Question

我希望能够计算

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

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

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

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

Answer 1

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

起初我对这个想法不以为然，但我仔细研究了一下，发现了两篇论文（1、2），它们可以帮助在使用蒙哥马利乘法的伽罗瓦域中实现二进制取幂。

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

感谢 sarnold 的意见。