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模约减，成功将除法化简为了两个乘法和一（两）个加法计算。