伽罗瓦域的快速幂运算 [英] Fast Exponentiation for galois fields

问题描述

我希望能够计算

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

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

where g is in a finite field GF(2^m). Here m is rather large, m = 256, 384, 512, etc. so lookup tables are not the solution. I know that there are really fast algorithms for a similar idea, modpow for Z/nZ (see page 619-620 of HAC).

1. 什么是快速的，非基于表的周期计算方法(即g ^ x)?
2. 这绝对是一个一厢情愿的问题，但它来了:蒙哥马利乘法/求幂被回收"到伽罗瓦油田吗?由于同构属性，我想这样想，但我真的不知道.

1. What is a fast, non-table based way to compute cycles (i.e. g^x)?
2. This is definitely a wishful question but here it comes: Can the idea of montgomery multiplication/exponentiation be 'recycled' to Galois fields? I would like to think so because of the isomorphic properties but I really don't know.

备注:这是从我的

Remark: this is from my post on math.stackoverflow.com I suppose this is the best community to ask this question.

推荐答案

来自

From the math stackexchange community, I had two people suggest Binary Exponentiaion. Wikipedia states a recursive it as a recursive algorithm. It can be changed to an iterative algorithm as shown in the Wiki's psuedocode.

我一开始对这个想法不满意，但后来对其进行了深入研究，结果发现有两篇论文( 2 )可以提供帮助在使用蒙哥马利乘法的Galois字段中实现二进制幂运算.

I frowned at the idea at first but I looked into it more and I found two papers (1, 2) that can help implement binary exponentiation in Galois Fields that uses Montgomery Multiplication.

此外， Jyrki Lahtonen 建议使用普通底数(或当m =/= 256,384，512，等最佳法线基数)以加快乘法速度.可以在此纸张中找到这种乘法方法的算法.

Furthermore, Jyrki Lahtonen suggested using normal bases (or when m =/= 256,384, 512, etc. optimal normal bases) to speed up the multiplication. Algorithms for this method of multiplication can be found in this paper.

感谢sarnold的投入.

Thanks to sarnold for his/her input.

这篇关于伽罗瓦域的快速幂运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！