Efficient Two-level RNS Reverse Conversion Algorithm for Big Number of Modules
Elizaveta Martirosyan, Roman Kurmaev, Valeria Ryabchikova, Vitaly Slobodskoy · 2022 International Conference on Quality Management, Transport and Information Security, Information Technologies (IT&QM&IS) · 2022
Residue Number System (RNS) has a big potential for the hardware accelerators due to its high area and performance efficiency for arithmetic computations based on multiplications and additions only. The choice of moduli set has a significant impact on the RNS efficiency. In general case, using arbitrary modulo, an increase in the number of moduli leads to the corresponding decrease of the average modulo size achieving less hardware area and power consumption, but this usually makes conversion algorithms less efficient. This article presents a two-level method for reverse conversion of a number in RNS to a Binary Number System (BNS) based on a combination of Core-function based methods and Mixed Radix Conversion (MRC) based methods for three-moduli set 2n, 2n+ 1, 2n– 1. We demonstrated how to choose modulo properly in order to achieve up to 64% of hardware area reduction, up to 97% of power consumption reduction and become up to 53% faster than traditional CRT-based methods.