Barrett reduction算法

- 日理万妓 2022-10-27 02:56 131阅读 0赞

转载自：[https://www.cnblogs.com/lxzbky/p/14178679.html][https_www.cnblogs.com_lxzbky_p_14178679.html]

### 1.模乘的两种优化 ###

1.蒙哥马利模乘算法

2.Barrett reduction算法

使用算法1需要满足条件,模数N和进制数R互质

当不符合此条件时,使用算法2

这次来记录下第二种算法,防止遗忘

### 2.先说一下流程 ###

b进制下,求 x mod m,默认大于0

m为k位数(b进制下),x位数小于等于2\*k

//b^n代表b的n次幂,mu=b^2k / m,可以预计算
    int BaRdc(x){
          q1 = x / b^(k-1);//右移k-1位,取整,后面同
          q2 = q1 * mu;
          q3 = q2 / b^(k+1);//移位
          r1 = x % b^(k+1);//取低k位,因为mod m,m是k位的,所以只需看低k位即可
          r2 = (q3 * m) % b^(k+1);//低k位
          r = r1 - r2;//低k位相减
          if ( r > m ) r -= m;
          return r;
    }

### 3.原理说明 ###

mu=\[b2km \]mu=\[b2km \]  
q1=\[xbk−1 \]q1=\[xbk−1 \]方括号代表取整  
q2=q1×muq2=q1×mu  
q3=\[q2bk+1 \]q3=\[q2bk+1 \]  
可以得到几个范围  
xbk−1−1<q1≤xbk−1xbk−1−1<q1≤xbk−1  
b2km−1<mu≤b2kmb2km−1<mu≤b2km 这两个应该很明显  
x×bk+1m−b2km−xbk−1+1<q2≤x×bk+1mx×bk+1m−b2km−xbk−1+1<q2≤x×bk+1m 两个范围相乘  
xm−bk−1m−xb2k+1bk+1<q3≤xmxm−bk−1m−xb2k+1bk+1<q3≤xm  
另外还有两个显然的条件  
bk−1m≤1,xb2k≤1bk−1m≤1,xb2k≤1  
m在b进制下为k位,x在b进制下不大于2k位  
所以进行下放缩,两项放缩一项舍去,xm−2<q3≤xmxm−2<q3≤xm  
设d=\[x/m\]d=\[x/m\]  
q3是整数,很容易观察到,d−1≤q3≤dd−1≤q3≤d  
q3应该大概率为d  
如果q3=d,xmodm=(x−q3m)modmxmodm=(x−q3m)modm  
q3=d-1时再减去一个m即可

[https_www.cnblogs.com_lxzbky_p_14178679.html]: https://www.cnblogs.com/lxzbky/p/14178679.html