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 页)。

什么是快速的、基于非表格的计算周期的方法(即 g^x)？

这绝对是一个一厢情愿的问题，但它来了:montgomery multiplication/exponentiation的想法可以吗？被“回收”到伽罗华域？由于同构特性，我想是这样，但我真的不知道。

备注:这是我的 post在 math.stackoverflow.com 上，我想这是提出这个问题的最佳社区。

Answer 1

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

起初我对这个想法皱眉，但我仔细研究了它，我发现了两篇论文( 1 ， 2 )可以帮助在使用蒙哥马利乘法的伽罗瓦域中实现二进制取幂。

此外，Jyrki Lahtonen建议使用正常基数(或当 m =/= 256,384、512 等时，最佳正常基数)来加速乘法。可以在此 paper 中找到此乘法方法的算法。 .

感谢 sarnold 的投入。