barret reduction原理详解及硬件优化
背景介绍
约减算法,通常应用在硬件领域,因为模运算mod是一个除法运算,在硬件中实现速度会比乘法慢的多,并且还会占用大量资源,因此需要想办法用乘法及其它简单运算来替代模运算。模约减算法可以利用乘法、加法和移位等操作实现大数的取模,规避了模运算中的除法,常见方法有蒙哥马利模约减,barret模约减等,本篇文章介绍barret 模约减算法原理。
barret reduction
约减就是用简单运算来规避除法运算,以便于硬件实现,以A mod q为例,如果要计算A对q取模的结果使用barret reduction算法应该怎么做?
先规定A mod q,则称A为模数,q为基。
假设A的位宽是,q的位宽是,对于硬件实现来说需要预计算出两个常数:
和在进行预计算的时候,都需要对计算结果进行取下整,进而和满足如下不等式:
令,则有如下不等式成立:
令,即对上面不等式,两边同时除以,得到:
由于A的位宽是,q的位宽是,所以A和q满足如下不等式:
把A和q所满足的不等式,带入不等式中,得到:
所以两边同时乘以q得到:
因此得到模运算可以化简为:
又由于是在A-3q和A之间的,所以它对q取模,只需要判断它在[0,q)、[q,2q)、[2q,3q)的哪个区间,若落在[q,2q)区间,则:
以上,完成了barret模约减,同样的,该模约减算法可以应用在模乘领域,即实现barret模乘。而相对于模乘,AB mod q,可以直接把AB的乘积看作是上面公式推导的A,然后再进行模乘。
barret模约减计算流程大体如下图所示:
硬件实现
看完模约减公式推导过程,肯定有人会疑问:
先前预计算了两个常数,我后面的约减推导全都是依赖于这两个常数。先来看H,为了将多项式系数约束在基的范围内,进而能够实现密码学领域中的一些同态加密算法,选取的基q,通常是定值,因此H的计算量很少可以直接预计算并存储到RAM中,哪怕我A的取值范围是1-200bit,在基q确定的情况下我最多也只需要预计算200个H的值。
选取基q确定的情况下H好计算,但A是输入变量,有任意种可能,那么该怎么预计算?
事实上不需要预计算,因为是A除以2的幂次,在硬件中,除以2的幂次可以通过移位操作来实现,至于计算需要对结果向下取整,只需要对A进行移位操作即可。例如
计算对结果向下取整,可以直接用A移位来替代。
综上,的值和的值我们都可以轻易得到了,并且不怎么消耗计算资源,也没有多少计算delay,并且后面的计算也是除以2的次幂,也可以转化为移位操作,因此barret模约减主要的计算量在于:
主要计算量在于上面的两个乘法,q2 = q1*H,和q3*q的计算。
硬件优化
在之前已经推导出barret模约减主要计算量在两个乘法,q2 = q1*H,和q3*q的计算。
对于硬件实现来说,第二个计算可以进行优化,因为A-q3*q之后还要对其的范围进行判断,若落在[q,2q)范围,则A mod q = A-q3*q-q,事实上我们关心其落在那个范围,并不需要比较所有bit位,q的位宽为,我们只需要比较低位的大小就可以判断其落在哪个范围,甚至对于q3*q也可以通过取q3的低位的数据和q进行乘运算,再取运算结果的低位进行比较,从而确定范围。
因此在硬件实现上,利用barret模约减,成功将除法化简为了两个乘法和一(两)个加法计算。
相关文章
- Redis 底层原理
- java actioncontext_关于struts2中ActionContext的实现原理
- socketpair原理_socket负载均衡
- mybatis的逻辑分页和物理分页_mybatis分页原理
- 【Android 属性动画】属性动画 Property Animation 工作原理 ( 线性插值动画 | 非线性插值动画 | 动画计算 | 经过分数 | 插值分数 | 类型估值器)
- 【Java 虚拟机原理】垃圾收集器 ( Serial | ParNew | Parallel Scavenge | CMS | Serial Old - MSC | Parallel Old )
- Go-Channel的使用和底层原理(上)
- Linux编译与加载:解读运行原理(linux编译与加载)
- Linux网络实战:探究网络原理(linux网络原理)
- 浅谈拒绝服务攻击的原理与防御(4):新型DDOS攻击 – Websocket和临时透镜
- 深入探究Linux VFS机制,深入理解文件系统的实现原理(linuxvfs机制)
- Linux LVM原理及其应用分析(linuxlvm原理)
- javaScript中的this示例学习详解及工作原理