我希望能够计算
g^x = g * g * g * ... * g (x times)
其中 g 在有限域 GF(2^m) 中。这里 m 相当大,m = 256、384、512 等,因此查找表不是解决方案。我知道对于类似的想法有非常快速的算法,用于 Z/nZ 的 modpow(参见 HAC 的第 619-620 页)。
备注:这是我的 post在 math.stackoverflow.com 上,我想这是提出这个问题的最佳社区。
最佳答案
来自 math stackexchange社区,我有两个人建议Binary Exponentiaion .维基百科将递归称为递归算法。它可以更改为迭代算法,如 Wiki 的伪代码所示。
起初我对这个想法皱眉,但我仔细研究了它,我发现了两篇论文( 1 , 2 )可以帮助在使用蒙哥马利乘法的伽罗瓦域中实现二进制取幂。
此外,Jyrki Lahtonen建议使用正常基数(或当 m =/= 256,384、512 等时,最佳正常基数)来加速乘法。可以在此 paper 中找到此乘法方法的算法。 .
感谢 sarnold 的投入。
关于multiplication - 伽罗瓦域的快速求幂,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11623827/