一种基于串并结合实现有限域乘法的方法及装置

摘要

本发明公开了一种基于串并结合实现有限域乘法的方法及装置，所述方法包括：对m位的乘法因子A按从低位到高位进行分组，以k位为一组，分为p组，分组后的各组表示为ei，其中i＝0，1，...，p-1；将e0与乘法因子B进行有限域内的乘法运算，得到D0；将D′0作下一步中的C′1输出；对乘法因子B进行有限域内左移k位操作，得到E1；将ej与Ej进行有限域内乘法运算，得到D′j；将D′j与C′j进行有限域内的加法运算，得到C′j+1；将Ej进行有限域内左移k位操作，得到Ej+1；其中，j＝1，2，3...p-2；将ep-1与Ep-1进行有限域内乘法运算，得到D′p-1；将D′p-1与C′p-1进行有限域内的加法运算，得到C′p；输出C′p即为乘法因子A和乘法因子B在有限域内的乘积。本发明的技术方案能提高有限域乘法的运算效率。

权利要求

1.一种基于串并结合实现有限域乘法的装置，该装置用于实现有限域内m位乘法因子A和m位乘法因子B的相乘运算，其特征在于，包括：输入模块，分组模块，输出模块，p个PM模块，其中，PM模块包括改进的Arash乘法器模块；这p个PM模块分别为：PM1模块、PM2模块、…、PMp模块；

输入模块，用于将m位乘法因子A发送给分组模块，将m位乘法因子B发送给PM1模块；

分组模块，用于接收输入模块发送的乘法因子A，将乘法因子A从低位到高位进行分组操作，以k位为一组，分成p组，分组后的各组表示为ei，将ei依次发送给相应的PMi+1模块；

其中 ，i=0,1，...，p-1；其中，最高位ep-1不足k位时，将不足的位数进行补0操作，补成k位； 表示向上取整函数；

PM1模块，用于接收分组模块发送的e0，以及输入模块发送的乘法因子B；将e0和B进行有限域内的乘法运算，得到D'0；将D'0作为C'1发送给PM2模块；将乘法因子B进行有限域

1 1

内左移k位操作，得到E，将E 发送给PM2模块；

j j

PMj+1模块，用于接收分组模块发送的ej，以及PMj模块发送的E 与C'j；将ej与E 进行有限域内的乘法运算，得到D'j；将D'j与C'j进行有限域内的加法运算，得到C'j+1，将C'j+1j j+1 j+1发送给PMj+2模块；将E 进行有限域内左移k位操作，得到E ，将E 发送给PMj+2模块，其中，j=1,2,3…p-2；

p-1

PMp模块，用于接收分组模块发送的ep-1，以及PMp-1模块发送的E 与C'p-1；将ep-1与p-1E 进行有限域内乘法运算，得到D'p-1，将D'p-1与C'p-1进行有限域内的加法运算，得到C'p，将C'p发送给输出模块；

输出模块，用于接收PMp模块发送的C'p，将C'p输出；

所述改进的Arash乘法器模块包括：左移位模块，矩阵列截短模块，矩阵相乘模块，右移位模块，矩阵行列截短模块，矩阵简化模块，二元异或门列模块；其中，j左移位模块，用于接收输入模块发送的乘法因子B或读取寄存器Zj存储的E，将获取到的操作数进行m次左移位操作，得到m行m列的矩阵Lm，m，将所述矩阵Lm，m发送给矩阵列截短模块；

矩阵列截短模块，用于接收左移位模块发送的矩阵Lm，m，将所述矩阵Lm，m进行矩阵列截短操作，得到m行k列的矩阵Lm，k；将矩阵Lm，k发送给矩阵相乘模块；

j

右移位模块，用于接收输入模块发送的乘法因子B或读取寄存器Zj中存储的E，将获取到的操作数进行m-1次右移位操作，得到m-1行m列的矩阵Um-1，m，将所述矩阵Um-1，m发送给矩阵行列截短模块；

矩阵行列截短模块，用于接收右移位模块发送的矩阵Um-1，m，将所述矩阵Um-1，m进行矩阵行列截短操作，得到k-1行k列的矩阵Uk-1，k；将矩阵Uk-1，k发送给矩阵相乘模块；

j

矩阵相乘模块，用于将矩阵列截短模块发送的与E 相对应的左移矩阵Lm，k和分组模块发送的ej进行相乘运算，得到Lm，k×ej；将Lm，k×ej发送给二元异或门列模块；用于将矩阵行j列截短模块发送的与E 相对应的右移矩阵Uk-1，k和分组模块发送的ej进行相乘运算，得到Uk-1，k×ej；将Uk-1，k×ej发送给矩阵简化模块；

矩阵简化模块，用于接收矩阵相乘模块发送的Uk-1，k×ej，将Uk-1，k×ej化简成m列1行的矩阵Rm，1；将矩阵Rm，1发送给二元异或门列模块；

二元异或门列模块，用于接收矩阵相乘模块发送的Lm，k×ej和矩阵简化模块发送的相对应的矩阵Rm，1；将Lm，k×ej与Rm，1进行异或操作，得到D'j，将D'j输出。

2.根据权利要求1所述的装置，所述PM1模块包括：改进的Arash乘法器模块，移位模块，寄存器Z1，寄存器C1；其中，改进的Arash乘法器模块，用于接收输入模块发送的乘法因子B，分组模块发送的e0；

将B与e0进行有限域内的乘法运算，将得到的相乘结果D'0作为C'1发送寄存器C1；

移位模块，用于接收输入模块发送的乘法因子B，将乘法因子B进行在有限域内左移k

1 1

位操作，得到E，将E 发送给寄存器Z1；

1

寄存器Z1，用于存储移位模块发送的E ；

寄存器C1，用于存储改进的Arash乘法器模块发送的C'1。

3.根据权利要求1所述的装置，所述PMj+1模块包括：改进的Arash乘法器模块，移位模块，异或阵列模块，寄存器Zj+1，寄存器Cj+1；其中，j j

改进的Arash乘法器模块，用于从寄存器Zj中读取E，接收分组模块发送的ej，将E 与ej进行有限域内的乘法运算，得到D'j；将D'j发送异或阵列模块；

j j j+1

移位模块，用于读取寄存器Zj中的E，将E 进行有限域内左移k位操作，得到E ，将j+1E 发送给寄存器Zj+1；

异或阵列模块，用于读取寄存器Cj中的C'j，接收改进的Arash乘法器模块发送的D'j；

将C'j与D'j进行有限域内的加法运算；得到C'j+1，将C'j+1发送给寄存器Cj+1；

j+1

寄存器Zj+1，用于存储移位模块发送的E ；

寄存器Cj+1，用于存储异或阵列模块发送的C'j+1；

其中，j=1,2,3…p-2。

4.根据权利要求1所述的装置，所述PMp模块包括：改进的Arash乘法器模块，异或阵列模块，寄存器Cp；其中，p-1

改进的Arash乘法器模块，用于从寄存器Zp-1中读取E ，接收分组模块发送的ep-1，将p-1E 与ep-1进行有限域内的乘法运算；得到D'p-1，将D'p-1发送异或阵列模块；

异或阵列模块，用于从寄存器Cp-1读取C'p-1，接收改进的Arash乘法器模块发送的D'p-1；将C'p-1与D'p-1进行有限域内的加法运算，得到C'p；将C'p发送给寄存器Cp；

寄存器Cp，用于存储异或阵列模块发送的C'p。

5.根据权利要求1所述的装置，其特征在于，所述矩阵相乘模块包括m+k-1个MTP单元：其中的m个MTP单元用于实现与Ej相对应的矩阵Lm，k和分组模块发送的ej的相乘运算；这m个MTP单元依次为MTP1、MTP2…MTPk、…、MTPk；

j

k-1个MTP单元用于实现分组模块发送的ej和与E 相对应的矩阵Uk-1，k的相乘运算；

该k-1个MTP单元分别为MTPk-1、…、MTP2、MTP1；

MTPx单元包括x个与门和x-1个异或门，其中，x个与门为并列结构，x-1个异或门为树形结构，x个与门与x-1异或门次级连接；x＝1，2，…，k。

说明书

一种基于串并结合实现有限域乘法的方法及装置

技术领域

[0001] 本发明涉及信息技术领域，特别是一种基于串并结合实现有限域乘法的方法及装置。

背景技术

[0002] 有限域运算在差错控制、密码学领域均得到广泛应用。特别是在加密认证算法中，有限域运算应用广泛，它是指在特定的规则下进行的两类运算：加法运算和乘法运算。

[0003] 有限域GF(2)仅包含两个元素0和1，加法运算很容易利用一个异或门来实现，而m乘法运算利用一个与门也可以轻易实现。特别地，有限域GF(2)可以看做GF(2)的m维扩m
域，包括2 个元素。此时，有限域加法可由m个异或门实现，而乘法运算的实现则要复杂很多。

[0004] 在实现上，加法运算对应相应位数的异或门，而乘法的实现，效率远低于加法，资源消耗则远高于加法，是有限域运算的关键。另一方面，其他运算，如指数运算、除法运算、求逆运算等都是通过乘法的多次运算来实现。

[0005] 因而乘法器的性能是有限域运算在上述领域应用的关键。

[0006] 目前已提出的有限域乘法器主要有两类：比特串行乘法器和比特并行乘法器。在输入位宽为m的情况下。比特串行乘法器具有O(m)空间复杂度(O(m)表示算法的空间消耗与m成正比)，该方法对同一个模块进行轮询操作，能够将资源消耗降至最低。但该方案2
需要等待m个周期后才能得到输出，时延大。比特并行乘法器具有(O(m))空间复杂度，该方法结构紧凑，易于硬件实现，能够实现较高的吞吐量，适宜于现今高速的通信系统，但其消耗大量资源，不适宜成本的节约。

发明内容

[0007] 本发明提供了一种基于串并结合实现有限域乘法的方法，该方法能将简化乘法器结构，提高有限域内乘法运算的效率。

[0008] 为达到上述目的，该方法是这样实现的：

[0009] 本发明公开了一种基于串并结合实现有限域乘法的方法，本方法用于实现有限域内m位乘法因子A和m位乘法因子B的相乘运算，该方法包括：

[0010] 对m位的乘法因子A按从低位到高位进行分组，以k位为一组，分为p组，分组后的各组表示为ei，其中 i＝0，1，...，p-1；

[0011] 将e0与乘法因子B进行有限域内的乘法运算，得到D′0；将D′0作下一步中的1
C′1输出；对乘法因子B进行有限域内左移k位操作，得到E ；
j

[0012] 将ej与E 进行有限域内乘法运算，得到D′j；将D′j与C′j进行有限域内的加j j+1法运算，得到C′j+1；将E 进行有限域内左移k位操作，得到E ；其中，j＝1，2，3...p-2；
p-1

[0013] 将ep-1与E 进行有限域内乘法运算，得到D′p-1；将D′p-1与C′p-1进行有限域内的加法运算，得到C′p；输出C′p即为乘法因子A和乘法因子B在有限域内的乘积。

[0014] 本发明还提供了一种基于串并结合实现有限域乘法的装置，该装置用于实现有限域内m位乘法因子A和m位乘法因子B的相乘运算，所述装置包括：输入模块，分组模块，输出模块，p个PM模块，p个PM模块包括PM1模块、PM2模块...、PMp模块；

[0015] 输入模块，用于将m位乘法因子A发送给分组模块，将m位乘法因子B发送给PM1模块；

[0016] 分组模块，用于接收输入模块发送的乘法因子A，将乘法因子A从低位到高位进行分组操作，以k位为一组，分成p组，分组后的各组表示为ei，将ei依次发送给相应的PMi+1模块；其中 i＝0，1，...，p-1；

[0017] PM1模块，用于接收分组模块发送的e0，以及输入模块发送的乘法因子B；将e0和B进行有限域内的乘法运算，得到D′0；将D′0作为C′1发送给PM2模块；将乘法因子B进1 1
行有限域内左移k位操作，得到E，将E 发送给PM2模块；
j

[0018] PMj+1模块，用于接收分组模块发送的ej，以及PMj模块发送的E 与C′j；将ej与jE 进行有限域内的乘法运算，得到D′j；将D′j与C′j进行有限域内的加法运算，得到j j+1 j+1
C′j+1，将C′j+1发送给PMj+2模块；将E 进行有限域内左移k位操作，得到E ，将E 发送给PMj+2模块，其中，j＝1，2，3...p-2；
p-1

[0019] PMp模块，用于接收分组模块发送的ep-1，以及PMp-1模块发送的E 与C′p-1；将ep-1p-1与E 进行有限域内乘法运算，得到D′p-1，将D′p-1与C′p-1进行有限域内的加法运算，得到C′p，将C′p发送给输出模块；

[0020] 输出模块，用于接收PMp模块发送的C′p，将C′p输出。

[0021] 有上述可知，本发明这种通过串并结合的方法，将高位宽的相乘运算分解成多个低位宽的相乘运算，缩短了有限域乘法计算的关键路径，降低了空间复杂度，提高了有限域内乘法运算的效率。

附图说明

[0022] 图1是本发明中的一种基于串并结合实现有限域乘法的方法的流程图；

[0023] 图2是本发明中一种基于串并结合实现有限域乘法的装置的整体结构示意图；

[0024] 图3是本发明中一种基于串并结合实现有限域乘法的装置的PM1模块的内部结构图；

[0025] 图4是本发明中一种基于串并结合实现有限域乘法的装置的PMj+1模块的内部结构图；

[0026] 图5是本发明中一种基于串并结合实现有限域乘法的装置的PMp模块的内部结构图；

[0027] 图6是本发明中一种基于串并结合实现有限域乘法的装置的改进的Arash乘法器模块结构示意图；

[0028] 图7是本发明中一种基于串并结合实现有限域乘法的装置的MTP单元的结构示意图；

[0029] 图8是本发明中一种基于串并结合实现有限域乘法的装置的移位模块的结构示意图；

[0030] 图9是本发明中一种基于串并结合实现有限域乘法的装置的异或门阵列模块结构示意图；

[0031] 图10是本发明中一种基于串并结合实现有限域乘法的装置的实施例的结构示意图。

具体实施方式

[0032] 本发明公开了一种基于串并结合实现有限域乘法的方法，本方法用于实现有限域内m位乘法因子A和m位乘法因子B的相乘运算，为了使本发明的目的、技术方案和优点更加清楚，下面结合附图和具体实施例对本发明进行详细描述。

[0033] 图1是本发明中的一种基于串并结合实现有限域乘法的方法的流程图，如图1所示：

[0034] 步骤101，对m位的乘法因子A按从低位到高位进行分组，以k位为一组，分为p组，分组后的各组表示为ei，其中 i＝0，1，...，p-1；

[0035] 步骤102，将e0与乘法因子B进行有限域内的乘法运算，得到D′0；将D′0作下1
一步中的C′1输出；对乘法因子B进行有限域内左移k位操作，得到E ；
j

[0036] 步骤103，将ej与E 进行有限域内乘法运算，得到D′j；将D′j与C′j进行有j j+1限域内的加法运算，得到C′j+1；将E 进行有限域内左移k位操作，得到E ；其中，j＝1，
2，3...p-2；
p-1

[0037] 步骤104，将ep-1与E 进行有限域内乘法运算，得到D′p-1；将D′p-1与C′p-1进行有限域内的加法运算，得到C′p；输出C′p即为乘法因子A和乘法因子B在有限域内的乘积。

[0038] 本发明这种将有限域内的高阶乘法运算分解成有限域内多个低阶乘法运算，其中，将上一个低阶乘法运算的结果作为下一个低阶乘法运算的输入； 表示向上取整函数， 即分组个数p的值等于将m/k的值向上取整；其中，最高位ep-1不足k位时，将不足的位数进行补0操作，补成k位。

[0039] 本发明中，乘法因子A的第一个分组e0与B进行有限域内的乘法运算得到D′0与j j将ej与E 进行有限域内乘法运算得到D′j的过程相同，其中E 由乘法因子B经过j次左j
移操作得到；下面以ej与E 进行有限域内乘法运算得到D′j为例说明；

[0040] 首先，Ej进行m次左移位操作，每次左移一位，得到m个m位的数，将依次得到的数构成矩阵Lm，m；将矩阵Lm，m进行矩阵列截短得到m行k列的矩阵Lm，k，将矩阵Lm，k与ej进行相乘运算，得到Lm，k×ej；

[0041] Ej进行m-1次右移位操作，每次右移一位，得到m-1个m位的数，将依次得到的数构成矩阵Um-1，m；将矩阵Um-1，m进行矩阵行列截短得到k-1行k列矩阵Uk-1，k，将矩阵Uk-1，k与ej进行相乘运算，得到矩阵Uk-1，k×ej；

[0042] 将Uk-1，k×ej进行矩阵化简运算后，与Lm，k×ej一起进行异或操作，所述异或操作即得进行相加运算；得到D′j。

[0043] 本发明还公开了一种基于串并结合实现有限域乘法的装置，该装置用于实现有限域内m位乘法因子A和m位乘法因子B的相乘运算，如图2所示，图2是本发明中一种基于串并结合实现有限域乘法的装置的整体结构示意图。该装置包括：输入模块201，分组模块202，输出模块206，p个PM模块，该p个PM模块包括PM1模块203、...PMj+1模块204...、PMp模块205；

[0044] 输入模块201，用于将m位乘法因子A发送给分组模块202，将m位乘法因子B发送给PM1模块203；

[0045] 分组模块202，用于接收输入模块201发送的乘法因子A，将乘法因子A从低位到高位进行分组操作，以k位为一组，分成p组，分后的各组表示为ei，将ei依次发送给相应的PMi+1模块；其中 i＝0，1，...，p-1；

[0046] PM1模块203，用于接收分组模块202发送的e0，输入模块201发送的乘法因子B；将e0和B进行有限域内的乘法运算，得到D′0；将D′0作为C′1发送给PM2模块；将乘法
1 1
因子B进行有限域内左移k位操作，得到E，将E 发送给PM2模块；
j

[0047] PMj+1204模块，用于接收分组模块202发送的ej，PMj模块发送的E 与C′j；将ejj与E 进行有限域内的乘法运算，得到D′j；将D′j与C′j进行有限域内的加法运算，得到j j+1 j+1
C′j+1，将C′j+1发送给PMj+2模块；将E 进行有限域内左移k位操作，得到E ，将E 发送给PMj+2模块，其中，j＝1，2，3...p-2；
p-1

[0048] PMp模块205，用于接收分组模块发送的ep-1，PMp-1模块发送的E 与C′p+1；将ep-1p-1与E 进行有限域内乘法运算，得到D′p-1，将D′p-1与C′p-1进行有限域内的加法运算，得到C′p，将C′p发送给输出模块206；

[0049] 输出模块206，用于接收PMp模块205发送的C′p，将C′p输出。所述输出模块206输出的C′p即为m位乘法因子A和m位乘法因子B在有限域内的相乘运算的结果。

[0050] 如图2所示，该装置中共有p个PM模块，其中 在该p个PM模块中，除PM1模块203和PMp模块205外，其余的PM2模块至PMp-1模块都有相同的结构，并且该p个PM模块依次相连。

[0051] 图3是本发明中一种基于串并结合实现有限域乘法的装置的PM1模块的内部结构图，如图3所示，所示PM1模块203包括改进的Arash乘法器模块302，移位模块301，寄存器Z1 303，寄存器C1 304；

[0052] 改进的Arash乘法器模块302，用于接收输入模块201发送的乘法因子B，分组模块202发送的e0；将B与e0进行有限域内的乘法运算，将得到的相乘结果D′0作为C′1发送寄存器C1 304；

[0053] 移位模块301，用于接收输入模块201发送的乘法因子B，将乘法因子B进行在有1 1
限域内左移k位操作，得到E，将E 发送给寄存器Z1 303；

[0054] 寄存器Z1 303，用于存储移位模块301发送的E1；

[0055] 寄存器C1 304，用于存储改进的Arash乘法器模块302发送的C′1。

[0056] PM1模块203的输入由图2中的输入模块201和分组模块202提供输入。

[0057] 图4是本发明中一种基于串并结合实现有限域乘法的装置的PMj+1模块的内部结构图，如图4所示，所述PMj+1模块204包括：改进的Arash乘法器模块401，移位模块402，异或阵列模块403，寄存器Zj+1 404，寄存器Cj+1 405；其中，

[0058] 改进的Arash乘法器模块401，用于从寄存器Zj中读取Ej，接收分组模块202发送j的ej，将E 与ej进行有限域内的乘法运算，得到D′j；将D′j发送异或阵列模块403；

[0059] 移位模块402，用于读取寄存器Zj中的Ej，将Ej进行有限域内左移k位操作，得到j+1 j+1E ，将E 发送给寄存器Zj+1；

[0060] 异或阵列模块403，用于读取寄存器Cj中的C′j，接收改进的Arash乘法器模块401发送的D′j；将C′j与D′j进行有限域内的加法运算；得到C′j+1，将C′j+1发送给寄存器Cj+1 404；

[0061] 寄存器Zj+1 405，用于存储移位模块402发送的Ej+1；

[0062] 寄存器Cj+1 404，用于存储异或阵列模块403发送的C′j+1。

[0063] 其中寄存器Zj和寄存器Cj是PMj模块中的寄存器模块。

[0064] 图5是本发明中一种基于串并结合实现有限域乘法的装置的PMp模块的内部结构图，如图5所示，所述PMp模块205包括：改进的Arash乘法器模块501，异或阵列模块502，寄存器Cp 503；其中，

[0065] 改进的Arash乘法器模块501，用于从寄存器Zp-1中读取Ep-1，接收分组模块202发p-1送的ep-1，将E 与ep-1进行有限域内的乘法运算；得到D′p-1，将D′p-1发送异或阵列模块
502；

[0066] 异或阵列模块502，用于从寄存器Cp-1读取C′p-1，接收改进的Arash乘法器模块501发送的D′p-1；将C′p-1与D′p-1进行有限域内的加法运算，得到C′p；将C′p发送给寄存器Cp 503；

[0067] 寄存器Cp 503，用于存储异或阵列模块502发送的C′p。

[0068] 在各PM模块中，所包含的改进的Arash乘法器模块、异或阵列模块、移位模块、寄存器都具有相同的结构。

[0069] 图6是本发明中一种基于串并结合实现有限域乘法的装置的改进的Arash乘法器模块结构示意图；如图6所示，所述改进的Arash乘法器模块包括：左移位模块601，矩阵列截短模块602，矩阵相乘模块605，右移位模块603，矩阵行列截短模块604，矩阵简化模块606，二元异或门列模块607；其中，

[0070] 左移位模块601，用于接收输入模块201发送的乘法因子B或读取寄存器Zj存储j的E，将获取到的操作数进行m次左移位操作，得到m行m列的矩阵Lm，m，将所述矩阵Lm，m发送给矩阵列截短模块602；

[0071] 所述左移位模块601包括m个m位的移位寄存器，将所获得的操作数Ej或是乘法因子B进行左移位操作，将每次左移得到的数存放在对应的移位寄存器中，经过m次左移位操作，得到m个m位的数，将该m个m位寄存器中的数构成一个m行m列的矩阵Lm，m；其中，每个操作数都有一个与之相对应的矩阵Lm，m。

[0072] 矩阵列截短模块602，用于接收左移位模块601发送的矩阵Lm，m，将所述矩阵Lm，m进行矩阵列截短操作，得到m行k列的矩阵Lm，k；将矩阵Lm，k发送给矩阵相乘模块605，其中Lm，k即在矩阵Lm，m中取前m行k列的数构成；

[0073] 右移位模块603，用于接收输入模块201发送的乘法因子B或读取寄存器Zj中存储j的E，将获取到的操作数进行m-1次右移位操作，得到m-1行m列的矩阵Um-1，m，将所述矩阵Um-1，m发送给矩阵行列截短模块604；所述右移位模块603包括m-1个m位的移位寄存器，；

[0074] 矩阵行列截短模块604，用于接收右移位模块603发送的矩阵Um-1，m，将所述矩阵Um-1，m进行矩阵行列截短操作，得到k-1行k列的矩阵Uk-1，k；将矩阵Uk-1，k发送给矩阵相乘模块605；

[0075] 矩阵相乘模块605，用于将矩阵列截短模块602发送的与Ej相对应的左移矩阵Lm，k和分组模块202发送的ej进行相乘运算，得到Lm，k×ej；将Lm，k×ej发送给二元异或门列模j块607；用于将矩阵行列截短模块604发送的与E 相对应的右移矩阵Uk-1，k和分组模块202发送的ej进行相乘运算，得到Uk-1，k×ej；将Uk-1，k×ej发送给矩阵简化模块606；

[0076] 如图6所示，矩阵相乘模块605包括m+k-1个MTP单元，其中，m个MTP单元与矩阵列截短模块602相连，用于实现矩阵Lm，k与ej的相乘运算，将得到中间结果Lm，k×ej发送给二元异或门列模块607，其中，中间结果Lm，k×ej为m行1列的矩阵；该m个MTP从第1列到到k列依次为MTP1、MTP2...MTPk；从第k+1列到m列都为MTPk。

[0077] 矩阵相乘模块605中k-1个MTP单元与矩阵行列截短模块604相连，用于实现矩阵Uk-1，k与ej的相乘运算得到中间结果为Uk-1，k×ej，该Uk-1，k×ej为k-1行1列的矩阵。该k-1个MTP单元分别为MTPk-1、...、MTP2、MTP1。

[0078] 矩阵简化模块606，用于接收矩阵相乘模块605发送的Uk-1，k×ej，将Uk-1，k×ej化简成m行1列的矩阵Rm，1；将矩阵Rm，1发送给二元异或门列模块607；

[0079] 上述矩阵简化模块606用于实现矩阵相乘模块605发送的Uk-1，k×ej与简化矩阵R相乘，将k-1行1列的矩阵转换成m行1列的矩阵Rm，1。所述简化矩阵R矩阵由有限域上的m kt k2 k1不可约多项式P(x)＝x+x +..+x +x +1确定且具有唯一性，其生成规则如下：

[0080] R矩阵的第0行有t+1列1，其余列为0，1的分布分别在0，k1，k2，...，kt列，其m kt k2 k1中0，k1，k2，...，kt为表示P(x)＝x+x +..+x +x +1中x的幂，t为计数单位，表示为第几个；

[0081] R矩阵的第1行至m-kt-1行由第0行依次右移位得到。

[0082] R矩阵的第m-kt至m-2行的构造规则如下：

[0083] 当i行最后一列以1结尾时，i+1行向右移一位并与第0行的值进行异或运算；

[0084] 当i行最后一列以0结尾时，i+1行向右移一位。

[0085] 在本发明中按照上述构造规则，构造第0行至第k-2行，得到的简化矩阵R为k-1行m列矩阵。

[0086] 二元异或门列模块607，用于接收矩阵相乘模块605发送的Lm，k×ej和矩阵简化模块606发送的相对应的矩阵Rm，1；将Lm，k×ej与Rm，1进行异或操作，得到D′j，将D′j输出。其中Lm，k×ej为m行1列的矩阵，Rm，1也是m行1列的矩阵，将Lm，k×ej与Rm，1进行异或操作得到的结果即D′j。D′j即低阶乘法装置将m位乘法因子与k位的乘法因子相乘得到的结果。该结果D′j与寄存器Cj中的C′j进行异或操作，将得到的结果C′j+1存储在寄存器Cj+1中，将用于下一个低阶乘法装置的输入，依次进行运算，得到最终结果C′p。

[0087] 图7是本发明中一种基于串并结合实现有限域乘法的装置的MTPx单元的结构示意图，如图7所示，所述MTPx单元包括x个与门和x-1个异或门，其中，x个与门为并列结构，位于第一级，x-1个异或门为树形结构，x个与门与x-1异或门次级连接。

[0088] 图8是本发明中一种基于串并结合实现有限域乘法的装置的移位模块的结构示i i+1意图，所述移位模块用于对操作数E 依次进行有限域内左移K位的操作，得到结果为E 。
如图8所示，所述移位模块包括Rk，m矩阵模块801和异或门结果802。其中，Rk，m矩阵模块
801中的矩阵Rk，m与矩阵简化模块606中的矩阵Rk-1，m的原理与生成规则相同，即都是由简化矩阵R转换得到的；所述Rk，m由简化矩阵R中的k行m列构造而成。

[0089] 以操作数Ei-1为例，其中 (j＝0...m-1)用来表示Ei-1的第j位的位值；所述i-1E 共有m为分别为 如图所示，其中从 直接发送给异
或门模块802，从 到 发送给Rk，m矩阵模块801，经Rk，m矩阵模块801的简化矩阵Rk，m相乘后将m位数，分别为 其中 直接输出，其余的发送给
异或门模块802，通过异或门模块802与 进行异或操作得到
所述输出的数共m位即Ei-1经过左移k位得到的Ei。

[0090] 图9是本发明中一种基于串并结合实现有限域乘法的装置的异或门阵列模块结构示意图，如图9所示，所述异或门阵列模块901有m个并列结构的异或门构成。

[0091] 下面结合具体实施例来说明本发明。GCM(Galois/Counter Mode)是一种在二元Galois域使用泛散列提供加密认证的分组密码算法。其中认证方案核心为128位乘法装置。即实现m位的乘法因子A和m位的乘法因子B的乘法运算，其中m＝128。图10是本发明中一种基于串并结合实现有限域乘法的装置的实施例的结构示意图；如图10所示，[0092] 步骤1，m＝128，对128位宽的乘法因子A进行位宽分割，以k＝8比特位宽为一组，可以分为p＝[128/8]＝16个组；即乘法因子A的[7:0]为e0，[15:8]为e1，L[127:120]记为ep-1；乘法因子B不进行分组，直接由输入模块发送给PM1模块。可知其所对应的有限域GF(2128)上的不可约多项式为P(x)＝x128+x7+x2+x+1，即k1＝1，k2＝2，k3＝7，共有3个数则t＝3。则构造的简化矩阵R的第0行有t+1＝4个1，分别在0，1，2，7列；简化矩阵R的第1行至6行由第0行依次右移位得到。得到简化矩阵R为：

[0093]

[0094] 步骤2，构造128个128为的移位寄存器，每个移位寄存器分别用于将获得的与之相连的上一个移位寄存器中的操作数进行左移一位的操作并将所得到的数存储；共得到128个128位的数，构成矩阵L128，128；将所得到的矩阵发送给矩阵列截短模块，经过矩阵列截短后，得到一个128行8列的矩阵L128，8。将矩阵L128，8发送给矩阵相乘模块。

[0095] 步骤3，构造127个128为的移位寄存器，每个移位寄存器分别用于将获得的与之相连的上一个移位寄存器中的操作数进行又移一位的操作并将所得到的数存储；共得到127个128位的数，构成矩阵U127，128；将所得到的矩阵发送给矩阵列截短模块，经过矩阵列截短后，得到一个7行8列的矩阵U7，8。将矩阵U7，8发送给矩阵相乘模块。所述矩阵相乘模块包括135个MTP单元，其中，与矩阵列截短模块相连的128个MTP单元，用于实现矩阵L128，
8与e0的相乘运算，得到中间结果L128，8×e0，该中间结果L128，8×e0为128行1列的矩阵；其中，与矩阵行列截短模块相连的7个MTP单元，用于实现矩阵e0与U7，8的相乘运算得到中间结果为U7，8×e0，该U7，8×e0为7行1列的矩阵。

[0096] 步骤5，将该U7，8×e0发送给简化矩阵模块进行与简化矩阵R进行相乘运算，生成T TR×U7，8×e0为128行1列的矩阵，在将该R×U7，8×e0与L128，8×e0进行异或操作。得到的结果即有限域内B与e0的乘积。将该结果存储在寄存器C1。

[0097] 步骤6，乘法因子B进行GF(2128)域内的左移8位的移位操作，将得到的E1存入寄128
存器Z1中。其中，B在GF(2 )域内的进行左移8位的操作，所用到的Rk，m矩阵模块中的矩阵R8，128如下所示：

[0098]

[0099] 步骤7，取寄存器Z1中的数据与乘法因子A的第二个分组e1进行乘法运算，具体步骤同上步骤1到步骤6，将得到的乘积与寄存器C1中的值异或，并将结果存入寄存器C2中。128
取寄存器Z1中的数据，经过GF(2 )域内的左移8位操作将结果存入寄存器Z2中。

[0100] 重复步骤7，直到A的最后一个分组e15，最终得到C16，即为GF(2128)A和B的乘积。

[0101] 综上所述，本发明采用分治思想，通过串并结合的方法，将高位宽的相乘运算分解成多个低位宽的相乘运算，缩短了有限域乘法计算的关键路径，降低了空间复杂度；本发明中乘法器在结构上采用流水线结构，具有低复杂度、高吞吐量的特性。

[0102] 有限域乘法器的时间复杂度通常用时延衡量。在m位下的时间复杂度是其中TA是一个而输入与门的时延，TX是一个二输入异或门的时延。有限域乘法器空间复杂度通常用所使用的与门异或门数量衡量，本发明的乘法器在m位下的空间复杂度是：与门数m2，异或门数m2-(3-p-2/p)m-p。

[0103] 同时参数k(或p)可调整，即调节时间复杂度和空间复杂度的关系，(用时间换低空间复杂度，或用空间复杂度换低时延)，以适应不同应用场景对时空复杂度的要求。