二进制域乘法和求模快速算法.pdf

乘法运算的一种新方法

在二进制域GF（2）内两元素A，B的乘法运算最常用的是传统的n

“移位相加”算法。通常传统的方法移位操作会产生2s（n-1）位的

中间结果，其中n是比特数。

我们的算法试图减少占计算消耗很大一部分的移位操作的数量。我们

的方法需要2s（w-1）位的移位中间结果，其中w是处理器字长，s=n/w。

这能很大的有助于性能提升，尤其对于小字长的处理器。值得注意的

是域加法的数量依然和传统方法相同，虽然它依赖于被乘数的汉明重

量（哈明权，指其中非零元素的个数）。由于二进制域GF（2）中的

加操作不包含进位，所以将其定义为异或操作，我们的新算法使节省

移位操作成为可能。

有效的域乘法算法

定义1.B=（b…bb）作为乘数B的比特串表示，B可以被分成s

sw-110

块，每块长w位，s=n/w。表示t=A*b*x,i∈{0,1…n-1}。i

ii

域乘法的结果

可以被表示为C

有效的域乘法基于下面的计算模型，首先计算中间结(t,t…t)，

0w(s-1)w

然后依次计算(t,t…t)，直到(t,t…t),将所有的中

1w+1(s-1)w+1w-12w+1(s-1)w+(w-1)

间结果都计算出来。

算法1.LeftShift(x)表示多项式X的系数表示（字节串）左移一位，

C[j]表示多项式C的系数表示的第j个字，其中j∈{0…(s-1)}.

模约减

域乘法的结果需要2*sw位的存储空间。模约减通过不可约多项式（如

三项式和五项式）的移位和加法可以高效实现。这个想法是使高位为

零然后加上移位后的每一项的系数。Schroeppel等人描述了一种实用

的方法来实现多项式的模约减，那就是分组计算，每次计算一个字长。

n

对于x+x+1类型的三项式模，使n=167,k=6。每当域乘法或平方运

1676

算后都要对结果求模F(x)=x+x+1。

两个次数166的多项式乘积是一个次数为332的多项式。假设需要约

减的多项式为：

1676

模x+x+1的计算需要对每一项求模然后再从结果中减去。可见

由高位到低位每次取一个字节进行降次运算，这里取s/2个字，每次

降次s/2。为了使运算有效，三项式次数要尽量小。

算法2A表示将要进行求模运算的域乘法或平方运算的结果，A的

次数最多为2n-2。将A分成2s组，每组长w位。用A表示域元素

i

的第i组。函数CarryRightShift(Q,d,T)表示将Q右移d位，利用带进

位指令有效的移位操作，进位部分存储在T中。Temp1和Temp2是

w位的寄存器。以下算法表示对A求三项式模