CN118819470A - 模乘运算电路、方法、数据处理芯片和电子设备 - Google Patents

Abstract

本申请公开了一种模乘运算模乘运算电路、方法、数据处理芯片和电子设备。其中，该电路包括：存储组件，用于存储计算数据，计算数据包括第一乘数、第二乘数和除数；计算组件，与存储组件连接，用于将第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于多项式中的各个项对除数进行模约减运算，以确定第一乘数、第二乘数和除数的目标模值；控制组件，与寄存器组件及计算组件连接，用于控制计算组件从存储组件中读取计算数据，并将计算组件输出的计算结果存储至存储组件。本申请实施例可以解决相关技术中模乘计算耗时较长，且计算效率较低的技术问题。

Description

模乘运算电路、方法、数据处理芯片和电子设备

技术领域

本申请涉及数据处理技术领域，具体涉及一种模乘运算电路、方法、数据处理芯片和电子设备。

背景技术

现在人们越来越重视数据的安全性，尤其是在数据传输过程中的安全性。所以，在进行数据传输时，通常会采用加密算法对数据加密，常见的加密算法包括RSA密码算法、椭圆曲线密码算法、Paillier密码算法等。上述加密算法需要对大整数进行模乘和模幂运算，蒙哥马利运算是一种执行模乘运算的快速方法，但在计算之前需要转换到蒙哥马利域，计算后变换为正常域才能获取最终计算结果。由于域转换增加了模乘运算的计算量，需要耗费较多时钟周期，导致模乘计算任务耗时较长、模乘计算效率较低。

发明内容

鉴于上述问题，本申请提供一种模乘运算电路、方法、数据处理芯片和电子设备，以至少相关技术中模乘计算耗时较长，且计算效率较低的技术问题。

根据本申请实施例的第一方面，提供了一种模乘运算电路，包括：存储组件，用于存储计算数据，上述计算数据包括第一乘数、第二乘数和除数；计算组件，与上述存储组件连接，用于将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于上述多项式中的各个项对上述除数进行模约减运算，以确定上述第一乘数、上述第二乘数和上述除数的目标模值；控制组件，与上述存储组件及上述计算组件连接，用于控制上述计算组件从上述存储组件中读取上述计算数据，并将上述计算组件输出的计算结果存储至上述存储组件。

根据本申请实施例的第二方面，提供了一种模乘运算方法，应用于上述第一方面的模乘运算电路，上述模乘运算方法包括：接收模乘运算指令，上述模乘运算指令中携带第一乘数、第二乘数和除数；响应于上述模乘运算指令，将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于上述多项式中的各个项对上述除数进行模约减运算得到模约减值，以确定上述第一乘数、上述第二乘数和上述除数的目标模值。

根据本申请实施例的第三方面，提供了一种数据处理芯片，包括上述第一方面的模乘运算电路。

根据本申请实施例的第四方面，还提供了一种电子设备，包括上述第三方面的数据处理芯片。

根据本申请实施例的第五方面，还提供了一种计算机可读的存储介质，该计算机可读的存储介质中存储有计算机程序，其中，该计算机程序被设置为运行时执行上述第二方面的模乘运算方法。

在本申请实施例中，将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于上述多项式中的各个项对上述除数进行模约减运算，以确定上述第一乘数、上述第二乘数和上述除数的目标模值，上述电路无需进行蒙哥马利域转换，即无需在模乘前后进出蒙哥马利域，减少了模乘计算过程中的循环次数，同时减少模乘计算任务的耗时，从而能够提高模乘计算效率。

附图说明

通过阅读对下文优选实施方式的详细描述，各种其他的优点和益处对于本领域普通技术人员将变得清楚明了。附图仅用于示出优选实施方式的目的，而并不认为是对本申请的限制。而且在全部附图中，用相同的附图标号表示相同的部件。在附图中：

图1是根据本申请实施例的一种可选的模乘运算电路的示意图；

图2是根据本申请实施例的另一种可选的模乘运算电路的示意图；

图3是根据本申请实施例的另一种可选的模乘运算电路的示意图；

图4是根据本申请实施例的又一种模乘运算电路的示意图；

图5是根据本申请实施例的另一种可选的模乘运算电路的示意图；

图6是根据本申请实施例的一种乘法器的计算过程示意图；

图7是根据本申请实施例的另一种可选的模乘运算电路的示意图；

图8是根据本申请实施例的另一种可选的模乘运算电路的示意图；

图9是根据本申请实施例的一种可选的模乘运算电路中模约减计算器的示意图；

图10是本申请实施例提供的一种模乘运算方法的流程示意图；

图11是本申请实施例提供的一种模乘运算装置的结构示意图。

具体实施方式

为了使本技术领域的人员更好地理解本发明方案，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分的实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都应当属于本发明保护的范围。

需要说明的是，本发明的说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的本发明的实施例能够以除了在这里图示或描述的那些以外的顺序实施。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，例如，包含了一系列步骤或单元的过程、方法、系统、产品或设备不必限于清楚地列出的那些步骤或单元，而是可包括没有清楚地列出的或对于这些过程、方法、产品或设备固有的其它步骤或单元。

相关技术中，加密算法需要对大整数进行模乘和模幂运算，以大整数a，b和m为例，模乘是为了计算a*b(mod m)，即a与b相乘，再对m取模。普通算法中，在计算模m时，利用的是带余除法，除法运算需要太多次乘法，计算复杂度较高。而蒙哥马利算法的思想就是利用进制表示简化除法运算，将除法运算转化为位运算。

传统的蒙哥马利模乘具体实现过程如下：

在模乘器输入操作数a和b，以及模数m，通常a和b均小于m。然后模乘器基于预设程序进行模乘运算，并输出模乘结果d’＝a**^-n。计算过程中，先令初始参数等于1，并定义i＝1至v-1(步长为1)，然后另t等于t*t*mmodr。之后另t等于r-t。且为d’设定初始值0，再定义i＝0、1、2…n-1(步长为1)，计算q＝(a₀*_i+’₀)*modr，以及d’＝(a*b_i+’+*)·^-1。并且，当d’≥m时，使d’等于d’-进行迭代。

其中，a*b_i+’+*这里有如下的n轮运算，经过n轮运算之后，得到的结果除以r。

(1)a₀*_i+0+*₀(根据多位数乘法的运算规则,得到的结果高位h₀与下一轮相加，低位l₀保留)；

(2)a₁*_i+h₀+*₁(高位为h₁，低位为l₁，保留低位)；

(3)a₂*_i+h₁+*₂(高位为h₂，低位为l₂，保留低位)；

(4)a₃*_i+h₂+*₃(高位为h₃，低位为l₃，保留低位)；

(5)a_n-1*_i+h_n-2+*_n-1(高位为h_n-1，低位为l_n-1,最后一轮运算高位和低位全部保留)。

在上述流程中，r表示操作数(进行运算操作的数据)的进制，比如在传统的计算机中，操作数均为二进制的形式，那么此时r＝2；n表示为n在r进制下的位数。通常在加密过程中操作数都是二进制数。

例如，若计算a·b(mod m)，则仅需调用蒙哥马利模乘4次即可。令ρ＝r²ⁿ mod m：

(1)A＝MontMul(a，ρ)＝a*rⁿ mod m；

(2)B＝MontMul(b，ρ)＝b*rⁿ mod m；

(3)D＝MontMul(A，B)＝a*b·rⁿ mod m；

(4)d＝MontMul(D，1)＝a*b mod m。

上述第(4)步得到的结果d即为蒙哥马利模乘的计算结果。其中(1)、(2)步称之为进入蒙哥马利域，即将操作数a，b变为a*rⁿ mod m，b*rⁿ mod m的形式；第(4)步称之为退出蒙哥马利域，即由a·b*rⁿ mod m恢复为a·b mod m。MontMul()为蒙哥马利模乘函数。

从上述蒙哥马利运算过程可以看出，在模乘计算之前需要转换到蒙哥马利域，计算后变换为正常域才能获取最终计算结果。由于域转换增加了模乘运算的计算量，需要耗费较多时钟周期，导致模乘计算任务的时间花费过长、模乘计算效率较低，同时也会导致模乘电路的耗电量和发热量过大。

为了解决上述技术问题，作为一种可选地实施方式，如图1所示，本申请实施例提供了一种模乘运算电路，包括：

存储组件，用于存储计算数据，上述计算数据包括第一乘数、第二乘数和除数；

计算组件，与上述存储组件连接，用于将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于上述多项式中的各个项对上述除数进行模约减运算，以确定上述第一乘数、上述第二乘数和上述除数的目标模值；

控制组件，与上述存储组件及上述计算组件连接，用于控制上述计算组件从上述存储组件中读取上述计算数据，并将上述计算组件输出的计算结果存储至上述存储组件。

具体地，在本申请实施例中，上述存储组件包括但不限于为多个寄存器组成的寄存器组，该存储组件可以存储用于模乘计算的第一乘数、第二乘数和除数，以及用于存储模乘运算过程得到的计算数据。

以a·b(mod m)为例，这里的第一乘数为a、第二乘数b，或者第一乘数为b，第二乘数为a；a和b均小于m，且a，b均为正整数。例如，计算组件可以将上述a·b的乘法运算的表达式转换为多项式：a*2⁰*b₀+a*2^k*b₁+a*2^2k*b₂+…+a*2^kn*b_n，k为正整数；然后根据取模运算的计算规则，将该多项式中的各个项对上述除数m进行模约减运算，各项对除数m进行模运算，得到多个模值的累加和，然后将该累加和对除数m进行模运算后可以得到a·b(mod m)的目标模值。即a*b(mod m)＝(a*2⁰*b₀(mod m)+a*2^k*b₁(mod m)+a*2^2k*b₂(mod m)+…+a*2^kn*b_n(mod m))mod m。

在本申请实施例中，将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于上述多项式中的各个项对上述除数进行模约减运算，以确定上述第一乘数、上述第二乘数和上述除数的目标模值，上述电路无需进行蒙哥马利域转换，即无需在模乘前后进出蒙哥马利域，减少了模乘计算过程中的循环次数，同时减少模乘计算任务的耗时，从而能够提高模乘计算效率。

在一个或多个实施例中，上述计算组件，具体用于对上述第一乘数进行位数分解，得到多个乘数因子以及各个乘数因子对应的位数参数；基于各乘数因子及各乘数因子对应的位数参数，将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式。

上述多项式中各项分别包括上述第二乘数、一个乘数因子与上述一个乘数因子对应的位数参数三者的乘积，上述各项包括的乘数因子各不相同。

具体地，这里以第一乘数为b，第二乘数为a为例，上述计算组件对上述第一乘数b对应的二进制数进行位数分解，得到多个乘数因子b₀，b₁，…，b_n。其中，乘数因子b₀对应的位数参数为2⁰，乘数因子b₁对应的位数参数为2^k，乘数因子b_n对应的位数参数为2^kn。多项式中的其中一项，例如包括第二乘数a、一个乘数因子b₁以及b₁对应的位数参数2^k三者的乘积a*2^k*b₁。

在一个或多个实施例，上述计算组件，还用于分别计算上述各项中上述第二乘数与位数参数的乘积与上述除数之间的模约减值，以及对于上述各项，计算项对应的模约减值与项中的乘数因子的乘积。将各项计算出的乘积进行求和，将得到的和值与上述除数进行模约减运算得到上述目标模值。

具体地，以第一乘数为b，第二乘数为a为例，(a*2⁰*b₀(mod m)+a*2^k*b₁(mod m)+a*2^2k*b₂(mod m)+…+a*2^kn*b_n(mod m))mod m。将该公式中的多项式进行变形可以得到如下公式：

a*b(mod m)＝(a*2⁰(mod m)*b₀+a*2^k(mod m)*b₁+a*2^2k(mod m)*b₂+…+a*2^kn(modm)*b_n)mod m。

计算组件分别计算上述各项中a*2⁰(mod m)，a*2^k(mod m)至a*2^kn(mod m)各自对应的模约减值，然后计算各项对应的模约减值与项中的乘数因子的乘积，即计算a*2⁰(modm)*b₀，a*2^k(mod m)*b₁至a*2^kn(mod m)*b_n各自所得的乘积，将各项计算出的乘积进行求和，将得到的和值，即该多项式a*2⁰(mod m)*b₀+a*2^k(mod m)*b₁+a*2^2k(mod m)*b₂+…+a*2^kn(mod m)*b_n对应的和值与上述除数m进行模约减运算可以得到上述目标模值。

在一个或多个实施例中，如图2所示，上述计算组件包括混合运算单元和模约减计算器；

上述混合运算单元，用于在当前迭代周期内计算当前迭代周期对应的模约减值与所需计算的项中的乘数因子的乘积，将计算的乘积与当前迭代周期前各周期计算的乘积累加，得到当前迭代周期的累加乘积。

具体地，在本申请实施例中，这里以第一乘数为b，第二乘数为a为例，上述计算组件对上述第一乘数b的二进制数进行位数分解，根据位数分解的个数确定迭代计算的轮次，假设b为2478，其二进制数(100110101110)按照4个预设位数为基准进行位数分解得到3个乘数因子：b₀＝14(b’1110)，b₁＝10(b’1010)，b₂＝9(b’1001)，迭代计算的轮次可以确定为3轮。以各迭代周期的累加乘积c_i＝c_i-1+b_ir_i为累加公式，r_i为各迭代周期对应的模约减值，在每个迭代周期中，第一轮迭代周期取累加乘积c₁＝0+14*r₀；第二轮迭代周期累加乘积c₁＝14*r₀+10*r₁，最后一轮迭代周期的累加乘积c₂＝14*r₀+10*r₁+9*r₂。

上述模约减计算器，用于对当前迭代周期的上一周期的模约减值向左移位预设位数得到移位值，以及将上述移位值与上述除数进行模约减运算得到当前迭代周期对应的模约减值，上述当前迭代周期为上述模乘运算中除第一周期和最后一个周期之外的任一周期，上述第一周期的模约减值为上述第二乘数。将最后一个迭代周期的前一迭代周期对应的累加乘积，与上述除数进行模约减运算得到上述目标模值。

具体地，由于第二乘数a小于除数m，因此第一迭代周期的对应的模约减值为a；在第二个迭代周期，模约减计算器对上一周期的模约减值a向左移位预设位数得到移位值a<<k，这里k为预设位数，通过模约减函数QR当前迭代周期对应的模约减值r₁＝QR(a<<k，m，k)。在最后一个迭代周期的前一迭代周期对应的累加乘积c₂与上述除数进行模约减运算得到上述目标模值。

在一个或多个实施例中，如图3所示，上述混合运算单元包括第一乘法器和第一加法器，上述第一乘法器与第一加法器相连接。

上述第一乘法器，用于计算当前迭代周期所需计算的项的乘数因子与当前迭代周期对应的模约减值的乘积。

具体地，例如，在第一轮迭代周期，第一乘法器将当前迭代周期所需计算的项的乘数因子b₀＝14与当前迭代周期对应的模约减值r₁的乘积；在第二轮迭代周期，第一乘法器将当前迭代周期所需计算的项的乘数因子b₀＝10与当前迭代周期对应的模约减值r₁的乘积。

上述第一加法器，用于将当前迭代周期的乘积与当前迭代周期前一周期对应的累加乘积相加，得到当前迭代周期的累加乘积。

具体地，例如在第二轮迭代周期，将当前迭代周期的乘积10*r₁与当前迭代周期前一周期对应的累加乘积14*r₁相加，得到当前迭代周期的累加乘积14*r₀+10*r₁。

在一个或多个实施例中，如图4所示，上述混合运算单元包括第二乘法器和第二加法器，上述第二乘法器与第二加法器相连接。

上述第二乘法器，用于将当前迭代周期对应的模约减值分解为上述预设位数的多个累加乘数因子；分别计算各个累加乘数因子与所需计算的项中的乘数因子的乘积，将计算的各个乘积的高预设位数值按位数依次进行拼接得到第一拼接值，将计算的各个乘积的低预设位数值按位数依次进行拼接得到第二拼接值。

上述第二加法器，用于将上述当前迭代周期的前一周期的累加乘积、上述第一拼接值和第二拼接值相累加，得到当前迭代周期的累加乘积。

具体地，如图6所示，假设第一乘数为b_i分解后的每个乘数因子的位数为64位，例如当前迭代周期对应的模约减值r分解为64位的多个累加乘数因子；为了提高计算效率，节省计算时间，分别计算各个累加乘数因子{r_1，r_2，…，r_8}与所需计算的当前项中的乘数因子b_i的乘积，r_1*b_i后得到0至128位区间内128位的数值，r_2*b_i后得到128至256位区间内128位的数值，以此类推，直至得到r_8*b_i。将计算的各个乘积的高64位值按位数依次进行拼接得到第一拼接值res_1，将计算的各个乘积的低64数值按位数依次进行拼接得到第二拼接值res_2。

上述第二加法器，将上述当前迭代周期的前一周期的累加乘积、上述第一拼接值res_1和第二拼接值res_2相累加，得到当前迭代周期的累加乘积。

在一个或多个实施例中，上述模约减计算器，具体用于对上述移位值向右移位得到乘数高位值，以及对上述除数向右移位得到除数高位值。

将取模运算中上述乘数高位值除以上述除数高位值的除法运算转换为乘法运算，得到约减余数，并对上述约减余数进行修正得到模约减值。

具体地，在本申请实施例中，模约减函数QR的计算过程利用两次近似过程计算定长输入的约减结果。首先是高有效位预估，利用高位估计商值，此处商值会出现1以内的负误差；然后通过巴雷特算法，把除法转化为乘法，此时商值会出现1以内的负误差，此时的商值共计2以内的负误差。把商值加1后误差调整为1以内的正负误差。利用有误差的预估商计算约减余数，然后对该余数进行误差修正得到最终约减结果，即模约减值。

例如，在第一迭代周期，r₁＝QR(a<<k，m，k)，具体计算过程中，，将移位值(a<<k)向右进行移位得到乘数高位值a′，以及对上述除数m向右移位得到除数高位值移位的位数为l-△-2，l为第二乘数b的位数，△为当前迭代周期的移位值(a<<k)比m多的最大位数。通过巴雷特算法将取模运算中上述乘数高位值a′除以上述除数高位值的除法运算转换为乘法运算，r₁’＝(a<<k)-(γ+1)m，γ＝(a′m′)，得到约减余数r₁’，将约减余数r₁’进行修正后，可以得到第一周期的模约减值r₁。

在一个或多个实施例中，如图5所示，上述模约减计算器包括依次相连接的除法器、第三乘法器、第三加法器和修正器；

上述除法器，用于将上述乘数高位值除以上述除数高位值的除法运算转换为乘法运算，并确定当前迭代周期的约减参数，上述约减参数用于表征当前迭代周期的移位值除以上述除数得到的商值。

具体地，本申请实施例中的除法器包括但不限于利用巴雷特约减算法，将上述乘数高位值除以上述除数高位值的除法运算转换为乘法运算，并确定当前迭代周期的约减参数，例如在第一迭代周期，在第一迭代周期，r₁＝QR(a<<k，m，k)，具体计算过程中，将移位值(a<<k)向右进行移位得到乘数高位值a′，以及对上述除数m向右移位得到除数高位值移位的位数为l-△-2，l为第二乘数b的位数，△为当前迭代周期的移位值(a<<k)比m多的最大位数。约减参数为通过巴雷特算法进行推导，得到约减参数为γ＝(a′m′)。

上述第三乘法器，用于计算上述约减参数与预设数值之和得到第一加和值；将第一加和值与上述除数的相反数的补码值相乘，得到运算乘积。

具体地，这的预设数值通常取值为1，即第一加和值为γ+1，由于约减参数r₁’＝(a<<k)-(γ+1)m，由于-m为负数，这里用上述除数m的相反数的补码值来表示，得到运算乘积-(γ+1)m。

第三加法器，用于将上述第三乘法器输出的运算乘积和当前迭代周期的移位值相加得到第二加和值。

具体地，将-(γ+1)m与当前迭代周期的移位值(a<<k)相加，得到第二加和值(a<<k)-(γ+1)m。

上述修正器，用于判断上述第二加和值是否小于零，并根据判断结果对上述第二加和值进行调整，得到上述目标模值。

具体地，上述修正器根据(a<<k)-(γ+1)m是否小于零，并根据判断结果对上述第二加和值进行调整，得到上述目标模值。

在一个或多个实施例中，上述修正器，具体用于在上述第二加和值小于零的情况下，将上述第二加和值与除数相加得到上述目标模值；

在上述第二加和值大于等于零的情况下，若确定上述第二加和值小于上述除数，将上述第二加和值确定为上述目标模值；若确定上述第二加和值大于上述除数，将上述第二加和值减去上述除数的差值确定为上述目标模值。

具体地，第二加和值r₁’＝(a<<k)-(γ+1)m，若r₁’小于上述除数m，将上述r₁’确定为上述目标模值；当确定上述第二加和值r₁’大于上述除数m，将上述第二加和值m减去上述除数m的差值确定为上述目标模值。

在一个或多个实施例中，如图7所示，上述计算组件还包括多路选择器，上述多路选择器，用于从上述存储组件选择上述混合运算单元在各迭代周期所需的数据输入上述混合运算单元，从上述存储组件选择上述模约减计算器在各迭代周期所需的数据输入至上述模约减计算器。具体地，这里各迭代周期所需的数据包括但不限于，第一乘数，第二乘数，除数，每个迭代周期的周期数，每个迭代周期的模约减值，累加乘积等。

在一个或多个实施例中，在当前迭代周期不是最后一个周期的情况下，上述混合运算单元和模约减计算器为并行计算的单元。

具体地，在本申请实施例中，为了提高模乘的计算效率，这里在当前迭代周期不是最后一个周期的情况下，将上述混合运算单元和模约减计算器配置为并行计算的单元。

在一个或多个实施例中，如图8所示，上述模乘运算电路包括，寄存器组，用于存储计算数据；上述计算数据包括第一乘数a、第二乘数b和除数m；a，b，m均为正整数，上述除数m为奇数，a，b均小于上述除数m；c为每个迭代周期的累加乘积，k为进行移位操作的预设位数，nxt_c为当前迭代周期的累加乘积，cnt为当前迭代周期的周期数。

计算组件包括乘法器、加法器、模约减计算器和多个多路选择器。

该乘法器包括上述实例中的第一乘法器或第二乘法器；该加法器包括上述实施例中的第一加法器或第二加法器。

模约减计算器，用于对当前迭代周期的上一周期的模约减值向左移位预设位数得到移位值，以及将上述移位值与上述除数进行模约减运算得到当前迭代周期对应的模约减值，上述当前迭代周期为上述模乘运算中除第一周期和最后一个周期之外的任一周期，上述第一周期的模约减值为上述第二乘数；将最后一个迭代周期的前一迭代周期对应的累加乘积，与上述除数进行模约减运算得到上述目标模值。

多路选择器，用于从上述存储组件选择上述混合运算单元在各迭代周期所需的数据输入上述混合运算单元，从上述存储组件选择上述模约减计算器在各迭代周期所需的数据输入至上述模约减计算器。

在一实施例中，如图9所示，模约减计算器包括巴雷特(Barrett)除法器，乘法器，加法器，修正器。该实施例中的乘法器包括上述的第三乘法器，加法器包括上述的第三加法器。

在一个或多个实施例中，如图10所示，本申请实施例还提供了一种模乘运算方法，应用于上述任一实施例中的模乘运算电路，该方法包括：

S1002，接收模乘运算指令，上述模乘运算指令中携带第一乘数、第二乘数和除数；

S1004，响应于上述模乘运算指令，将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于上述多项式中的各个项对上述除数进行模约减运算得到模约减值，以确定上述第一乘数、上述第二乘数和上述除数的目标模值。

在本申请实施例中，根据将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于上述多项式中的各个项对上述除数进行模约减运算，以确定上述第一乘数、上述第二乘数和上述除数的目标模值，上述电路无需进行蒙哥马利域转换，即无需在模乘前后进出蒙哥马利域，减少了模乘计算过程中的循环次数，同时减少模乘计算任务的耗时，从而能够提高模乘计算效率。

在一个或多个实施例中，上述将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式，包括：

对上述第一乘数进行位数分解，得到多个乘数因子以及各个乘数因子对应的位数参数；基于各乘数因子及各乘数因子对应的位数参数，将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式；其中，上述多项式中各项分别包括上述第二乘数、一个乘数因子与上述一个乘数因子对应的位数参数三者的乘积，上述各项包括的乘数因子各不相同；

上述基于上述多项式中的各个项对上述除数进行模约减运算得到模约减值，以确定上述第一乘数、上述第二乘数和上述除数的目标模值，包括：

分别计算上述各项中上述第二乘数与位数参数的乘积与上述除数之间的模约减值，以及对于上述各项计算项对应的模约减值与项中的乘数因子的乘积；

将各项计算出的乘积进行求和，将得到的和值与上述除数进行模约减运算得到上述目标模值。

在一个或多个实施例中，上述分别计算上述各项中上述第二乘数与位数参数的乘积与上述除数之间的模约减值，以及对于上述各项计算项对应的模约减值与项中的乘数因子的乘积；

将各项计算出的乘积进行求和，将得到的和值与上述除数进行模约减运算得到上述目标模值，包括：

对当前迭代周期的上一周期的模约减值向左移位预设位数得到移位值，以及将上述移位值与上述除数进行模约减运算得到当前迭代周期对应的模约减值，上述当前迭代周期为上述模乘运算中除第一周期和最后一个周期之外的任一周期，上述第一周期的模约减值为上述第二乘数；

在当前迭代周期内计算当前迭代周期对应的模约减值与所需计算的项中的乘数因子的乘积，将计算的乘积与当前迭代周期前各周期计算的乘积累加，得到当前迭代周期的累加乘积；

将最后一个迭代周期的前一迭代周期对应的累加乘积，与上述除数进行模约减运算得到上述目标模值。

基于上述实施例，以第一乘数a、第二乘数b和除数m，k为进行移位操作的预设位数，c为每个周期的迭代乘积为例来说明本申请计算a*b(mod m)的过程，

对个计算数据进行初始化，计算a，b，m对应的二进制数。

m＝3115(b’1100 0010 1011)；

a＝3002(b’1011 1011 1010)；

b＝2478(b’1001 1010 1110)[b0＝14(b’1110)b1＝10(b’1010)b2＝9(b’1001]；

k＝4；

第一迭代周期:

当前周期累加乘积c₁＝0+14*3002＝42028；

当前周期操作值a＝3002<<4＝48032；

当前周期模约减值r₁＝QR(48032,3115,4)＝1307；

m’＝1024/48＝20(b’010101)；

a’＝48032>>6＝750(b’1011101110)；

γ＝(750*21)>>10＝15(b’1111)；

r₁’＝48032-16*3115＝-1808；

r₁＝-1808+3115＝1307；

第二迭代周期:

当前周期累加乘积c₂＝42028+10*1307＝55098；

当前周期移位操作值r₁＝1307<<4＝20912；

当前周期模约减值r₂＝QR(20912,3115,4)＝2222；

m’＝1024/48＝20(b’010101)；

a’＝20912>>6＝326(b’0101000110)；

γ＝(326*21)>>10＝6(b’0110)；

r₂’＝20912-7*3115＝-893；

r₂＝-893+3115＝2222；

第三迭代周期:

当前周期累加乘积c₃＝55098+9*2222＝75096；

当前周期模约减值r₃＝QR(75096,3115,6)＝336；

m’＝16384/194＝84(b’01010100)；

a’＝75096>>4＝4693(b’01001001010101)；

γ＝(4693*84)>>14＝24(b’011000)；

r₃’＝75096-25*3115＝-2779；

r₃＝-2779+3115＝336；

最后得到a*b(mod m)的目标模值为336。

需要说明的是，对于前述的各方法实施例，为了简单描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本发明并不受所描述的动作顺序的限制，因为依据本发明，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例，所涉及的动作和模块并不一定是本发明所必须的。

根据本申请实施例的另一个方面，还提供了一种用于实施上述模乘运算方法的模乘运算装置。如图11所示，该装置包括：

接收单元1102，接收模乘运算指令，上述模乘运算指令中携带第一乘数、第二乘数和除数；

转换计算单元1104，响应于上述模乘运算指令，将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于上述多项式中的各个项对上述除数进行模约减运算得到模约减值，以确定上述第一乘数、上述第二乘数和上述除数的目标模值。

在本申请实施例中，将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于上述多项式中的各个项对上述除数进行模约减运算，以确定上述第一乘数、上述第二乘数和上述除数的目标模值，上述电路无需进行蒙哥马利域转换，即无需在模乘前后进出蒙哥马利域，减少了模乘计算过程中的循环次数，同时减少模乘计算任务的耗时，从而能够提高模乘计算效率。

在一个或多个实施例中，上述转换计算单元1104，包括：

分解模块，用于对上述第一乘数进行位数分解，得到多个乘数因子以及各个乘数因子对应的位数参数；基于各乘数因子及各乘数因子对应的位数参数，将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式；其中，上述多项式中各项分别包括上述第二乘数、一个乘数因子与上述一个乘数因子对应的位数参数三者的乘积，上述各项包括的乘数因子各不相同；

计算模块，用于分别计算上述各项中上述第二乘数与位数参数的乘积与上述除数之间的模约减值，以及对于上述各项计算项对应的模约减值与项中的乘数因子的乘积；

将各项计算出的乘积进行求和，将得到的和值与上述除数进行模约减运算得到上述目标模值。

在一个或多个实施例中，上述计算模块，包括：

移位子单元，用于对当前迭代周期的上一周期的模约减值向左移位预设位数得到移位值，以及将上述移位值与上述除数进行模约减运算得到当前迭代周期对应的模约减值，上述当前迭代周期为上述模乘运算中除第一周期和最后一个周期之外的任一周期，上述第一周期的模约减值为上述第二乘数；

累加单元，用于在当前迭代周期内计算当前迭代周期对应的模约减值与所需计算的项中的乘数因子的乘积，将计算的乘积与当前迭代周期前各周期计算的乘积累加，得到当前迭代周期的累加乘积；

模约减子单元，用于将最后一个迭代周期的前一迭代周期对应的累加乘积，与上述除数进行模约减运算得到上述目标模值。

根据本申请实施例的又一个方面，还提供了一种包括上述任一实施例中模乘运算电路的数据处理芯片。该数据处理芯片在进行模乘运算时无需进行蒙哥马利域转换，即无需在模乘前后进出蒙哥马利域，减少了模乘计算过程中的循环次数，同时减少模乘计算任务的耗时，从而能够提高模乘计算效率，还能降低耗电量和发热量。

根据本申请实施例的又一个方面，还提供了一种包括上述数据处理芯片的电子设备。可选地，在本实施例中，上述电子设备可以为计算机网络的多个网络设备中的至少一个网络设备。

在其他实施例中，上述电子设备可以是一个分布式系统中的一个节点，其中，该分布式系统可以为区块链系统，该区块链系统可以是由该多个节点通过网络通信的形式连接形成的分布式系统。其中，节点之间可以组成点对点(P2P，Peer To Peer)网络，任意形式的计算设备，比如服务器、终端等电子设备都可以通过加入该点对点网络而成为该区块链系统中的一个节点。

在一个或多个实施例中，本申请还提供了一种计算机程序产品或计算机程序，该计算机程序产品或计算机程序包括计算机指令，该计算机指令存储在计算机可读存储介质中。计算机设备的处理器从计算机可读存储介质读取该计算机指令，处理器执行该计算机指令，使得该计算机设备执行上述的模乘运算方法。其中，该计算机程序被设置为运行时执行上述任一项方法实施例中的步骤。

可选地，在本实施例中，上述计算机可读的存储介质可以被设置为存储用于执行以下步骤的计算机程序：

S1，接收模乘运算指令，上述模乘运算指令中携带第一乘数、第二乘数和除数；

S2，响应于上述模乘运算指令，将上述第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于上述多项式中的各个项对上述除数进行模约减运算得到模约减值，以确定上述第一乘数、上述第二乘数和上述除数的目标模值。

可选地，在本实施例中，本领域普通技术人员可以理解上述实施例的各种方法中的全部或部分步骤是可以通过程序来指令终端设备相关的硬件来完成，该程序可以存储于一计算机可读存储介质中，存储介质可以包括：闪存盘、只读存储器(Read-Only Memory，ROM)、随机存取器(Random Access Memory，RAM)、磁盘或光盘等。

上述本申请实施例序号仅仅为了描述，不代表实施例的优劣。

上述实施例中的集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在上述计算机可读取的存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在存储介质中，包括若干指令用以使得一台或多台计算机设备(可为个人计算机、服务器或者网络设备等)执行本发明各个实施例方法的全部或部分步骤。

在本发明的上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其他实施例的相关描述。

在本申请所提供的几个实施例中，应该理解到，所揭露的客户端，可通过其它的方式实现。其中，以上所描述的装置实施例仅仅是示意性的，例如单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，单元或模块的间接耦合或通信连接，可以是电性或其它的形式。

作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

另外，在本申请各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

以上仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。

本申请所涉及的用户信息(包括但不限于用户设备信息、用户个人信息等)和数据(包括但不限于用于分析的数据、存储的数据、展示的数据等)，均为经用户授权或者经过各方充分授权的信息和数据，并且相关数据的收集、使用和处理需要遵守相关国家和地区的相关法律法规和标准，并提供有相应的操作入口，供用户选择授权或者拒绝。

Claims (15)

1.一种模乘运算电路，其特征在于，包括：

存储组件，用于存储计算数据，所述计算数据包括第一乘数、第二乘数和除数；

计算组件，与所述存储组件连接，用于将所述第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于所述多项式中的各个项对所述除数进行模约减运算，以确定所述第一乘数、所述第二乘数和所述除数的目标模值；

控制组件，与所述存储组件及所述计算组件连接，用于控制所述计算组件从所述存储组件中读取所述计算数据，并将所述计算组件输出的计算结果存储至所述存储组件。

2.根据权利要求1所述的电路，其特征在于，所述计算组件，具体用于对所述第一乘数进行位数分解，得到多个乘数因子以及各个乘数因子对应的位数参数；基于各乘数因子及各乘数因子对应的位数参数，将所述第一乘数和第二乘数的乘法运算的表达式转换为多项式；

所述多项式中各项分别包括所述第二乘数、一个乘数因子与所述一个乘数因子对应的位数参数三者的乘积，所述各项包括的乘数因子各不相同。

3.根据权利要求2所述的电路，其特征在于，所述计算组件，还用于分别计算所述各项中所述第二乘数与位数参数的乘积与所述除数之间的模约减值，以及对于所述各项，计算项对应的模约减值与项中的乘数因子的乘积；

将各项计算出的乘积进行求和，将得到的和值与所述除数进行模约减运算得到所述目标模值。

4.根据权利要求3所述的电路，其特征在于，所述计算组件包括混合运算单元和模约减计算器；

所述混合运算单元，用于在当前迭代周期内计算当前迭代周期对应的模约减值与所需计算的项中的乘数因子的乘积，将计算的乘积与当前迭代周期前各周期计算的乘积累加，得到当前迭代周期的累加乘积；

所述模约减计算器，用于对当前迭代周期的上一周期的模约减值向左移位预设位数得到移位值，以及将所述移位值与所述除数进行模约减运算得到当前迭代周期对应的模约减值，所述当前迭代周期为所述模乘运算中除第一周期和最后一个周期之外的任一周期，所述第一周期的模约减值为所述第二乘数；

将最后一个迭代周期的前一迭代周期对应的累加乘积，与所述除数进行模约减运算得到所述目标模值。

5.根据权利要求4所述的电路，其特征在于，所述混合运算单元包括第一乘法器和第一加法器，所述第一乘法器与第一加法器相连接；

所述第一乘法器，用于计算当前迭代周期所需计算的项的乘数因子与当前迭代周期对应的模约减值的乘积；

所述第一加法器，用于将当前迭代周期的乘积与当前迭代周期前一周期对应的累加乘积相加，得到当前迭代周期的累加乘积。

6.根据权利要求4所述的电路，其特征在于，所述混合运算单元包括第二乘法器和第二加法器，所述第二乘法器与第二加法器相连接；

所述第二乘法器，用于将当前迭代周期对应的模约减值分解为所述预设位数的多个累加乘数因子；分别计算各个累加乘数因子与所需计算的项中的乘数因子的乘积，将计算的各个乘积的高预设位数值按位数依次进行拼接得到第一拼接值，将计算的各个乘积的低预设位数值按位数依次进行拼接得到第二拼接值；

所述第二加法器，用于将所述当前迭代周期的前一周期的累加乘积、所述第一拼接值和第二拼接值相累加，得到当前迭代周期的累加乘积。

7.根据权利要求4至6任一项所述的电路，其特征在于，所述模约减计算器，具体用于对所述移位值向右移位得到乘数高位值，以及对所述除数向右移位得到除数高位值；

将取模运算中所述乘数高位值除以所述除数高位值的除法运算转换为乘法运算，得到约减余数，并对所述约减余数进行修正得到模约减值。

8.根据权利要求7所述的电路，其特征在于，所述模约减计算器包括依次相连接的除法器、第三乘法器、第三加法器和修正器；

所述除法器，用于将所述乘数高位值除以所述除数高位值的除法运算转换为乘法运算，并确定当前迭代周期的约减参数，所述约减参数用于表征当前迭代周期的移位值除以所述除数得到的商值；

所述第三乘法器，用于计算所述约减参数与预设数值之和得到第一加和值；将第一加和值与所述除数的相反数的补码值相乘，得到运算乘积；

第三加法器，用于将所述第三乘法器输出的运算乘积和当前迭代周期的移位值相加得到第二加和值；

所述修正器，用于判断所述第二加和值是否小于零，并根据判断结果对所述第二加和值进行调整，得到所述目标模值。

9.根据权利要求8所述的电路，其特征在于，所述修正器，具体用于在所述第二加和值小于零的情况下，将所述第二加和值与除数相加得到所述目标模值；

在所述第二加和值大于等于零的情况下，若确定所述第二加和值小于所述除数，将所述第二加和值确定为所述目标模值；若确定所述第二加和值大于所述除数，将所述第二加和值减去所述除数的差值确定为所述目标模值。

10.根据权利要求4所述的电路，其特征在于，所述计算组件还包括多路选择器；

所述多路选择器，用于从所述存储组件选择所述混合运算单元在各迭代周期所需的数据输入所述混合运算单元，从所述存储组件选择所述模约减计算器在各迭代周期所需的数据输入至所述模约减计算器。

11.根据权利要求4所述的电路，其特征在于，在当前迭代周期不是最后一个周期的情况下，所述混合运算单元和模约减计算器为并行计算的单元。

12.一种模乘运算方法，其特征在于，应用于权利要求1-11任一项所述的模乘运算电路，所述方法包括：

接收模乘运算指令，所述模乘运算指令中携带第一乘数、第二乘数和除数；

响应于所述模乘运算指令，将所述第一乘数和第二乘数的乘法运算的表达式转换为多项式，基于所述多项式中的各个项对所述除数进行模约减运算得到模约减值，以确定所述第一乘数、所述第二乘数和所述除数的目标模值。

13.一种数据处理芯片，其特征在于，包括如权利要求1 11中任一项所述的模乘运算电路。

14.一种电子设备，其特征在于，包括如权利要求13所述的数据处理芯片。

15.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述程序被处理器执行实现如权利要求12所述方法的步骤。