2021SC@SDUSC
mrmonty.c主要实现蒙哥马利的无除法模运算方法。
这种方法的优点是不需要除法来计算模,缺点是必须要转化为n-residue形式。
针对快速模幂运算这一课题,西方现代数学家提出了大量的解决方案,通常都是先将幂模运算转化为乘模运算。
例如求D=C^15%N
由于:ab % n = (a % n)(b % n) % n
所以令:
C1 =CC % N =C^2 % N
C2 =C1C % N =C^3 % N
C3 =C2C2 % N =C^6 % N
C4 =C3C % N =C^7 % N
C5 =C4C4 % N =C^14 % N
C6 =C5C % N =C^15 % N
即:对于E=15的幂模运算可分解为6 个乘模运算,归纳分析以上方法可以发现:
对于任意指数E,都可采用以下算法计算D=C**E % N:
D=1
WHILE E>0
IF E%2=0
C=CC % N
E=E/2
ELSE
D=DC % N
E=E-1
RETURN D
继续分析会发现,要知道E 何时能整除 2,并不需要反复进行减一或除二的操作,只需验证E 的二进制各位是0 还是1 就可以了,从左至右或从右至左验证都可以,从左至右会更简洁,
设E=Sumi=0 to n,0<=E<=1
则:
D=1
FOR i=n TO 0
D=DD % N
IF E=1
D=DC % N
RETURN D这样,模幂运算就转化成了一系列的模乘运算。
关键代码:
void nres_dotprod(_MIPD_ int n,big *x,big *y,big w)
{
int i;
#ifdef MR_OS_THREADS
miracl *mr_mip=get_mip();
#endif
if (mr_mip->ERNUM) return;
MR_IN(120)
mr_mip->check=OFF;
zero(mr_mip->w7);
for (i=0;i<n;i++)
{
multiply(_MIPP_ x[i],y[i],mr_mip->w0);
mr_padd(_MIPP_ mr_mip->w7,mr_mip->w0,mr_mip->w7);
}
copy(mr_mip->pR,mr_mip->w6);
/* w6 = p.R */
divide(_MIPP_ mr_mip->w7,mr_mip->w6,mr_mip->w6);
redc(_MIPP_ mr_mip->w7,w);
mr_mip->check=ON;
MR_OUT
}
#endif
void nres_negate(_MIPD_ big x, big w)
{
#ifdef MR_OS_THREADS
miracl *mr_mip=get_mip();
#endif
if (size(x)==0)
{
zero(w);
return;
}
#ifdef MR_COMBA
if (mr_mip->ACTIVE)
{
comba_negate(_MIPP_ x,w);
return;
}
else
{
#endif
if (mr_mip->ERNUM) return;
MR_IN(92)
mr_psub(_MIPP_ mr_mip->modulus,x,w);
MR_OUT
#ifdef MR_COMBA
}
#endif
}
void nres_div2(_MIPD_ big x,big w)
{
#ifdef MR_OS_THREADS
miracl *mr_mip=get_mip();
#endif
MR_IN(198)
copy(x,mr_mip->w1);
if (remain(_MIPP_ mr_mip->w1,2)!=0)
add(_MIPP_ mr_mip->w1,mr_mip->modulus,mr_mip->w1);
subdiv(_MIPP_ mr_mip->w1,2,mr_mip->w1);
copy(mr_mip->w1,w);
MR_OUT
}
void nres_div3(_MIPD_ big x,big w)
{
#ifdef MR_OS_THREADS
miracl *mr_mip=get_mip();
#endif
MR_IN(199)
copy(x,mr_mip->w1);
while (remain(_MIPP_ mr_mip->w1,3)!=0)
add(_MIPP_ mr_mip->w1,mr_mip->modulus,mr_mip->w1);
subdiv(_MIPP_ mr_mip->w1,3,mr_mip->w1);
copy(mr_mip->w1,w);
MR_OUT
}
void nres_div5(_MIPD_ big x,big w)
{
#ifdef MR_OS_THREADS
miracl *mr_mip=get_mip();
#endif
MR_IN(208)
copy(x,mr_mip->w1);
while (remain(_MIPP_ mr_mip->w1,5)!=0)
add(_MIPP_ mr_mip->w1,mr_mip->modulus,mr_mip->w1);
subdiv(_MIPP_ mr_mip->w1,5,mr_mip->w1);
copy(mr_mip->w1,w);
MR_OUT
}
文章评论