Optimal Small-Bitwidth Moduli Set for Residue Number Systems

Danila Gorodecky (Gorodetsky) · 2026

Read Optimal Small-Bitwidth Moduli Set for Residue Number Systems by Danila Gorodecky (Gorodetsky) (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-24387.txt.

Introduction

Gorodecky offers a technical note on choosing moduli sets for residue number systems. The method generates sets of co-prime moduli inside a chosen integer range. The aim is to keep the bit lengths of the moduli balanced while making the dynamic range as large as possible. Tests show the generated sets reach optimal dynamic range with an even spread of bit lengths. Such sets suit parallel hardware designs built on residue arithmetic.

Catalog record

CREATORDanila Gorodecky (Gorodetsky)
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18633
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.24387

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimal Small-Bitwidth Moduli Set for Residue Number Systems Danila Gorodecky (Gorodetsky) Abstract This technical note presents a algorithmic approach for generating optimal sets of co-prime moduli within specified integer ranges. The proposed method addresses the challenge of balancing moduli bit-lengths while maximizing the dynamic range in Residue Number System (RNS) implementations. Experimental results demonstrate that the generated moduli sets achieve optimal dynamic range coverage while maintaining balanced bit-length distribution, making them particularly suitable for parallel hardware implementations based on RNS. 1 Introduction The Chinese Reminder Theorem (CRT) [ 1 ] states that there is a one-to-one correspondence between a set of residues S_{1},S_{2},...,S_{n} and an integer number in the range from 0 to p_{1}\cdot p_{2}\cdot...\cdot p_{n}-1=P-1 , where \{p_{i}|_{1\leq i\leq n}\} is the moduli set of co-prime numbers for which the \{S_{i}|_{1\leq i\leq n}\} have been calculated. Since the value of the represented number is invariant under any permutation of the residues, RNS is a non-positional number system. In comparison to positional number systems, RNS alternative number system has pros and cons. If from one side RNS allows parallelizing computations and hence speeds them up, on the other side it does not allow for directly comparing the magnitude of two numbers represented by their residues.RNS exhibits data parallelism, computer arithmetic is performed independently on each residue, constituting what is called a channel. Since the residues have a lower number of digits than the original binary representation, and arithmetic operations over the residues are performed separately for each modulus of the set, it results in faster computation. RNS is suitable for arithmetic operations such as addition, subtraction, and multiplication, with an arbitrary number of operands. Data processing in RNS typically includes the following steps. If the input operands A_{1},A_{2},\dots,A_{n} are represented in binary, they have to be converted to modular representations RNS by computing the remainders (or residues) with respect to the moduli \{p_{1},p_{2},\dots,p_{n}\} ; then arithmetic operations are applied to the residues for each modulo p_{i} ; finally, the results S_{1},S_{2},...,S_{n} might have to be converted back from residues to the binary representation S , as depicted in Fig. 1 . Figure 1: Schematic representation of RNS, where \circ\in\{+,-,\times\} . In Fig. 1 block (1) operands are converted into X(mod\ P) ; in block (2) modular summation, multiplication, and combinations of these operators, such as A\cdot B+C are performed; in block (3) the polynomial form S_{1}\cdot C_{1}+S_{2}\cdot C_{2}+\cdots+S_{n}\cdot C_{n}-P\cdot k is computed, where S_{1},\cdots S_{n} are outputs of the previous block, C_{1},\cdots,C_{n} are pre-calculated constants, k is a constant which is obtained during the computation of the polynomial and P=p_{1}\cdot p_{2}\cdot...\cdot p_{m} . Therefore, the main arithmetic operations needed for RNS computations are the modulo function X(mod\ P) , modular summation, and modular multiplication. For converting the representation of S from RNS to binary, the CRT and the Mixed Radix Conversion (MRC) [ 2 , 3 ] can be applied: \begin{split}S=&(S_{1}\cdot C_{1}+S_{2}\cdot C_{2}+...+S_{n}\cdot C_{n})\>mod\>P\\ =&S_{1}\cdot C_{1}+S_{2}\cdot C_{2}+...+S_{n}\cdot C_{n}-k\cdot P,\end{split} (1) where k is a natural number and C_{i}=\frac{P}{p_{i}}\cdot q_{i} , with q_{i}\cdot\frac{P}{p_{i}}(mod\>p_{i})=1 , for i=1,2,...,n . Some drawbacks prevent using RNS for general-purpose computing. For example, it is hard to compute division and comparison in the RNS domain, and binary-RNS forward and backward conversions are overheads in cost and performance. The backward conversion consists of multipliers and adders, according to ( 1 ), and either the reduction modulo P is computed or a comparison with the value k\cdot P is performed several times in order to find k . In practice, these problems associated with RNS have been mitigated by adopting small sets of special moduli, which limits the applicability of RNS. Special moduli define specific forms, such as Mersenne primes ( 2^{k}-1 ), Fermat numbers ( 2^{2^{k}}+1 ), Cullen numbers ( n\cdot 2^{k}+1 ), Sophie Germain primes k , for 2\cdot k+1 prime, and other variations of ”power of two” numbers [ 2 , 4 , 5 , 6 , 7 ] . Special features of these types of moduli simplify the reduction to calculate the residues. But it is not known any efficient common approach to calculating the residue for an arbitrary divider. Flexibility is improved by allowing arbitrary modulo sets, which may reduce significantly the bit-width of the residues in comparison to special moduli approaches. For instance, considering multiplication for 50-bit range in RNS, for a special moduli set may require 17-bit ( 2^{17}-1,2^{17},2^{17}+1 ) or 6-bit for an arbitrary moduli set ( \{37,39,41,43,47,49,55,59,61\} ). A slower multiplication of 17-bit for the first case is replaced by a faster 6-bit for the second. On the other hand, the difficulty of calculating the residues for arbitrary moduli sets may overshadow the advantages of multiplication. RNS deals with special values of moduli due also to the complexity of reverse conversion and reduction for arbitrary modulo values. Despite extensive research in RNS architectures, as comprehensively surveyed by Mohan [ 4 ] , the optimization of small moduli sets for balanced hardware implementation remains an underexplored area. Previous investigations by Bajard et al. [ 8 , 9 , 10 , 11 ] have primarily focused on identifying co-primes within predefined number sets, discovering moduli with limited Hamming weight, and developing sets with specific cryptographic properties. However, the systematic generation of moduli sets that simultaneously maximize dynamic range and minimize bit-width variance has not been adequately addressed. The alternative paradigm, which forms the foundation of this work work, utilizes a large number of small moduli. This approach offers superior flexibility in system configuration and enables more balanced parallel processing. However, it introduces the challenge of reverse conversion, i.e. transforming residues back to binary representation requires handling intermediate values on the order of P . Recent studies have demonstrated that specialized hardware algorithms enable modular arithmetic implementations on FPGA [ 12 ] and ASIC [ 13 , 14 ] platforms that achieve up to 30-fold efficiency improvements over conventional EDA-synthesized designs for small-bitwidth moduli (up to 12 bits). This promising result motivates the search for co-prime moduli sets that can provide large dynamic ranges of hundreds or even thousands of bits while utilizing only small-bitwidth moduli. Such an approach would allow RNS to be considered not merely as a computational framework for a limited class of cryptographic applications, but as a viable alternative to conventional positional arithmetic for a broader range of computational tasks. This work introduces the tool based on a deterministic algorithm for generating optimal co-prime moduli sets within user-specified ranges [ 15 ] , subject to the following design objectives: 1. maximization of the achievable dynamic range P=\prod_{i=1}^{n}p_{i} ; 2. minimization of moduli bit-width variance to facilitate balanced parallel processing and preferential allocation of moduli at the maximum feasible bit-length within the specified range, i.e. the range under consideration must contain as many modules as possible with the highest bit depth from the given range and the greatest number of modules must be of the same bit depth; 3. mandatory inclusion of a power-of-two modulus to simplify certain RNS operations, i.e. a number of 2^{n} should be within the input range. While MATLAB’s numerical limitations affect dynamic range exceed 1000 bits, the generated moduli sets remain valid and can be verified using alternative tools. 2 Algorithmic Framework Given a range

Read the complete text