arXiv:2605.18415v1 [cs.DC] 18 May 2026
Residue Number System Comparison revisited, a software perspective ∗ Nadia El Mrabet Centre CMP, Department SAS Mines Saint-Etienne,CEA-LETI Saint-Etienne, France [email protected]
Laurent-Stéphane Didier Université de Toulon Toulon, France [email protected]
Jean-Marc Robert Université de Toulon Toulon, France [email protected]
Léa Glandus Université de Toulon Toulon, France [email protected]
May 11, 2025
Abstract 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 Opn2 q, which can be reduced to Oplogpnqq 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.
1
Introduction
This paper deals with comparison in Residue Number Systems (RNS), which is a costly operation that usually requires conversions to a positional system suitable to perform the comparison itself. RNS is a non-positional number system, that was described in 1959 by Garner [6], where operations such as additions, subtractions, and multiplications can be performed in parallel on independent residues (see Knuth [9]). A n-channel RNS base consists in a set of n relatively prime residues. The dynamic range of such systems is the product of the moduli. Such number systems mainly target signal processing and cryptographic applications (see Molahosseini et al. [14]). However, because of their non-positional nature, the comparison of two RNS numbers is costly. Furthermore, the division operation also remains costly, as it requires one to know the magnitude of both operands. ∗ This work has been partially funded by the AID, project 2022151.
1
Several contributions addressed the comparison problem. In general, comparing numbers in RNS requires a conversion to a positional system such as Mixed Radix System (MRS) or binary. After this conversion of each number, the comparison is done by comparing each pair of digits in the lexicographic order. Almost all previously published techniques either are based on Mixed Radix conversion either make use of the Chinese Remainder Theorem (CRT) or the Core function (see Ananda) [12]. The advantage of MRS conversion is that it involves computation on data that have the size of RNS moduli (see Szabo and Tanaka [21]). However, the computation of the MRS digits has a quadratic complexity in operation, though it can be implemented in a parallel to execute in linear time. The techniques based on the CRT formula require costly modular operations on large numbers having the magnitude of the RNS base. The use of specific bases can significantly reduce this cost in hardware implementations (see Zhang et al., Parhami, Wang et al. and Mohan. [13, 15, 22, 24]), but are not suitable for large RNS bases that are used in cryptographic applications. In the implementation of the RNS division, some adaptations of the CRT formula have been made in order to obtain the magnitude of the operands. For their division, Lu and Chiang presented in [10] a method based on parity checking, which uses lookup tables. Unfortunately, this method is not practicable for large RNS bases. Similarly, Sousa proposed a comparison scheme also based on parity checking which is simplified by the use of a specific RNS base [20]. Approximate techniques for computing the CRT have been proposed in division methods (see Posch et al. and Bajar et al. [3, 16]). However, because of the rounding, they are not adapted to catch the magnitude of small values. Kawamura et al. proposed a comparison method suitable for computing the final step of the modular multiplication of large RNS numbers [8]. Recently, a comparison method based on the approximate computing of the CRT formula has been published (see Xiao et al. [23]). However, similarly to the methods of [3, 16], it allows only the comparison of numbers that are large enough. An other way to compare numbers is to use mapping functions from the RNS to binary that are different from the CRT formula. The Core functions proposed by Akushkii et al. [1] are such mapping functions. However, they require modular computations on very large numbers and some numbers cannot be used for comparison (see Miller et al. [11]). Dimauro et al. developed a comparison scheme based on another mapping function called Diagonal function [4]. The modular computations make this approach not suitable for cryptographic-size RNS numbers. Contributions We target software implementations of cryptographic applications which require computations with large numbers of size ranging around several thousand bits. In such a context, the most frequent operation is the modular multiplication that requires to deal with two different RNS bases (see Bajard et al. [2]). In this paper, we revisit the comparison for large RNS numbers and present an approach which requires only one conversion instead of two in the classical methods of Szabo and Tanaka in [21]. This is possible when we already have the representation of both numbers in both bases, and one of the modulus of the second base can be used as a redundant modulus for comparison purpose. Thus, we assume that the redundant modulus is readily available. The comparison algorithm we propose works for all couple of numbers in the range of the RNS base, denoted M : @N1 , N2 such that 0 ď N1 , N2 ă M Our algorithm returns: True if N1 ě N2 or False if N1 ă N2 It requires a redundant modulus and uses a mixed radix extension to this modulus in order to provide the comparison. Furthermore, our approach is generic in the sense that there is no condition on the RNS 2
base: no special form of the moduli, no restrictions in the modulus number, no bounds on the input values N1 and N2 insofar as they remain in the RNS dynamic range (i.e. 0 ď N1 , N2 ă M ). We provide a theorem with the proof of correctness of our algorithm and finally, a complexity evaluation which shows the competitiveness of our approach in our context. We point out that our approach is designed to be, as far as possible, the most generalist one, and works whatever the size of the considered dynamic range of the RNS system. Organization of the paper This paper is organized as follows : Section 2 reminds the RNS system and details base extension approaches, Section 3 presents our comparison method and its complexity, and a conclusion ends the paper.
2
Residue Number Systems
In RNS, a number X is represented by its remainders xi “ |X|mi “ X mod mi . If the residues are śn relatively prime, the CRT proves that X is unique in [0, M[. We note M “ i“1 mi . The proof of this theorem gives a formula in order to compute X with the remainders xi : ˇ ˇ n ˇ ˇÿ ˇ ˇ ˇ ˇˇ ´1 ˇ (1) xi ˆ Mi mi ˆ Mi ˇ X“ˇ ˇ ˇi“1 M
ˇ ˇ where Mi “ M {mi and ˇMi´1 ˆ Mi ˇmi “ 1. The base of this Residue Number System is the set of the n relatively prime moduli B “ tm1 , ¨ ¨ ¨ , mn u. The main advantage of this number representation system is the parallel computations of additions, subtractions and multiplications on each channel independently. Considering X and Y , one computes in RNS Z Ð X d Y as follows: zi “ xi d yi mod mi where d P t`, ´, ˆu
However, the non-positional characteristic of the RNS representation renders rather difficult comparison, division or scaling operations. This motivates the numerous works around comparison algorithms, which is the subject of the present work.
2.1
Base extensions
The base extension consists in converting an RNS number from an RNS base to another. This operation requires to convert the RNS number into a positional representation and to compute the residues of this value in the new RNS base. There are mainly two families of base extension: • using a forward conversion to a Mixed Radix representation (MRC) and a backward computation of the value of this representation modulo each modulus of the destination base. • approaches based on the Chinese Remainders Theorem (CRT) formula. 2.1.1
Mixed Radix technique
This method was presented by Szabo and Tanaka in [21]. It consists in converting the RNS representation into a positional number system using the partial products of moduli as follows: X
“
a 1 ` a 2 ¨ m1 ` a 3 ¨ m1 ¨ m2 ` . . . `an´1 ¨ m1 ¨ . . . ¨ mn´2 `an ¨ m1 ¨ . . . ¨ mn´1 3
(2)
´1 We denote m´1 j,i the inverse of mj mod mi , that is mj ¨ mj,i ” 1 mod mi . The mixed-radix digits ai are computed as follows: $ a1 “ x1 mod m1 ’ ’ ’ ’ a2 “ px2 ´ a1 q ¨ m´1 ’ 1,2 mod m2 ’ ’ & a “ ppx ´ a q ¨ m´1 ´ a q ¨ m´1 mod m 3
.. ’ . ’ ’ ’ ’ ’ a ’ % n
3
“
1
1,3
2
3
2,3
´1 p¨ ¨ ¨ pxn ´ a1 q ¨ m´1 1,n ´ a2 q ¨ m2,n q ´ ¨ ¨ ¨ ´an´1 q ¨ m´1 n´1,n mod mn
The main advantage of this technique is that there is no need for large integer computations and that the value of X is obtained without correction to deal with the dynamic range of the RNS system. Another characteristic is that each digit is bounded, i.e. 0 ď ai ă mj . This guarantees that one has for sure 0 ď X ă M . In terms of complexity, this approach requires npn ´ 1q{2 word size multiplications and memorized constants. However, there are some parallelization techniques that allow Oplogpnqq execution time in some cases (see, for example, Huang in [7]). 2.1.2
CRT based approaches
This class of techniques retrieves X with the equation (1). The main drawback is that we need to compute X as a sum modulo M . This is very costly because M is a large number. ˇ ˇ řnoperation Thus, by denoting Y “ i“1 ˇxi ˆ Mi´1 ˇmi ˆ Mi , this is equivalent to find k such that X “Y ´k¨M
(3)
Different methods have been proposed to compute k: • Posch and Posch in [17] suggest performing a floating-point division of approximate values (˘1). Thus, this method can not be used when the exact value of k is needed. • Kawamura et al. in [8] propose another method also computing an approximate value of k, trading the division of the previous approach by shiftings and multiplications by small constants. Like the previous method, there is a bound on X beyond which the estimation of k is not correct, by 1. This bound depends on a special parameter α introduced by the authors (0 ď α ă 1), and can be expressed as p1 ´ αq ¨ M , and this parameter is set according to the base extension. On average, the authors suggest taking α “ 0.5, which is feasible in case of use in successive modular reduction, but not in case when the exact reduction modM is required. • Shenoy and Kumaresan in [18, 19] suggest using a redundant modulus mr in order to compute k as follows: ˇ˜ ˇ ¸ n ˇ ÿ ˇ ˇ ˇ k“ˇ ||xi ¨ yi |mi ¨ Mi |mr ´ xr ˇ ˇ i“1 ˇ
mr
provided mr is large enough.
One issue with this approach is that it is necessary to guarantee xr “ X mod mr in any case. Otherwise, one may meet a situation in which the evaluation of k is erroneous. Indeed, if we need to extend the difference of two numbers N1 and N2 modulo M , with 0 ď N1 , N2 ă M , and if N1 ă N2 , the base extension requires xr “ |M ` N1 ´ N2 |mr . Because we will use xr “ ||N1 |mr ´ |N2 |mr |mr ‰ |M ` N1 ´ N2 |mr , the estimation of k will not be correct. 4
3
Comparison Approach
In this section, we present our method for number comparison in RNS. To determine whether N1 ě N2 or N1 ă N2 , we will use an extra modulus that can be any value, large or small, provided that it is prime with M . We denote this modulus ma . One extra modulus has also been used by Lu et Chiang in [10] with ma “ 2. However, their design targets only hardware implementation and requires large look-up tables. Here, we propose a comparison algorithm designed for software implementation of large RNS bases. This targets cryptographic applications.
3.1
Algorithm
In the context of cryptography, each operand of, say, modular multiplications, is represented in two different RNS bases B and B 1 [2]. This extra modulus ma can be chosen as one of the moduli of the second base B 1 , provided that it is prime with each modulus of the first base B. This is convenient because, as we will show, our method will only need one single conversion. In other contexts, this extra modulus can be managed separately. This leads to the comparison Algorithm 1. It takes as inputs two integers N1 and N2 in their RNS p1q p1q p2q p2q representation, respectively tn1 , . . . , nn u and tn1 , . . . , nn u, and their residue modulo the redundant p1q p2q modulus, that is na “ N1 mod ma and na “ N2 mod ma . The algorithm returns either N1 ě N2 , or N1 ă N2 . Algorithm 1 uses a conversion to a Mixed Radix representation, whose choice will be justified section 3.2. The proof of this algorithm is provided by the Theorem 1. Algorithm 1 Comparison of two integers in RNS representation, RN SComppN1 , N2 q p1q
p1q
p2q
p2q
Require: tn1 , . . . , nn u and tn1 , . . . , nn u, the RNS representation in base B of respectively N1 and N2 , p1q p2q 0 ď N1 , N2 ă M , and their residues na “ N1 mod ma and na “ N2 mod ma Ensure: N1 ě N2 , or N1 ă N2 p1q p2q 1: ∆1 Ð |na ´ na |ma p1q p2q p1q p2q 2: tz1 , ¨ ¨ ¨ , zn u Ð t|n1 ´ n1 |m1 , . . . , |nn ´ nn |mn u // Mixed Radix conversion, Alg. 2 3: tδ1 , . . . , δn u Ð M RConversionptz1 , ¨ ¨ ¨ , zn uq // Residue mod ma , Alg. 3 4: ∆ Ð toma ptδ1 , . . . , δn uq// ∆ “ | |N1 ´ N2 |M |ma 5: if ∆ “ ∆1 then 6: return N1 ě N2 7: else 8: return N1 ă N2 9: end if Theorem 1 (Comparison). Let two RNS numbers N1 and N2 in the base B “ tm1 , ¨ ¨ ¨ , mn u and a modulus ma prime with B. If N1 ´ N2 mod ma “ ppN1 ´ N2 q mod M q mod ma , then N1 ě N2 , otherwise N1 ă N2 . Proof. In one hand, we compute ∆B Ð N1 ´ N2 in base B, i.e. ∆B “ pN1 ´ N2 q mod M . From this value, we compute ∆B mod ma . It can be computed as a small base extension of only 1 modulus ma . Thus: ∆ “ ppN1 ´ N2 q mod M q mod ma p1q
p2q
In the other hand, we use nma Ð N1 mod ma and nma Ð N2 mod ma , in order to obtain: p2q ∆1 Ð pnp1q ma ´ nma q mod ma
5
• If N1 ě N2 , then: ∆ “ “ “ “
ppN1 ´ N2 q mod M q mod ma pN1 ´ N2 q mod ma p1q p2q pnma ´ nma q mod ma 1 ∆
• Otherwise, if N1 ă N2 then N1 ´ N2 ă 0 and pN1 ´ N2 q mod M “ N1 ´ N2 ` M . Therefore, we have : ∆ “ “ “ ‰
ppN1 ´ N2 q mod M q mod ma pM ` N1 ´ N2 q mod ma p2q p1q ppM mod ma q ` nma ´ nma q mod ma 1 ∆
Reciprocally, if ∆ ‰ ∆1 , then: ppN1 ´ N2 q mod M q mod ma ‰ pN1 ´ N2 q mod ma and there exists an integer k ‰ 0 so that ppN1 ´ N2 q mod M q “ N1 ´ N2 ` k.M with k “ 1, because 0 ă pN1 ´ N2 q mod M ă M . Thus: 0 ă N1 ´ N2 ` M ă M and N1 ´ N2 ă 0 Therefore, N1 ă N2 , otherwise N1 ě N2 . Remark 1. Our method also works in the special cases where N1 ´ N2 ” 0 mod ma . p2q p1q Indeed, in this case, one has N1 mod ma ” N2 mod ma , i.e. nma “ nma and one has always p2q ∆1 Ð pnp1q ma ´ nma q mod ma “ 0
1. if N1 ě N2 , one has N1 ´ N2 “ k ˆ ma , with k a positive constant. Thus ∆ “ 0 “ ∆1 2. if N1 ă N2 , one has N1 ´ N2 “ ´k ˆ ma ” M ´ k ˆ ma mod M , with k a positive constant. Thus ∆ “ M mod ma ‰ ∆1 , since ∆1 “ 0.
3.2
Choice of base extension
Our comparison method works, provided we get the correct value mod ma . That is @X, 0 ď X ď M and tx1 , . . . , xn u the set of residues in the RNS base B “ tm1 , . . . , mn u, we need to compute xma “ X mod ma To achieve this, we use a base extension from the base B into the modulus ma .
6
Choice of the method and algorithm Taking into account what has been said in Section 2.1, and since it is mandatory to have the exact value modM (i.e. the exact value of k in the computation of N1 ´ N2 mod M , see equation 3), the chosen base extension method is based on the Mixed Radix conversion. We now present the generic algorithms for our comparison approach. Mixed Radix conversion We provide the Mixed Radix conversion method Algorithm 2, as presented by Szabo and Tanaka [21]. This algorithm provides the mixed radix representation of the number X from its residues in the RNS base B. Algorithm 2 Mixed Radix conversion, M RConversionptx1 , ¨ ¨ ¨ , xn uq Require: tx1 , . . . , xn u in RNS base B representing X, 0 ď X ă M , precomputed values m´1 j,i mod mi Ensure: ta1 , ¨ ¨ ¨ , an u as defined eq. 2 1: for i from 1 to n do 2: ai Ð xi 3: end for 4: for i from 2 to n do 5: for j from 1 to i ´ 1 do 6: ai Ð pai ´ aj q ¨ m´1 j,i mod mi 7: end for 8: end for 9: return ta1 , ¨ ¨ ¨ , an u The complexity of this approach is straightforward: one performs n ¨ pn ´ 1q{2 modular multiplications. In terms of memory, the need is n ¨ pn ´ 1q{2 word constants, corresponding to the values m´1 j,i mod mi . One may notice that the inner loop in algorithm 2 can be parallelized, leading to an execution time in Opnq. We do not present here other methods, though we already mentioned Huang in [7], whose approach runs in Oplogpnqq time, with the same complexity. Another method could be the one presented by Wang et al. in [22], with the same complexity properties. Conversion to the redundant modulus We now need to know the residue xma Ð X mod ma . This is Algorithm 3. In this algorithm, we precompute the following values, for i “ 2 to n : ˇ ˇ ˇ ˇ i´1 ˇź ˇ βi Ð ˇ mi ˇ ˇj“1 ˇ ma
Algorithm 3 From Mixed Radix to the residue modma , toma pta1 , ¨ ¨ ¨ , an uq Require: ta1 , . . . , an u the mixed radix representation of X, 0 ď X ă M , precomputed values βi Ensure: xma “ X mod ma 1: xma Ð a1 mod ma 2: for i from 2 to n do 3: xma Ð pxma ` ai ¨ βi q mod ma 4: end for 5: return xma
The instruction count is as follows: n word size modular multiplications and n ´ 1 word size modular additions. The memory cost is the storage of the pn ´ 1q βi constants, for 2 ď i ď n. Again, parallelization techniques allow an execution time in Oplogpnqq.
7
3.3
Complexity
We provide Table 1 the operation count and the time complexities, versus a sequential or parallel implementation. We compare our work with the the classic approach, requiring two mixed-radix conversions (see Flores [5]), which compares two numbers in the same conditions as ours: no special form base or moduli, no bounds on the numbers. while in this work it is pn`2qpn´1q . The memory cost is npn´1q 2 2 Op. Count This work Classic Appr. [5]
Time Comp. seq. par.
` nqM p n¨pn´1q 2 `2nA pn ¨ pn ´ 1qqM `nC
Opn2 q Oplogpnqq Opn2 q Oplogpnqq
Table 1: Complexity of the comparison algorithm, M = word size modular multiplication, A = word size addition, C = word size comparison A comparison with other approaches is non-trivial since either the proposed methods are specific for special form of RNS base or requiring conditions on the input data (bounds, etc.) Furthermore, previous works often present complexities in the background of hardware implementation, which is not our target.
4
Conclusion
In this work, we have proposed a method for number comparison in RNS, in the most generic context possible, requiring one redundant modulus which is often readily available in most contexts. In this method, the RNS base can be chosen arbitrarily, without conditions on the moduli form or moduli number. In addition, there are no requirements on the input numbers that can be taken in the whole RNS dynamic range. This method achieves the comparison with one single Mixed Radix conversion, with Opn2 q and can run in Oplogpnqq time, in case of parallel implementation, with Opn2 q word constant memorization. To the best of our knowledge, this is competitive in our context. Future Work We intend to extend this work to improve division and scaling algorithm in the context of software implementations taking advantage of SIMD instruction sets, for application in various use cases (homomorphic encryption, post-quantum schemes...). For all these approaches, software implementations will attempt to take advantage of the SIMD feature and optimization with various ranges of parameters, in particular moduli number and size.
References [1] I Ja Akushskii, VM Burcev, and IT Pak. A new positional characteristic of non-positional codes and its application. In Coding theory and the optimization of complex systems, pages 9–16. Nauka Alma-Ata, Kazakhstan, 1977. [2] J.-C Bajard, Laurent-Stéphane Didier, and Peter Kornerup. Modular multiplication and base extensions in residue numbersystems. In Proceedings 15th IEEE Symposium on Computer Arithmetic, pages 59–65, 02 2001. [3] Jean Claude Bajard, Laurent-Stéphane Didier, and Jean-Michel Muller. A new euclidean division algorithm for residue number systems. VLSI Signal Processing, 19:167–178, 07 1998.
8
[4] Giovanni Dimauro, Sebastiano Impedovo, and Giuseppe Pirlo. A new technique for fast number comparison in the residue number system. IEEE transactions on computers, 42(5):608–612, 1993. [5] Ivan Flores. Residue arithmetic and its application to computer technology (Nicholas S. Szabo and Richard I. Tanaka). SIAM Review, 11(1):103–104, 1969. [6] H. L. Garner. The residue number system. IRE Transactions on Electronic Computers, EL-8(6):140–147, June 1959. [7] Huang. A fully parallel mixed-radix conversion algorithm for residue number applications. IEEE Transactions on Computers, C-32(4):398–402, 1983. [8] Shinichi Kawamura, Masanobu Koike, Fumihiko Sano, and Atsushi Shimbo. Cox-rower architecture for fast parallel montgomery multiplication. In Bart Preneel, editor, Advances in Cryptology — EUROCRYPT 2000, pages 523–538, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg. [9] Donald E Knuth. The Art of Computer Programming: Seminumerical Algorithms, Volume 2. AddisonWesley Professional, 2014. [10] Mi Lu and Jen-Shiun Chiang. A novel division algorithm for the residue number system. IEEE Transactions on Computers, 41(8):1026–1032, 1992. [11] Dale D Miller, RE Altschul, JR King, and JN Polky. Analysis of the residue class core function of Akushskii, Burcev, and Pak, pages 390–401. IEEE Press, 1986. [12] P Ananda Mohan. Reverse conversion using core function, crt and mixed radix conversion. Circuits, Systems, and Signal Processing, 36, 07 2017. [13] PV Ananda Mohan. Residue number systems. Springer, 2016. [14] Amir Sabbagh Molahosseini, Leonel Seabra De Sousa, and Chip-Hong Chang. Embedded systems design with special arithmetic and number systems. Springer, 2017. [15] B. Parhami. Optimal table-lookup schemes for binary-to-residue and residue-to-binary conversions. In 27th Asilomar Conference on Signals, Systems and Computers, volume 1, pages 812–816, Pacific Grove, USA, 1993. IEEE Computer Society Press. [16] Karl Christian Posch and Reinhard Posch. Division in residue number systems involving length indicators. Journal of computational and applied mathematics, 66(1-2):411–419, 1996. [17] K.C. Posch and R. Posch. Modulo reduction in residue number systems. IEEE Transactions on Parallel and Distributed Systems, 6(5):449–454, 1995. [18] A.P. Shenoy and R. Kumaresan. Fast base extension using a redundant modulus in rns. IEEE Transactions on Computers, 38(2):292–297, 1989. [19] M.A.P. Shenoy and R. Kumaresan. A fast and accurate rns scaling technique for high speed signal processing. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(6):929–937, 1989. [20] Leonel Sousa. Efficient method for magnitude comparison in rns based on two pairs of conjugate moduli. In 18th IEEE Symposium on Computer Arithmetic (ARITH’07), pages 240–250. IEEE, 2007. [21] N. S. Szabo and R. I. Tanaka. Residue Arithmetic and its Applications to Computer Technology. McGraw-Hill, 1967. [22] Yuke Wang, Xiaoyu Song, and Mostapha Aboulhamid. A new algorithm for rns magnitude comparison based on new chinese remainder theorem ii. In Proceedings Ninth Great Lakes Symposium on VLSI, pages 362–365. IEEE, 1999. 9
[23] Hanshen Xiao, Yu Ye, Guoqiang Xiao, and Qin Kang. Algorithms for comparison in residue number systems. In 2016 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA), pages 1–6. IEEE, 2016. [24] C. N. Zhang, B. Shirazi, and D. Y. Y. Yun. An efficient algorithm and parallel implementations for binary and residue number systems. Journal of Symbolic Computation, 15(4):451–462, 1993.
10