pith. sign in

arxiv: 2605.18415 · v1 · pith:5SCIFHDGnew · submitted 2026-05-18 · 💻 cs.DC

Residue Number System Comparison revisited, a software perspective

Laurent-St\'ephane Didier (UTLN) , L\'ea Glandus (UTLN) , Nadia El Mrabet , Jean-Marc Robert (UTLN) This is my paper

Pith reviewed 2026-05-19 23:39 UTC · model grok-4.3

classification 💻 cs.DC
keywords residue number systemRNS comparisonmixed radix conversionmodular arithmeticfull range comparisondigital signal processing
0
0 comments X

The pith

A Residue Number System comparison method works over the full dynamic range using one mixed-radix conversion and an extra modulus.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a technique for comparing two integers represented in Residue Number System. It relies on an additional modulus that is often already present in applications like modular computations. The method converts the residues once to a mixed radix form to determine which number is larger. This works for any pair within the complete range of the RNS base without requiring the moduli to have a special form or restricting the size of the inputs. The computational cost is quadratic in the number of moduli but drops to logarithmic time when the conversion steps run in parallel.

Core claim

The authors present a method to compare two RNS integers over their entire dynamic range by performing a single conversion to mixed radix representation with the help of one extra modulus. This approach imposes no special conditions on the moduli set and avoids bounds on the input values, while delivering O(n squared) sequential complexity that parallelizes to O(log n).

What carries the argument

Single conversion to mixed radix representation using one additional modulus to establish ordering.

If this is right

  • Comparison becomes possible for arbitrary RNS bases without special modulus forms.
  • The method supports direct use in full-range arithmetic operations such as division and scaling.
  • Parallel execution reduces the comparison time to O(log n).
  • Cryptographic and signal-processing applications gain a less restricted RNS comparison primitive.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Existing RNS code bases that already maintain an extra modulus for other reasons could adopt the comparison with little added infrastructure.
  • The technique might reduce the number of special-case checks currently needed in software RNS libraries.
  • Extending the same single-conversion idea to other difficult RNS operations such as exact division could be explored next.

Load-bearing premise

The extra modulus fits the RNS base without conflict and the mixed-radix conversion step always produces the correct ordering for every pair of numbers in the full range.

What would settle it

Any pair of numbers inside the RNS dynamic range whose order is reported incorrectly after the mixed-radix conversion would disprove the method.

read the original 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 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes a method for comparing two numbers represented in a Residue Number System (RNS) by using an additional modulus (often already present in applications) and performing a single conversion of one number to mixed-radix form. The central claim is that this yields a correct ordering for any pair in the full dynamic range [0, M-1] where M is the product of the n moduli, without requiring special moduli forms or input bounds, at O(n²) sequential or O(log n) parallel complexity.

Significance. If the central claim holds with a correct full-range guarantee, the result would be useful for RNS-based implementations in digital signal processing, modular arithmetic, and cryptography, where comparison is a recurring bottleneck. The approach avoids the restrictions of prior methods and leverages an extra modulus that is frequently available anyway.

major comments (2)
  1. [Abstract and §3 (algorithm description)] The manuscript provides no derivation, proof sketch, or error analysis showing that the single mixed-radix conversion step unambiguously determines the sign of X-Y for arbitrary X, Y in the full range. In particular, it is unclear how the algorithm handles the case when X and Y straddle M/2 or differ by 1 near a power-of-two boundary; the skeptic concern about truncation or missing borrow propagation therefore remains unaddressed.
  2. [§4 (experimental results) and §5 (complexity analysis)] No numerical examples, corner-case tests, or comparison against the dynamic-range limits of existing methods are supplied. Without such verification, the claim that the method works for the full range (unlike methods that impose bounds) cannot be evaluated.
minor comments (2)
  1. [§5] The complexity statement O(n²) for the mixed-radix conversion should be accompanied by a precise operation count (additions, multiplications, or modular reductions) rather than a high-level big-O.
  2. [§2 (RNS background)] The paper should clarify whether the extra modulus is assumed coprime to all existing moduli or whether the method tolerates a non-coprime choice.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address the major comments point by point below and will revise the paper to strengthen the presentation of the proof and experimental validation.

read point-by-point responses

  1. Referee: The manuscript provides no derivation, proof sketch, or error analysis showing that the single mixed-radix conversion step unambiguously determines the sign of X-Y for arbitrary X, Y in the full range. In particular, it is unclear how the algorithm handles the case when X and Y straddle M/2 or differ by 1 near a power-of-two boundary; the skeptic concern about truncation or missing borrow propagation therefore remains unaddressed.

    Authors: We acknowledge that the current manuscript does not include a formal derivation or proof sketch. In the revised version we will add this material to Section 3. The approach relies on an additional modulus (commonly available in target applications) to perform a single mixed-radix conversion that resolves the sign of X-Y over the complete interval [0, M-1]. The extra modulus supplies the information needed to detect borrow propagation correctly, thereby eliminating truncation ambiguities at boundaries. We will explicitly analyze the cases in which X and Y straddle M/2 or differ by one near a power-of-two boundary, showing that the resulting mixed-radix digits yield the correct ordering without requiring special moduli or input restrictions. revision: yes

  2. Referee: No numerical examples, corner-case tests, or comparison against the dynamic-range limits of existing methods are supplied. Without such verification, the claim that the method works for the full range (unlike methods that impose bounds) cannot be evaluated.

    Authors: We agree that concrete verification is necessary to substantiate the full-range claim. The revised manuscript will augment Section 4 with numerical examples and targeted corner-case tests, including pairs that differ by one near power-of-two boundaries and pairs that straddle M/2. We will also insert direct comparisons with representative prior methods, illustrating that our technique achieves the complete dynamic range without the input bounds or special moduli forms required by those approaches. revision: yes

Circularity Check

0 steps flagged

No circularity: direct algorithmic construction from standard RNS definitions

full rationale

The paper presents an explicit algorithmic procedure for RNS comparison that invokes one mixed-radix conversion step using an additional modulus. No equations reduce a claimed result to a fitted parameter or to a self-referential definition of the same quantity. No load-bearing uniqueness theorem is imported from prior work by the same authors, and no ansatz is smuggled via citation. The derivation chain consists of standard residue-to-mixed-radix conversion steps whose correctness is independent of the target comparison result and can be checked against the definition of the RNS dynamic range.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The method rests on standard properties of Residue Number Systems and the assumption that an extra modulus is available; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption RNS comparison can be performed via conversion to mixed radix representation using an additional modulus
    Invoked as the core of the proposed method in the abstract.

pith-pipeline@v0.9.0 · 5686 in / 1183 out tokens · 38876 ms · 2026-05-19T23:39:39.560572+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    A new positional characte ristic of non-positional codes and its application

    I Ja Akushskii, VM Burcev, and IT Pak. A new positional characte ristic of non-positional codes and its application. In Coding theory and the optimization of complex systems , pages 9–16. Nauka Alma-Ata, Kazakhstan, 1977

    work page 1977

  2. [2]

    Modular multiplication and base extensions in residue numbersystems

    J.-C Bajard, Laurent-St´ ephane 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

    work page 2001

  3. [3]

    A new euclidean division algorithm for residue number systems

    Jean Claude Bajard, Laurent-St´ ephane Didier, and Jean-Mich el Muller. A new euclidean division algorithm for residue number systems. VLSI Signal Processing , 19:167–178, 07 1998. 8

    work page 1998

  4. [4]

    A ne w technique for fast number com- parison in the residue number system

    Giovanni Dimauro, Sebastiano Impedovo, and Giuseppe Pirlo. A ne w technique for fast number com- parison in the residue number system. IEEE transactions on computers , 42(5):608–612, 1993

    work page 1993

  5. [5]

    Residue arithmetic and its application to computer te chnology (Nicholas S

    Ivan Flores. Residue arithmetic and its application to computer te chnology (Nicholas S. Szabo and Richard I. Tanaka). SIAM Review , 11(1):103–104, 1969

    work page 1969

  6. [6]

    H. L. Garner. The residue number system. IRE Transactions on Electronic Computers, EL-8(6):140–147, June 1959

    work page 1959

  7. [7]

    A fully parallel mixed-radix conversion algorithm for residu e number applications

    Huang. A fully parallel mixed-radix conversion algorithm for residu e number applications. IEEE Transactions on Computers , C-32(4):398–402, 1983

    work page 1983

  8. [8]

    Cox-rower architecture for fast parallel montgomery multiplication

    Shinichi Kawamura, Masanobu Koike, Fumihiko Sano, and Atsushi Shimbo. Cox-rower architecture for fast parallel montgomery multiplication. In Bart Preneel, editor, Advances in Cryptology — EURO- CRYPT 2000, pages 523–538, Berlin, Heidelberg, 2000. Springer Berlin Heidelber g

    work page 2000

  9. [9]

    The Art of Computer Programming: Seminumerical Algorithms , Volume 2

    Donald E Knuth. The Art of Computer Programming: Seminumerical Algorithms , Volume 2 . Addison- Wesley Professional, 2014

    work page 2014

  10. [10]

    A novel division algorithm for the res idue number system

    Mi Lu and Jen-Shiun Chiang. A novel division algorithm for the res idue number system. IEEE Trans- actions on Computers , 41(8):1026–1032, 1992

    work page 1992

  11. [11]

    Analysis of the residue class core function of Akushskii, Burcev, and Pak , pages 390–401

    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

    work page 1986

  12. [12]

    Reverse conversion using core function, crt and mixed radix conversion

    P Ananda Mohan. Reverse conversion using core function, crt and mixed radix conversion. Circuits, Systems, and Signal Processing , 36, 07 2017

    work page 2017

  13. [13]

    Residue number systems

    PV Ananda Mohan. Residue number systems . Springer, 2016

    work page 2016

  14. [14]

    Embedded systems design with special arithmetic and number systems

    Amir Sabbagh Molahosseini, Leonel Seabra De Sousa, and Chip-H ong Chang. Embedded systems design with special arithmetic and number systems . Springer, 2017

    work page 2017

  15. [15]

    B. Parhami. Optimal table-lookup schemes for binary-to-resid ue 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

    work page 1993

  16. [16]

    Division in residue numb er systems involving length indica- tors

    Karl Christian Posch and Reinhard Posch. Division in residue numb er systems involving length indica- tors. Journal of computational and applied mathematics , 66(1-2):411–419, 1996

    work page 1996

  17. [17]

    Posch and R

    K.C. Posch and R. Posch. Modulo reduction in residue number sys tems. IEEE Transactions on Parallel and Distributed Systems , 6(5):449–454, 1995

    work page 1995

  18. [18]

    Shenoy and R

    A.P. Shenoy and R. Kumaresan. Fast base extension using a red undant modulus in rns. IEEE Trans- actions on Computers , 38(2):292–297, 1989

    work page 1989

  19. [19]

    Shenoy and R

    M.A.P. Shenoy and R. Kumaresan. A fast and accurate rns scalin g technique for high speed signal processing. IEEE Transactions on Acoustics, Speech, and Signal Process ing, 37(6):929–937, 1989

    work page 1989

  20. [20]

    Efficient method for magnitude comparison in rns based on two pairs of conjugate moduli

    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

    work page 2007

  21. [21]

    N. S. Szabo and R. I. Tanaka. Residue Arithmetic and its Applications to Computer Techno logy. McGraw-Hill, 1967

    work page 1967

  22. [22]

    A new algorit hm for rns magnitude comparison based on new chinese remainder theorem ii

    Yuke Wang, Xiaoyu Song, and Mostapha Aboulhamid. A new algorit hm 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

    work page 1999

  23. [23]

    Algorithms for comparison in residue number systems

    Hanshen Xiao, Yu Ye, Guoqiang Xiao, and Qin Kang. Algorithms for comparison in residue number systems. In 2016 Asia-Pacific Signal and Information Processing Associ ation Annual Summit and Conference (APSIPA), pages 1–6. IEEE, 2016

    work page 2016

  24. [24]

    C. N. Zhang, B. Shirazi, and D. Y. Y. Yun. An efficient algorithm an d parallel implementations for binary and residue number systems. Journal of Symbolic Computation , 15(4):451–462, 1993. 10

    work page 1993