| 主权项 |
1.一种使用一模数(N)以一乘数(M)乘一被乘数(C)的模数乘法之方法,该被乘数(C),该乘数(M)及该模拟(N)为变数(x)的多项式,该方法包括下列步骤:(a)执行(210)一乘法预计方法以获得一乘法移位値(sZ),该乘法移位値(sZ)以该乘数的次方递增,但不在该乘数多项式内;(b)乘法(214)该变数(x)自乘该乘法移位値(sZ)的次方乘一中间结果多项式(Z),以获得一移位中间结果多项式(Z');(c)执行减法预计方法(212)以获得一减法移位値(sN),该减法移位(sN)等于该移位中间结果多项式(Z)的次数与该模数多项式(N)次数之差;(d)乘法(216)该变数(x)自乘该减法移位値(sN)的次方乘该模数多项式(N),以获得一移位模数多项式(N');(e)求和(218)该移位中间结果多项式(Z')及该被乘数(C)并减去该移位模数多项式(N'),以获得一最新中间结果多项式(Z);及(f)重复(226)步骤(a)至(e)直到所有该乘数(M)的次方完成处理,其中在重复步骤(a)至(e)中,步骤(d)使用前面步骤(e)的该最新中间结果多项式(Z)作为该中间结果多项式(Z),及在步骤(c)使用前面步骤(d)的该移位多项式作为该一模数多项式(N)。2.如申请专利范围第1项之方法,其中该乘法(210)在步骤(d)完成由移位该中间结果多项式(Z)一等于该乘法移位値(sZ)的数字,及其中该乘法(216)在步骤(d)完成由移位该模数多项式(N)一数字等于该减法移位値(sN)。3.如申请专利范围第1项之方法,其中该多项式的系数只能取値“0"或“1",及其中该加法及减法(218)在步骤(e)完成以位元方式XOR运算该中间结果多项式(Z'),该被乘数(C)及该移位模数多项式(N')。4.如申请专利范围第1项之方法,其中该减法预计方法(212)的获得一减法移位値(sN)的该步骤包括下列步骤:决定(414)一辅助移位値(si),致使该模数多项式(N)的次数及前步骤(e)乘以一自乘该辅助移位値(si)的次方的变数的该最新中间结果多项式(Z)的次数相等,及形成(422)该乘法移位値(sZ)及该辅助移位値(si)之差,以获得该减法移位値(sN)。5.如申请专利范围第4项之方法,其中执行该乘法预计方法(210)的该步骤及决定(414)该辅助移位値(si)的该步骤系彼此并列完成。6.如申请专利范围第1项之方法,其中限制该乘法移位値(sZ)至一最大乘法移位値(k),其中执行(210)该乘法移位方法的该步骤包括下列步骤:如果该乘法移位値等于该最大乘法移位値(k),等于该乘法移位値(sZ)及该最大移位値(k),建立(306,324)一乘法预计参数(a)含一预定位,及其中该求和步骤包括下列步骤:如果该乘法预计参数(a)具有该预定値,只求和该预定中间结果多项式(Z')及该移位模数多项式(N')。7.一种使用一模数(N)以一乘数(M)乘一被乘数(C)的模数乘法之装置,该被乘数(C),该乘数(M)及该模数(N)为变数(x)的多项式,该装置包括:(a)用于执行(210)一乘法预计方法以获得一乘法移位値(sZ)的装置,该乘法移位値(sZ)以该乘数的次方递增,但不在乘数多项式内;(b)用于乘以(214)该变数(x)自乘该该乘法移位値(sZ)的次方乘一中间结果多项式(Z)以获得一移位中间结果多项式(Z')的装置;(c)用于执行减法预计方法(212)以获得一减法移位値(sN)的装置,该减法移位値(sN)等于该移位中间结果多项式(Z)次数与该模数多项式(N)次数之差;(d)用于乘法(216)该变数(x)自乘该该减法移位値(sN)的次方乘该模数多项式(N)以获得一移位模数多项式(N')的装置;(e)用于求和(218)该移位中间结果多项式(Z')及该被乘数(C)并减去该移位模数多项式(N')以获得一最新中间结果多项式(Z)的装置;及(f)用于重复控制(226)该装置(a)至(e)直到所有该乘数(M)的次方完成处理的装置,其中在该装置(a)至(e)的重复控制中;该装置用于乘法(214)以获得一移位中间结果多项式经配置以使用先前控制用于求和(218)的该装置的最新中间结果多项式(Z)作为一中间结果多项式(Z),及该用于执行减法预计方法(212)的装置经配置,在重复控制中,作为模拟多项式(N),以使用先前控制用于乘法(216)以获得一移位模数多项式的该装置的该移位模数多项式。8.如申请专利范围第7项之装置,其中完成该装置(214)用于乘法以获得一移位中间结果多项式(Z')及该装置(216)用于乘法以获得一移位模数多项式(N')作为可控制移位暂存器,以根据该乘法移位値(sZ)或该减法移位値(sN),执行一相当数字的暂存器内容移位。9.如申请专利范围第7项之装置,其中用于加法及用于减法的该装置(218)完成该中间结果多项式(Z'),该被乘数(C)及该移位模数多项式(N')的位元方式XOR运算。10.如申请专利范围第7项之装置,该用于加法及减法的装置(218)包括:一计数器(500)含三输入线及二输出线,其中该中间结果多项式(Z)的一位元可施加在第一输入线,其中该被乘数(C)的一位元可施加在第二输入线,及其中该移位模数多项式(N')的一位元可施加在第三输入线;一全加法器(510)含三输入及一输出,该计数器(500)的一低阶输出连接该全加法器(510)的一高阶输入线;一开关(520)连接该计数器(500)的一高阶输出线及一较高阶位元的一全加法器(510)的一中输入之间;及一控制单元(530)用于处理多项式时打开该开关(520)。11.一种使用一模数多项式以一乘数多项式乘一被乘数多项式的乘法计算单元,该被乘数多项式,该乘数多项式及该模数多项式为变数的多项式,或选择性使用一模数整数以一乘数整数乘一被乘数整数,该计算单元包括:(a)用于执行(210)一乘法预计方法以获得一乘法移位値(sZ)的装置,该乘法移位値(sZ)以该乘数的次方递增,但不在乘数多项式内;(b)用于乘法(214)该变数自乘该该乘法移位値(sZ)的次方乘以一中间结果多项式以获得一移位中间结果多项式的装置;(c)用于执行减法预计方法(212)以获得一减法移位値(sN)的装置,该减法移位値(sN)等于该移位中间结果多项式次数与该模数多项式次数之差;(d)用于乘法(216)该变数(x)自乘该减法移位値(sN)的次方乘以该模数多项式以获得一移位模数多项式的装置;(e)用于执行整数运算数的一乘法预计方法及一减法预计方法以获得一整数中间结果及一移位整数模数的装置(710);(f)一三运算数加法器(700)具有一进位取消装置(730)用于结合整数运算数或多项式中间结果,该移位模数多项式及该多项式被乘数;及(g)一控制装置(730)用于控制该进位取消装置,俾使处理多项式运算数时该进位无效,及俾使处理整数运算数时该进位生效。12.如申请专利范围第11项之计算单元,该三运算设加法器具有一进位取消装置包括:一计数器(500)含三输入线及二输出线,其中该中间结果多项式的一位元可施加在第一输入线,其中该被乘数(C)的一位元可施加在第二输入线,及其中该移位模数多项式的一位元可施加在第三输入线;一全加法器(510)含三输入及一输出,该计数器(500)的一低阶输出连接该全加法器(510)的一高阶输入线;一开关(520)连接该计数器(500)的一高阶输出线及一下一高位元的一全加法器(510)的一中输入之间;及一控制单元(530)用于处理多项式时打开该开关(520)。13.如申请专利范围第12项之计算单元,其中提供复数个三运算数加法器,提供的三运算数加法器的数量大于或等于模数整数或多项式整数的数字。图式简单说明:图1为显示GF(2n)的模数指数计算流程图;图2为本发明方法的一高阶流程图;图3为乘法预计方法流程图用于计算乘法移位値;图4为减法预计方法流程图用于计算减法移位値;图5为一部份三运算数加法单元用于GF(2n)算术或Z/NZ算术;图6为一详细图显示进位取消功能;图7为一Z/NZ/GF(2n)计算单元方块图;图8a至8c为示意图显示减法移位値的计算;及图9为用于执行Z/NZ模数乘法的ZDN方法总图。 |
