一种基于心动模型的复合有限域乘法器

摘要

本发明提出一种基于心动模型的复合有限域乘法装置，包括：输入端口，用于输入复合有限域的运算数、复合有限域的子域上选定的既约多项式、复合有限域上选定的既约多项式以及时钟信号；复合有限域乘法器，用于执行所述运算数在复合有限域上的乘法；子域乘法器及子域加法器，分别供复合有限域乘法器调用以执行所述运算数在子域上的乘法及加法；控制器，信号连接输入端口和复合有限域乘法器以控制复合有限域乘法器；以及输出端口，信号连接控制器以输出复合有限域乘法器所执行的乘法的运算结果。本发明采用基于心动模型的方法进行复合有限域的乘法，在进行复合有限域上的乘法方面相对于现有乘法器有着明显的速度优势，可广泛用于数学和工程领域。

权利要求

1.一种基于心动模型的复合有限域乘法装置，其特征在于，包括：

输入端口，用于输入复合有限域的运算数、所述复合有限域的子域上选定的第一既约多项式、所述复合有限域上选定的第二既约多项式以及时钟信号；

复合有限域乘法器，用于执行所述运算数在所述复合有限域上的乘法；

子域乘法器，信号连接所述复合有限域乘法器且用于执行所述运算数在所述子域上的乘法；

子域加法器，信号连接所述复合有限域乘法器且用于执行所述运算数在所述子域上的加法；

控制器，信号连接所述输入端口和所述复合有限域乘法器且用于控制所述复合有限域乘法器；以及输出端口，信号连接所述控制器以输出所述复合有限域乘法器所执行的乘法的运算结果；

其中，所述子域乘法器和所述子域加法器均为两个、且均通过所述复合有限域乘法器连接所述控制器；

所述控制器包括信号连接的解析器和第一处理器；所述解析器用于解析所述时钟信号且当所述时钟信号跳变时通知所述第一处理器运算进入新的一个时钟周期，所述第一处理器用于接收所述运算数、所述第一既约多项式和所述第二既约多项式并将所述解析器的解析结果通知所述复合有限域乘法器，以控制所述复合有限域乘法器；

所述复合有限域乘法器包括信号连接的第二处理器和调度器；所述第二处理器用于执行所述运算数在所述复合有限域上的乘法，所述调度器用于调用所述子域乘法器和所述子域加法器；

所述子域乘法器包括信号连接的第三处理器、乘法心动阵列和取模心动阵列；所述乘法心动阵列用于执行乘法运算，所述取模心动阵列用于执行取模运算，所述第三处理器用于控制所述乘法心动阵列及所述取模心动阵列以执行所述运算数在所述子域上的乘法；

所述子域加法器包括信号连接的第四处理器和异或运算器；所述异或运算器用于执行异或运算，所述第四处理器用于控制所述异或运算器以执行所述运算数在所述子域上的加法。

2.根据权利要求1所述的基于心动模型的复合有限域乘法装置，其特征在于，所述输入端口包括：用于分别输入所述运算数中的第一运算数和第二运算数的第一运算数输入端口及第二运算数输入端口，用于输入所述第一既约多项式的第一既约多项式输入端口，用于输入所述第二既约多项式的第二既约多项式输入端口，以及用于输入所述时钟信号的时钟输入端口；

n 2 n

所述复合有限域为GF((2)) ，所述子域为GF(2)；所述第一及第二运算数分别具有表示形式：a(x)＝a1x+a0，b(x)＝b1x+b0；所述第一既约多项式具有表示形式：p(x)＝xn+pn-1xn-1+pn-2xn-2+...+p1x+1；所述第二既约多项式具有表示形式：q(x)＝q2x2+q1x+q0；

其中，a(x)和b(x)分别表示所述第一运算数和所述第二运算数，p(x)表示所述第一既约多项式，q(x)表示所述第二既约多项式，q2,q1,q0,a1,a0,b1,b0均为所述子域上的元素，pn-1,pn-2,...,p1均为有限域GF(2)上的元素。

3.根据权利要求1所述的基于心动模型的复合有限域乘法装置，其特征在于，所述运算数在所述子域上的乘法包括以下步骤：(S1)所述运算数中的第一和第二运算数分别表示为 和

aj、bk是所述乘法心动阵列的输入；

(S2)bk依次从左至右进入Si，每个时钟周期后向右移动进入Si+1，其中，Si及Si+1为所述乘法心动阵列中的阵列单元，i＝0,1,...,2n-2；

(S3)aj同时输入到每个Si，在2n个周期后，aj+1同时输入到每个Si；

(S4)在每个Si中，若满足j+k＝i，计算si＝si+ajbk；

(S5)根据 计算vij；

(S6)乘法运算结果表示为 cm是所述取模心动阵列的输入；

(S7)cm依次从左至右进入Si，每个时钟周期后向右移动进入Si+1；

(S8)在每个Si中，计算cm＝cm+νimSi，则c(x)是所述第一及第二运算数a(x)和b(x)在所述子域上的乘积且c(x)也是所述子域上的元素。

4.根据权利要求1所述的基于心动模型的复合有限域乘法装置，其特征在于，所述基于心动模型的复合有限域乘法装置为专用集成电路器件。

5.根据权利要求1所述的基于心动模型的复合有限域乘法装置，其特征在于，所述基于心动模型的复合有限域乘法装置为可编程逻辑器件。

6.根据权利要求5所述的基于心动模型的复合有限域乘法装置，其特征在于，所述可编程逻辑器件为FPGA器件。

说明书

一种基于心动模型的复合有限域乘法器

技术领域

[0001] 本发明涉及一种对有限域的元素进行相乘的装置，特别涉及一种基于心动模型对复合有限域的两个运算数进行相乘运算的装置。

背景技术

[0002] 有限域(也称伽罗华域，Galois Field,缩写为GF)是仅含有限多个元素的域，广泛地运用于数学和工程领域。目前，有限域的乘法根据设计的基底不同，大致可以分为四类：基于标准基的乘法、基于正规基的乘法、基于双基底的乘法和基于三角基的乘法。

[0003] 在有限域计算的设计方法中，基于心动模型的设计方法是高效的有限域计算方法之一，被广泛运用于有限域乘法、求逆、除法和求解线性方程组等运算。但基于心动模型的设计方法在复合有限域的应用较少。

[0004] 复合有限域是有限域的一种特殊形式，可以用GF((2n))m的形式表示。GF((2n))m是有限域GF(2n×m)的同构形式，被有效地运用于密码、信号处理、数据存储等领域。在复合有限n m n 2域GF((2)) 中，GF((2)) 是使用得最多的复合有限域之一。有效的复合有限域的乘法设计，对数学和工程领域起着至关重要的作用。现有技术中存在的复合有限域的乘法器，较少使用心动模型。在实时和对速度敏感的环境下，使用基于心动模型的特定硬件装置来实现复合有限域乘法可以提高运算效率。

发明内容

[0005] 因此，本发明提出一种基于心动模型的复合有限域乘法装置，以提升运算效率。

[0006] 具体地，本发明实施例提出的一种基于心动模型的复合有限域乘法装置，包括：输入端口，用于输入复合有限域的运算数、所述复合有限域的子域上选定的第一既约多项式、所述复合有限域上选定的第二既约多项式以及时钟信号；复合有限域乘法器，用于执行所述运算数在所述复合有限域上的乘法；子域乘法器，信号连接所述复合有限域乘法器且用于执行所述运算数在所述子域上的乘法；子域加法器，信号连接所述复合有限域乘法器且用于执行所述运算数在所述子域上的加法；控制器，信号连接所述输入端口和所述复合有限域乘法器且用于控制所述复合有限域乘法器；以及输出端口，信号连接所述控制器以输出所述复合有限域乘法器所执行的乘法的运算结果。

[0007] 在本发明的一个实施例中，所述输入端口包括：用于分别输入所述运算数中的第一运算数和第二运算数的第一运算数输入端口及第二运算数输入端口，用于输入所述第一既约多项式的第一既约多项式输入端口，用于输入所述第二既约多项式的第二既约多项式输入端口，以及用于输入所述时钟信号的时钟输入端口。所述复合有限域为GF((2n))2，所述子域为GF(2n)；所述第一及第二运算数分别具有表示形式：a(x)＝a1x+a0，b(x)＝b1x+b0；所述第一既约多项式具有表示形式：p(x)＝xn+pn-1xn-1+pn-2xn-2+...+p1x+1；所述第二既约多项2
式具有表示形式：q(x)＝q2x+q1x+q0。其中，a(x)和b(x)分别表示所述第一运算数和所述第二运算数，p(x)表示所述第一既约多项式，q(x)表示所述第二既约多项式，q2,q1,q0,a1,a0,b1,b0均为所述子域上的元素，pn-1,pn-2,...,p1均为有限域GF(2)上的元素。

[0008] 在本发明的一个实施例中，所述控制器包括信号连接的解析器和第一处理器；所述解析器用于解析所述时钟信号且当所述时钟信号跳变时通知所述第一处理器运算进入新的一个时钟周期，所述第一处理器用于接收所述运算数、所述第一既约多项式和所述第二既约多项式并将所述解析器的解析结果通知所述复合有限域乘法器，以控制所述复合有限域乘法器。

[0009] 在本发明的一个实施例中，所述复合有限域乘法器包括信号连接的第二处理器和调度器；所述第二处理器用于执行所述运算数在所述复合有限域上的乘法，所述调度器用于调用所述子域乘法器和所述子域加法器。

[0010] 在本发明的一个实施例中，所述子域乘法器包括信号连接的第三处理器、乘法心动阵列和取模心动阵列；所述乘法心动阵列用于执行乘法运算，所述取模心动阵列用于执行取模运算，所述第三处理器用于控制所述乘法心动阵列及所述取模心动阵列以执行所述运算数在所述子域上的乘法。

[0011] 在本发明的一个实施例中，所述运算数在所述子域上的乘法包括以下步骤：

[0012] (S1)所述运算数中的第一和第二运算数分别表示为 和是所述乘法心动阵列的输入；

[0013] (S2)bk依次从左至右进入Si，每个时钟周期后向右移动进入Si+1，其中，Si及Si+1为所述乘法心动阵列中的阵列单元，i＝0,1,...,2n-2，n为正整数；

[0014] (S3)aj同时输入到每个Si，在2n个周期后，aj+1同时输入到每个Si；

[0015] (S4)在每个Si中，若满足j+k＝i，计算si＝si+ajbk；

[0016] (S5)根据

[0017] (S6)乘法运算结果表示为 cm是所述取模心动阵列的输入；

[0018] (S7)cm依次从左至右进入Si，每个时钟周期后向右移动进入Si+1；

[0019] (S8)在每个Si中，计算cm＝cm+νimSi，则c(x)是所述第一及第二运算数a(x)和b(x)在所述子域上的乘积且c(x)也是所述子域上的元素。

[0020] 在本发明的一个实施例中，所述子域加法器包括信号连接的第四处理器和异或运算器；所述异或运算器用于执行异或运算，所述第四处理器用于控制所述异或运算器以执行所述运算数在所述子域上的加法。

[0021] 在本发明的一个实施例中，所述基于心动模型的复合有限域乘法装置为专用集成电路器件。

[0022] 在本发明的一个实施例中，所述基于心动模型的复合有限域乘法装置为可编程逻辑器件例如FPGA器件。

[0023] 因此，本发明实施例采用基于心动模型的方法进行复合有限域的乘法，在进行复合有限域上的乘法方面相对于现有的乘法器有着明显的速度优势，可以广泛运用于数学领域和工程领域。

[0024] 通过以下参考附图的详细说明，本发明的其它方面和特征变得明显。但是应当知道，该附图仅仅为解释的目的设计，而不是作为本发明的范围的限定。还应当知道，除非另外指出，不必要依比例绘制附图，它们仅仅力图概念地说明此处描述的结构和流程。

附图说明

[0025] 下面将结合附图，对本发明的具体实施方式进行详细的说明。

[0026] 图1为本发明实施例提出的一种基于心动模型的复合有限域乘法装置的结构示意图。

[0027] 图2为图1所示控制器的结构示意图。

[0028] 图3为图1所示GF((2n))2乘法器的结构示意图。

[0029] 图4为图1所示GF(2n)乘法器的结构示意图。

[0030] 图5为图4所示GF(2n)乘法器中的乘法心动阵列的结构示意图。

[0031] 图6为图4所示GF(2n)乘法器中的取模心动阵列的结构示意图。

[0032] 图7为图1所示GF(2n)加法器的结构示意图。

具体实施方式

[0033] 为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图对本发明的具体实施方式做详细的说明。

[0034] 如图1所示，本发明实施例提出的一种基于心动模型的复合有限域乘法装置10包括：控制器11、输入端口、输出端口、GF((2n))2乘法器13、GF(2n)乘法器15和GF(2n)加法器17，所述控制器11与输入端口、输出端口和GF((2n))2乘法器13分别信号连接；所述GF((2n))2乘法器13与GF(2n)乘法器15、GF(2n)加法器17分别信号连接；其中，GF(2n)乘法器15和GF(2n)加法器17例如均为两个，但本发明并不以此为限。下面将结合图1至图7分别对本发明实施例基于心动模型的复合有限域乘法装置10的各组成部分做详细介绍。

[0035] (1)输入端口：如图1所示，本实施例共有五个输入端口，包括4个数据信号输入端口和1个时钟信号输入端口。其中，输入端口a和b分别用于输入复合有限域GF((2n))2的运算数a(x)和b(x)而作为运算数输入端口，输入端口p和q分别用于输入有限域GF(2n)和复合有限域GF((2n))2上选定的既约多项式p(x)和q(x)而作为既约多项式输入端口，输入端口k用于输入时钟信号clk而作为时钟输入端口。

[0036] 运算数a(x)和b(x)以及既约多项式p(x)和q(x)可以表示为以下形式：

[0037] a(x)＝a1x+a0；

[0038] b(x)＝b1x+b0；

[0039] p(x)＝xn+pn-1xn-1+pn-2xn-2+...+p1x+1；

[0040] q(x)＝q2x2+q1x+q0；

[0041] 其中，q2,q1,q0,a1,a0,b1,b0均是有限域GF(2n)上的元素，pn-1,pn-2,...,p1均是有限域GF(2)上的元素，时钟信号clk是1比特(bit)数值，共有两种取值即0和1。

[0042] (2)输出端口：如图1所示，输出端口c用于输出求解复合有限域GF((2n))2的表达式(a(x)×b(x))mod(q(x))之后获得的运算结果c(x)而作为运算结果输出端口，其中mod为求模运算；c(x)可以表示为以下形式：c(x)＝c1x+c0.

[0043] (3)控制器11：控制器11在本实施例作为唯一能够和输入/输出端口(I/O端口)通信的部件，是本实施例基于心动模型的复合有限域乘法装置10中的核心部件，分别与输入端口a,b,p,q及k、输出端口c和GF((2n))2乘法器13相连，可以控制GF((2n))2乘法器13。如图2所示，控制器11由信号连接的解析器111和第一处理器(或信号处理电路)113组成。解析器
111用于解析从输入端口k输入的时钟信号clk。当clk的值从0至1发生变化，解析器111将通知第一处理器113运算进入新的一个时钟周期。第一处理器113用于接收输入的数据信号a(x)、b(x)、p(x)及q(x)并将解析器111的解析结果通知GF((2n))2乘法器13，从而实现对GF((2n))2乘法器13的控制。

[0044] (4)GF((2n))2乘法器13：如图3所示，GF((2n)2)乘法器13包括信号连接的第二处理n 2器(或信号处理电路)131和调度器133；第二处理器131是用于执行在复合有限域GF((2))上的乘法(a(x)×b(x))mod(q(x))，其中mod为求模运算；而调度器133用于调用GF(2n)乘法器15和GF(2n)加法器17。

[0045] (5)GF(2n)乘法器15：如图4所示，GF(2n)乘法器15包括信号连接的第三处理器(或信号处理电路)151、乘法心动阵列153和取模心动阵列155；第三处理器151用于实现对乘法心动阵列153和取模心动阵列155的控制、执行子域GF(2n)的运算数a(x)和b(x)的乘法(a(x)×b(x))mod(p(x))；乘法心动阵列153用于执行乘法运算，以及取模心动阵列155用于执行取模运算。此处值得一提的是，因为GF(2n)为复合有限域GF((2n)2)的子域，因而GF(2n)乘法器15也可以称之为子域乘法器。再者，运算数a(x)和b(x)在子域GF(2n)上的乘法可以包括以下步骤：

[0046] (5-1)两个运算数可以表示为 和 如图5所示，aj、bk是乘法心动阵列153的输入；

[0047] (5-2)bk依次从左至右进入Si，每个时钟周期后向右移动进入Si+1，其中，Si及Si+1为乘法心动阵列中的阵列单元，i＝0,1,...,2n-2,k＝0,1,...,n-1；

[0048] (5-3)aj同时输入到每个Si，在2n个时钟周期后，aj+1同时输入到每个Si，其中，i＝0,1,...,2n-2,j＝0,1,...,n-1；

[0049] (5-4)在每个Si中，若满足j+k＝i，计算si＝si+ajbk,其中，i＝0,1,...,2n-2；

[0050] (5-5)根据 计算vij，其中，i＝0,1,...,2(n-1),j＝0,1,...,n-1；

[0051] (5-6)运算结果可以表示为 如图6所示，cm是取模心动阵列的输入；

[0052] (5-7)cm依次从左至右进入Si，每个时钟周期后向右移动进入Si+1，其中，i＝0,1,...,2n-2,m＝0,1,...,n-1；

[0053] (5-8)在每个Si中，计算cm＝cm+νimSi，其中，i＝0,1,...,2n-2。则c(x)是运算数a(x)和b(x)在子域GF(2n)上的乘积且c(x)也是子域GF(2n)上的元素。

[0054] (6)GF(2n)加法器17：GF(2n)加法器17用于执行GF(2n)的运算数a(x)和b(x)的加法(a(x)+b(x))mod(p(x))，如图7所示，GF(2n)加法器17包括信号连接的第四处理器(或称信号处理电路)171和异或运算器173；第四处理器171用于实现对异或运算器173的控制、执行子域GF(2n)的运算数a(x)和b(x)的加法(a(x)+b(x))mod(p(x))，异或运算器173用于执行异或运算。此处值得一提的是，因为GF(2n)为复合有限域GF((2n)2)的子域，因而GF(2n)加法器17也可以称之为子域加法器。

[0055] 下面以n＝4为例说明本实施例的工作过程：

[0056] 令输入的时钟信号clk从0变化至1，控制器11中的解析器111通知控制器11中的第一处理器113进入新的时钟周期，控制器11中的第一处理器113接收输入的数据信号a(x)、b(x)、p(x)和q(x)；其中，a(x)和b(x)作为运算数，其表示形式例如为a(x)＝ahx+al和b(x)＝4 2 4
bhx+bl，并且均是复合有限域GF((2))上的元素，ah、al、bh和bl均是子域GF(2)上的元素；p(x)和q(x)作为输入的数据信号，分别是子域GF(24)和复合有限域GF((24)2)上选定的既约多项式(或称不可约多项式)，其表示形式例如为p(x)＝x4+x+1和q(x)＝x2+x+e，其中e＝9是子域GF(24)上的常数。

[0057] 控制器11中的第一处理器113发送a(x)、b(x)、p(x)和q(x)给GF((2n)2)乘法器13并等待获得反馈的结果。此时，GF((2n)2)乘法器13启动第二处理器131执行复合有限域GF((2n)2)上的乘法，分别计算ch＝ah·bh+ah·bl+al·bh和cl＝e·ah·bh+al·bl。其中，运算符“·”是子域GF(24)上的乘法运算，运算符“+”是子域GF(24)上的加法运算。

[0058] GF((2n)2)乘法器13的第二处理器131在处理子域GF(24)上的乘法或加法运算时，通过启动其内部的调度器133来完成运算。此时，内部的调度器133将需要参加运算的两个运算数发送给GF(2n)乘法器15或GF(2n)加法器17并等待获得反馈的结果。

[0059] 在GF(2n)乘法器15中，令 表示为 和 的乘积，aj和bk作为乘法心动阵列153的输入。bk依次从左至右进入Si，每个周期后向右移动进入Si+1，其中，i＝0,
1,...,6,k＝0,1,...,3。aj同时输入到每个Si，在8个周期后，aj+1同时输入到每个Si，其中，i＝0,1,...,6,j＝0,1,...,3。在每个Si中，若满足j+k＝i，计算si＝si+ajbk,其中，i＝0,
1,...,6。根据 计算vij，其中，i＝0,1,...,6,j＝0,1,...,3。cm
作为取模心动阵列的输入，cm依次从左至右进入Si，每个周期后向右移动进入Si+1，其中，i＝
0,1,...,6,m＝0,1,...,3。在每个Si中，计算cm＝cm+νimSi，其中，i＝0,1,...,6。

[0060] 在GF(2n)加法器17中，令 表示为 和 的和，则可以通过异或运算器173计算ci＝ai+bi，其中，i＝0,1,...,3。

[0061] 一旦GF(2n)乘法器15或者GF(2n)加法器17完成所需的运算并发送结果到调度器133，调度器133即时将此结果发给GF((2n)2)乘法器13中的第二处理器131。

[0062] GF((2n)2)乘法器13完成计算后，c(x)＝chx+cl是(a(x)×b(x))mod(q(x))的计算4 2 4
结果，是复合有限域GF((2))上的元素，ch和cl是子域GF(2)上的元素。第二处理器131将此运算结果发送给控制器11，控制器11即将此结果输出到输出端口c。

[0063] 最后值得一提的是，本发明前述实施例的基于心动模型的复合有限域乘法装置10可以是专用集成电路(Application Specific Integrated Circuits，ASIC)器件或者是可编程逻辑器件例如FPGA(Field Programmable Gate Array，现场可编程门阵列)器件。

[0064] 以上所述仅是本发明的较佳实施例而已，并非对本发明作任何形式上的限制，虽然本发明已以较佳实施例揭露如上，然而并非用以限定本发明，任何熟悉本专业的技术人员，在不脱离本发明技术方案范围内,当可利用上述揭示的技术内容做出些许更动或修饰为等同变化的等效实施例，但凡是未脱离本发明技术方案内容，依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化与修饰，均仍属于本发明技术方案的范围内。