快速幂的伽罗瓦域(Fast Exponentiation for galois fields)

我希望能够计算

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

其中g是在有限域GF（2 ^ M）。 这里m是相当大的，M = 256，384，512等中，从而查找表是不是解决办法。 我知道有非常快的算法类似的想法，modpow为Z / NZ（见619-620页HAC ）。

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

注：这是从我的岗位上math.stackoverflow.com我想这是要问这个问题最好的社区。

Answer 1:

从数学stackexchange社区，我有两个人建议二进制Exponentiaion 。 维基百科指出递归它作为一个递归算法。 如在Wiki的伪代码可以改为迭代算法。

我皱起了眉头，在起初的想法，但我看着它更多，我发现两篇论文（ 1 ， 2 ），可以帮助实现伽罗瓦域二进制幂使用蒙哥马利乘法。

此外， Jyrki Lahtonen使用正常的碱基（或当m = / = 256384，512，等等最佳正常碱基）以加速乘法建议。 乘法的这种方法的算法都可以在此找到文件 。

由于sarnold为他/她的输入。

文章来源: Fast Exponentiation for galois fields