An improvement of the Barrett modular reduction algorithm

Abstract

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.

Keywords:

• modular reduction
• Barrett reduction algorithm
• data expansion

2010 AMS Subject Classification:

• 68Q25

Acknowledgements

We thank the anonymous referee for his/her insightful suggestions to revise the paper, and the kindness of referring the latest dissertation [2] to us. This work is supported by the National Natural Science Foundation of China (Project 61303200), the Shanghai Leading Academic Discipline Project (S30104), and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.