广州天河酒店网站建设,专业画册设计公司,娱乐论坛网站建设方案范文,网站制作的基本流程背景介绍 约减算法#xff0c;通常应用在硬件领域#xff0c;因为模运算mod是一个除法运算#xff0c;在硬件中实现速度会比乘法慢的多#xff0c;并且还会占用大量资源#xff0c;因此需要想办法用乘法及其它简单运算来替代模运算。模约减算法可以利用乘法、加法和移位等…背景介绍 约减算法通常应用在硬件领域因为模运算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模约减成功将除法化简为了两个乘法和一两个加法计算。
