Residue Number System Comparison revisited, a software perspective
This work addresses the long-standing problem of efficient RNS comparison for general moduli sets, which is crucial for RNS-based cryptographic and signal processing applications.
The paper introduces a novel method for comparing two numbers in Residue Number System (RNS) using an additional modulus, achieving full-range comparison without restrictions on moduli form. The method requires only one mixed radix conversion with O(n^2) complexity, reducible to O(log n) with parallelization.
This paper presents a novel method to compare two numbers in Residue Number System (RNS) using an additional modulus, which is often already available because it is required in modular computations and digital signal processing scaling.Our method provides the comparison of two integers in the full range of the RNS base. It does not require moduli of a special form, unlike other state-of-the-art methods that are restricted to specific RNS bases or require bounds on input numbers. Our approach only requires one single conversion to a mixed radix representation with a complexity of O(n2), which can be reduced to O(log(n)) in time with parallelization. This provides a significant advantage over classical methods and more recent competitive methods which work under restrictions. This opens perspectives for advancements in challenging RNS operations such as division, scaling, and cryptographic applications.