An improvement of the Barrett modular reduction algorithm
Zhengjun Cao, Xiangjia Wu · International Journal of Computer Mathematics · 2013
The popular Barrett modular reduction algorithm requires a suitably chosen base b≥3. In this paper, we show that the setting will cause the problem of data expansion and require more cost for performing the unique multiplication which dominates the cost of this algorithm. We shall prove that the base b can be replaced by the usual base 2. The improvement gives a little of cost saving. Besides, it is more portable and more suitable for small devices such as smartphones.