密码学中的模乘算法——巴雷特模乘(Barrett Modular Multiplication)

密码学实践中常常需要处理 的模运算。模运算中当属模乘是最复杂的。蒙哥马利方法(Montgomery Modular Multiplication)是一种经典的快速模乘算法，感兴趣的小伙伴可以点击查看密码学中的模乘算法——蒙哥马利模乘（Montgomery Modular Multiplication）。这里介绍另外一种经典的快速模乘算法，称之为巴雷特方法（Barrett Modular Multiplication）[1]。

明确这里有待解决的问题，即求解 

这里 是一个浮点数。也就是说，如果我们能够以较高精度算得 , 那么求 是显然的。

考虑下面形式的逼近[2]，即寻找这样的整数 , 使得

因此有 。实践中通常取 且 。也就是说仅仅需要正常的乘法，加法和移位操作就可以完成模约减(modular reduction)运算，BarrettReduce算法大致可以描述如下：

上面的直觉有一个关键点没考虑。因为无论如何选取 ,,和目标 总是存在误差。由 可推出：

总之 。为了分析方便，这里要求选择相对大的 使得 。那么，上文中的BarrettReduce算法中的变量 满足：

所以算法的最终输出, 需要额外做一次判断将结果修正回来。

完整版的BarrettReduce算法描述如下：

正式叙述的写作思路部分参考[3]，它提供了Barrett算法的Python/Java代码实现。

在实际模约减中，常常遇到的情况是 , 不是 power-of-2 (因为模约减之前的运算是乘法，乘法的结果不会超过)。现在讨论这种情况下如何合理设置参数 和 。根据“直觉”章节的介绍，我们知道 的最小取值为 , 又因为 , 因此有理由选取：

"直觉"章节总结了 ，因此有理由选取：

综上所述，Barrett模约减算法总结如下：

1.选取, 。 

2.计算。 

3.计算。 

4.if : 

5.      。 

6.return 。

注意当模数固定时（绝大部分应用都是这种情形），算法的第1步只需要做一次即可。因此算法的主要运算是第2步的乘法和 第3步的乘法 。

从计算形式来看，Montgomery方法需要将输入的整数转成“蒙哥马利形式”，最后还需要将结果从蒙哥马利形式转回正常表达，因此Montgomery方法适用于大量,连续的模乘应用，比如RSA的模幂运算；Barrett方法则不需要这种复杂的形式转换，应用的范围更广。

从计算量来看，假定模数 有 bit，那么Barrett需要做一次 的乘法，一次 的乘法；Montgomery需要做两次 的乘法，计算复杂度更优些。

本文参考

[1]Barrett, Paul. "Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor." Advances in Cryptology—CRYPTO’86: Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000.

[2]https://en.wikipedia.org/wiki/Barrett_reduction

[3]https://www.nayuki.io/page/barrett-reduction-algorithm

本文作者：hujwei

知乎链接：https://zhuanlan.zhihu.com/p/621388087