1.一种蒙哥马利算法在有限域中实现四则运算的硬件实现方法,其特征在于:按照如下步骤1‑3,计算出两个大数在有限域中四则运算的结果,具体的硬件实现方法包括如下步骤:步骤1、进行预处理,大整数模数Q和除数y通过stein算法求出其模逆;
步骤2、通过蒙哥马利预处理模块的蒙哥马利算法将大整数x、y转化成蒙哥马利型式;
步骤3、通过蒙哥马利计算模块的蒙哥马利算法根据外部使能对有限域中的x和y进行四则运算,得出结果,其中:
所述步骤3中,通过蒙哥马利计算模块的蒙哥马利算法根据外部使能对有限域中的x和y进行四则运算,具体为:外部加减法使能时,(X±Y)modQ=(x±y)P mod Q,其中X和Y分别是大整数x、y的蒙哥k马利型式,P为参数且满足P=2,k为大位宽;
外部乘法使能时,(X*Y)mod Q=(x*y*P)*P mod Q,由于式(X*Y)mod Q=(x*y*P)*P mod Q不符合蒙哥马利型式,再进行一次蒙哥马利运算,即(x*y*P)*P*P′mod Q,其中P′为P在mod Q的逆元;
外部除法使能时, 其中y′为y在mod Q的逆元,此时将除法转化为乘法;
步骤2和步骤3中,在蒙哥马利预处理模块和蒙哥马利计算模块中的蒙哥马利算法是通过硬件实现的,具体步骤为:规定x<Q,y<Q,Q<P,且P=2k,其中k=256,512,.....;
步骤2‑1、将上式中参数x,y进行分解位宽处理,令:x={xm,xm‑1,...,x2,x1},其中xi=x[(ni‑1):(i‑1)n],mn=k,y={ym,ym‑1,...,y2,y1},其中yi=y[(ni‑1):(i‑1)n],mn=k;
步骤2‑2、参数Z根据蒙哥马利算法和位宽分解处理得到Zi,n n
Zi={[(S′i+x0)*yimod 2]*Q″}mod 2,其中,Si是大位宽k分解为m个宽度为n的小位宽后,计算第i个Si参数,S′i是中间结果Si的低n位,Q′是满足QQ′=‑1modP的正整数,Q″是Q′的低n位,Zi是大位宽k分解为m个宽度为n的小位宽后,计算第i个Zi参数;
步骤2‑3、结果S根据蒙哥马利算法和分布式处理得到中间结果Si;
其中,S0=0,Q={Qm,Qm‑1,...,Q2,Q1},当迭代m次后Si+1=Sm=(x*y+Z*Q)/P;
所述实现方法包括stein算法模块、蒙哥马利预处理模块和蒙哥马利计算模块三个模块,stein算法模块是通过stein算法实现大整数的模逆运算,用来求取大整数模数Q和除数y的模逆,蒙哥马利预处理模块是通过蒙哥马利算法对大整数x和y进行预处理,转化成进行蒙哥马利运算的蒙哥马利型式,蒙哥马利算法模块是对大整数x和y的蒙哥马利型式进行四则运算,最终得到大整数x和y在有限域中的四则运算的结果,通过分解位宽,形成流水线型式的迭代运算,通过分解大整数x的位宽,降低运算的资源消耗。
2.根据权利要求1所述的蒙哥马利算法在有限域中实现四则运算的硬件实现方法,其特征在于:所述步骤1具体包括如下步骤:步骤1‑1、确定大整数模数Q和两个大整数x、y;
k
步骤1‑2、通过模数Q,确定P=2且P>Q;
步骤1‑3、通过stein算法求出模数Q和除数y的模逆。
3.根据权利要求2所述的蒙哥马利算法在有限域中实现四则运算的硬件实现方法,其特征在于:所述步骤1‑3通过stein算法求出模数Q和除数y的模逆,即Q1Q′=1mod P和YY′=1mod Q,所述stein算法流程如下:‑1
规定d=r mod q,令x=1,y=1,步骤1‑1、判断r是否为1;
步骤1‑2、当r为偶数时,r=r/2;
当x为偶数时,x=x/2,否则x=(x+q)/2;
步骤1‑3、当q为偶数时,q=q/2;
当y为偶数时,y=y/2,否则y=(y+q)/2;
步骤1‑4、当r>q时,r=r‑q,x=x‑y;
否则q=q‑r,y=y‑x;
‑1
步骤1‑5、当r为1时,算法结束,此时x=d=r mod q,其中r、d是任意的正整数,并且满足dr=1modq。
4.根据权利要求1所述的蒙哥马利算法在有限域中实现四则运算的硬件实现方法,其特征在于:所述步骤2通过蒙哥马利预处理模块将大整数x、y转化成蒙哥马利型式的过程为:由蒙哥马利算法得
S=(x*y)P′mod Q
2
xP mod Q=xPP′mod Q
2 2
xPmod Q=(x mod Q*Pmod Q)mod Q,2
令p=Pmod Q,则通过蒙哥马利算法得xP mod Q=xp mod Q。