The Residue Number System: A Non-Comprehensive Review

Ahmad Al Badawi

The residue number system (RNS), also called the residue system or the remainder system, is a fundamental concept in mathematics that has numerous applications in various fields, including computer science, coding theory, and cryptography. Our primary focus here is on cryptography, specifically lattice-based, Ring Learning with Errors (RLWE)-based homomorphic encryption (HE) schemes, such as BGV (Brakerski, Gentry & Vaikuntanathan, 2014), B/FV, usually written BFV (Brakerski, 2012; Fan & Vercauteren, 2012), and CKKS (Cheon et al., 2017). In this domain, RNS plays a crucial role in enabling efficient implementations of HE schemes. To the best of my knowledge, nearly all leading (and performant) HE libraries, including OpenFHE, Microsoft SEAL, HElib, and Lattigo, employ RNS to enhance computational efficiency.

This article highlights the efficiency of RNS for handling large integer computations. We will explore the fundamental principles of RNS and illustrate its practical application through step-by-step examples of basic arithmetic operations. By the end, you will gain a clear understanding of how RNS can significantly accelerate computations involving large integers, and of the one thing RNS makes hard: knowing how large a number actually is.

Every worked example below is runnable: the RNS Calculator reproduces all fourteen examples and lets you change the numbers.

As the title suggests, this overview provides a brief introduction to RNS. For a comprehensive treatment, I recommend the following two books, which offer in-depth coverage of RNS concepts, theory, implementation, and applications, and one survey that covers the FHE-specific story:

1. A. R. Omondi and A. B. Premkumar, Residue Number Systems: Theory and Implementation, Imperial College Press, 2007 (Omondi & Premkumar, 2007).
2. P. V. Ananda Mohan, Residue Number Systems: Theory and Applications, Birkhäuser, 2016 (Ananda Mohan, 2016).
3. A. Al Badawi et al., Efficient Large-Integer Arithmetic for FHE, 2026 (Al Badawi et al., 2026). My co-authors and I trace how the RNS techniques sketched here evolved into the backends of today’s FHE libraries.

Note on terminology. Due to the strong connection between RNS and the Chinese Remainder Theorem (CRT), the terms are often used interchangeably in the literature.

Disclaimer: This article is written for readers interested in efficiently implementing HE schemes, and potentially other cryptographic schemes or applications that require multi-precision integer arithmetic. It assumes basic familiarity with modular arithmetic, and it provides the foundational concepts essential for optimizing RNS implementations of HE schemes.

Contents

• The History of the Chinese Remainder Theorem
• The HE Challenge RNS Can Address
• The Intuition behind RNS
• Integer Arithmetic with RNS
  • Integer Remainder Theorem
  • RNS Base
  • RNS Dynamic Range
  • RNS Representation of Integers
  • Addition and Subtraction in RNS
  • Multiplication in RNS
  • The Magnitude Problem
  • Division in RNS
• RNS Reconstruction Map
  • CRT-Based RNS Reconstruction Map
• RNS Base Extension
• Approximate RNS Base Extension
• Floating-Point Base Extension
• Try It
• Key Takeaways
• References & Further Reading
• Suggested Citation

The History of the Chinese Remainder Theorem

The Chinese Remainder Theorem stands as one of mathematics’ most elegant and practical discoveries, with roots stretching back through millennia of human history. While its exact origins remain debated among historians, it seems that this fundamental mathematical principle has evolved from an ancient puzzle-solving technique to a cornerstone of modern computing and cryptography.

The earliest known written record of what we now call the Chinese Remainder Theorem appears in the Sunzi Suanjing (The Mathematical Classic of Master Sun), written around the 3rd to 5th century AD. The text presents a fascinating problem, shown below.

“There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?”

Sunzi, Sunzi Suanjing

Sunzi’s seemingly simple puzzle encapsulates the essence of the CRT: finding a number based on its remainders when divided by different values. (The smallest answer is 23, as you can verify: \(23 = 7 \cdot 3 + 2 = 4 \cdot 5 + 3 = 3 \cdot 7 + 2\).)

Solve Sunzi’s puzzle in the calculator

The theorem’s development did not stop with Sunzi, as various mathematical traditions made significant contributions throughout history (Wikipedia: CRT, History). In India, Aryabhata described an algorithm for such remainder problems in the 6th century. Back in China, Qin Jiushao gave the first complete general solution, the Dayan rule, in his Shushu Jiuzhang (Mathematical Treatise in Nine Sections, 1247). The problem also entered popular culture: it is known in China as Han Xin dian bing (“Han Xin counts the soldiers”), after a legend in which the Han-dynasty general counted his troops by their remainders, and Cheng Dawei’s Suanfa Tongzong (1592) recorded the solution as a verse (multiply the remainders by 70, 21, and 15, add, and adjust by multiples of 105) that is still taught today (Wikipedia: Cheng Dawei). In Europe, special cases appear in Fibonacci’s Liber Abaci (1202), and Carl Friedrich Gauss gave the theorem its modern formulation, in the language of congruences, in his Disquisitiones Arithmeticae (1801).

Today, the CRT remains a vital tool in various fields, including cryptography, computer science, and digital systems. It serves as a testament to the ingenuity of ancient mathematicians and their enduring contributions to our understanding of numbers.

The HE Challenge RNS Can Address

HE is notorious for its substantial computational overhead, which presents a significant obstacle to its adoption in real-world applications. A natural question arises: why does HE carry such a high computational cost? While several factors contribute to this overhead, a major culprit lies in the arithmetic operations inherent to most HE schemes, which often involve manipulating very large integers (hundreds to thousands of bits). A common approach to handling large integers is to employ multi-precision arithmetic, but these operations are inherently sequential (due to carry and borrow propagations), leading to significant performance bottlenecks. Here comes the role of RNS, which provides an alternative (carry- and borrow-free) approach for tackling large integer problems, offering significant efficiency gains compared to the traditional multi-precision arithmetic approach.

With RNS, large integer problems (such as those found in HE) can be divided into smaller, independent sub-problems that can be solved simultaneously. Moreover, the size of the smaller sub-problems can be controlled by defining the RNS parameters. This ability to control the size of sub-problems and solve them in parallel makes RNS a widely used approach in HE and many other cryptographic technologies.

The Intuition behind RNS

RNS relies on a fundamental principle of problem-solving across various scientific disciplines: divide and conquer. This approach involves breaking down a large, complex problem into smaller, more manageable sub-problems. The core idea is that solving these smaller sub-problems individually is significantly easier than tackling the original problem directly. Once solutions for these smaller sub-problems are obtained, they are combined to arrive at a solution for the overall problem. This “divide and conquer” strategy is a cornerstone of efficient problem-solving in many fields, and RNS elegantly applies this principle to large integer arithmetic.

“If, in some cataclysm, all of scientific knowledge were to be destroyed, and only one sentence passed on to the next generations of creatures, what statement would contain the most information in the fewest words? I believe it is the atomic hypothesis (or the atomic fact, or whatever you wish to call it) that all things are made of atoms - little particles that move around in perpetual motion, attracting each other when they are a little distance apart, but repelling upon being squeezed into one another. In that one sentence, you will see, there is an enormous amount of information about the world, if just a little imagination and thinking are applied.”

Richard Feynman, The Feynman Lectures on Physics, Vol. I, Ch. 1

RNS offers a powerful approach to tackling complex computations involving large integer arithmetic. Using a decomposition map, a large integer problem \(P\) is decomposed into multiple smaller, simpler sub-problems \(\{p_0, p_1, \ldots, p_{r-1}\}\) that are easier to solve, generating sub-solutions \(\{s_0, s_1, \ldots, s_{r-1}\}\). But that is not all: RNS also eliminates the interdependence among these smaller sub-problems, decoupling them so they can be solved simultaneously. This means that if you have multiple solvers, you can simultaneously work on these smaller sub-problems, leading to a dramatic speedup in overall computation time. This concurrent processing capability is a major advantage of RNS and a crucial factor in its ability to accelerate complex HE operations. Lastly, if necessary, you can reconstruct the solution \(S\) to \(P\) using a reconstruction map. This is illustrated in the figure below.

It is worth noting that the decomposition and/or reconstruction maps may not always be necessary. In some cases, a large problem can be directly created in the sub-problems domain as a collection of multiple small problems. This eliminates the need for a decomposition map. Depending on the problem, you can continue working within the sub-problems domain, performing additional computations as needed. As you further solve the problem, the number of sub-problems may decrease (e.g., due to scaling-down operations), simplifying or eliminating the need for a reconstruction map. This flexibility is a significant advantage of the RNS approach, allowing you to adapt your strategy to the specific requirements of your problem.

HE computations provide a prime example of this, where some of these maps become entirely unnecessary.

Integer Arithmetic with RNS

Now that we have introduced RNS and the intuition behind it, we can explore how it enables basic integer arithmetic operations. Specifically, we will examine addition, subtraction, multiplication, and scaling, which are the fundamental arithmetic operations used in nearly all RNS-based HE implementations. But first, let us introduce some RNS notations, symbols, and basic concepts.

Integer Remainder Theorem

The integer remainder theorem states that for any integer \(a\) and positive integer \(m\), there exist two integers, the quotient \(q\) and the remainder \(r\), such that:

The quotient \(q\) can be computed using the floor function: \(q = \left\lfloor \frac{a}{m}\right\rfloor\). Here, division is performed in the real number domain, and the result is rounded down to the greatest integer less than or equal to \(\frac{a}{m}\).

Equation (1) can be rearranged to solve for \(r\) as follows:

In the literature, the remainder \(r\) is often denoted as \(r = \lvert a\rvert_{m}\), \(r = [a]_{m}\), or \(r \equiv a \pmod{m}\) (read as \(r\) is congruent to \(a\) mod \(m\)), where \(m\) is commonly referred to as the modulus. In this article, \(\lvert a\rvert_m\) denotes the non-negative remainder in \(\{0, 1, \ldots, m-1\}\) defined by Equation (2). Later on, we will also need the centered remainder \([a]_m \in [-\frac{m}{2}, \frac{m}{2})\), which equals \(\lvert a\rvert_m\) when \(\lvert a\rvert_m \lt \frac{m}{2}\) and \(\lvert a\rvert_m - m\) otherwise.

Example (1)

Find the quotient \(q\) and remainder \(r\) for the integer \(a = 27\) and modulus \(m = 11\).

Solution:

The quotient is \(q = \left\lfloor \frac{27}{11} \right\rfloor = 2\), and the remainder (that is, \(\lvert 27\rvert_{11}\)) is \(r = 27 - 2\cdot 11 = 5\).

Open this example in the calculator

RNS Base

RNS is defined over a set of pairwise co-prime moduli, referred to as the RNS base, and denoted as \(\mathcal{B}=\{m_0, \ldots, m_{k-1}\}\). Two moduli \(m_i\) and \(m_j\) are considered co-prime if their Greatest Common Divisor (GCD) is 1, i.e., \(\text{GCD}(m_i, m_j)=1\) for all \(i \neq j\).

Example (2): Standard RNS Base

The RNS base \(\mathcal{B}_1=\{5, 7, 16\}\) is standard (or good) as its moduli are pairwise co-prime:

• \(\text{GCD}(5, 7) = 1\),
• \(\text{GCD}(5, 16) = 1\),
• \(\text{GCD}(7, 16) = 1\).

Standard RNS bases allow unique RNS representations of numbers within their dynamic range (defined below).

Open this example in the calculator

Example (3): Non-Standard RNS Base

The RNS base \(\mathcal{B}_2=\{5, 8, 16\}\) is non-standard (or bad) as its moduli are not pairwise co-prime:

• \(\text{GCD}(5, 8) = 1\),
• \(\text{GCD}(5, 16) = 1\),
• \(\text{GCD}(8, 16) = 8\).

With a non-standard base, uniqueness is lost: distinct integers within the dynamic range can share the same RNS representation.

Open this example in the calculator

Hereafter, this article will focus exclusively on RNSs with standard bases.

Choosing the moduli in practice. The toy bases in this article are chosen for pen-and-paper arithmetic. In practice, HE libraries choose the moduli as distinct primes, which makes them pairwise co-prime automatically, and of a size that fits the machine word, e.g., up to 60 bits when 64-bit words are used. Moreover, since HE schemes multiply polynomials, each prime \(m_i\) is chosen to be NTT-friendly, i.e., \(m_i \equiv 1 \pmod{2N}\) where \(N\) is the ring dimension, so that polynomial multiplication modulo each modulus can use the Number Theoretic Transform (see my NTT article). The combination of RNS over the coefficients and NTT over the polynomial is known as the DoubleCRT representation, introduced in HElib (Gentry, Halevi & Smart, 2012), and it is how OpenFHE, SEAL, HElib, and Lattigo store their ciphertexts.

RNS Dynamic Range

An important characteristic of RNS is its dynamic range, denoted as \(M\). The dynamic range defines the set of integers that a specific RNS system with a given standard base can represent uniquely.

An RNS system with a standard base \(\{m_0, \ldots, m_{k-1}\}\) can uniquely represent unsigned or signed integers in the following ranges:

• For unsigned numbers: \(\{0, 1, \ldots, M-1\}\).
• For signed numbers:
  • \(\{-\frac{M-1}{2}, \ldots, -1, 0, 1, \ldots, \frac{M-1}{2}\}\) for an odd \(M\),
  • \(\{-\frac{M}{2}, \ldots, -1, 0, 1, \ldots, \frac{M}{2}-1\}\) for an even \(M\),

where the dynamic range is \(M=\prod_{i=0}^{k-1}m_i\).

Note that numbers greater than or equal to \(M\) (the largest representable unsigned number is \(M-1\)) wrap around modulo \(M\). In other words, arithmetic operations are performed modulo \(M\), or in \(\mathbb{Z}_M\). Thanks to the CRT, the \(M\) possible values in the RNS system represent \(M\) distinct residue classes. For example, \(M+5 \equiv 5 \pmod{M}\).

Example (4)

Find the dynamic range of the RNS system in Example (2).

Solution:

\(M = 5 \cdot 7 \cdot 16 = 560\).

Open this example in the calculator

Signed numbers. A signed integer \(x\) in the range above is stored through its non-negative representative \(\lvert x\rvert_M\) (that is, \(x + M\) when \(x\) is negative), and its residues are simply the residues of that representative. Equivalently, each residue is the non-negative remainder \(\lvert x\rvert_{m_i}\) of \(x\) itself, since \(\lvert x + M\rvert_{m_i} = \lvert x\rvert_{m_i}\). Negation is therefore limb-wise: the residue of \(-x\) modulo \(m_i\) is \(m_i - x_i\) when \(x_i \neq 0\), and \(0\) otherwise. Reading the sign of a number back, however, requires knowing whether \(\lvert x\rvert_M\) lies below \(\frac{M}{2}\) (non-negative) or at or above it (negative), which is magnitude information that no single residue reveals; we will return to this point shortly. HE implementations use the signed view constantly: the noise in a ciphertext is a small signed quantity around zero, and the centered remainder \([x]_m\) is the natural tool for keeping it small.

Example (5)

Represent \(x = -20\) with respect to the base \(\mathcal{B}=\{3, 5, 7\}\), where \(M = 105\).

Solution:

The non-negative representative is \(\lvert {-20}\rvert_{105} = -20 + 105 = 85\), whose residues are \((\lvert 85\rvert_3, \lvert 85\rvert_5, \lvert 85\rvert_7) = (1, 0, 1)\). We get the same result by negating the residues of \(20\), which are \((2, 0, 6)\): \((3 - 2, 0, 7 - 6) = (1, 0, 1)\). In fact, \(-20 = (-7)\cdot 3 + 1 = (-4) \cdot 5 + 0 = (-3) \cdot 7 + 1\).

Open this example in the calculator

Hereafter, our examples use unsigned numbers, as this keeps the arithmetic simple. However, it is essential to note that both unsigned and signed number representations are required for RNS implementations of HE.

RNS Representation of Integers

In RNS, an integer \(a\) is represented as a set of residues with respect to the moduli in the RNS base \(\mathcal{B}=\{m_0,\ldots,m_{k-1}\}\). The RNS representation of \(a \in \mathbb{Z}_M\) is denoted as:

where \(a_i\) is the remainder (or residue) of \(a\) modulo \(m_i\).

The \(\text{RNS}_{\text{Decompose}}\) map can be thought of as the decomposition map illustrated in Figure 1, with \(r = k\) sub-problems, one per modulus.

Note that the magnitude of the input \(a\) can be as large as \(M-1\) (assuming worst-case analysis and \(a\) within the dynamic range), whereas the residues (a.k.a. channels or limbs) \(a_i\) have magnitudes smaller than the corresponding \(m_i\). Hence, the map is known as decomposition, since the moduli \(m_i\) are smaller than the dynamic range \(M\). Moreover, one can control the limbs’ magnitudes by selecting moduli of the preferred size.

This decomposition is also a gift for HE. Key switching, the operation behind relinearization and slot rotations, needs to split a large number into small digits whose recombination is linear. In RNS, the limbs themselves serve as those digits, at no extra cost, whereas extracting the digits of a positional (multi-precision) number is a sequential operation.

Example (6)

Find the RNS representations of \(a = 204\), \(b=47\), and \(c = 99\) with respect to the base \(\mathcal{B}=\{3,5,7\}\).

Solution:

First, let’s calculate the dynamic range of the system: \(M = 3\cdot 5 \cdot 7 = 105\). Note that \(a \gt M\), but this does not pose a problem since \(a\) is automatically reduced modulo \(M\). Next, we find the RNS representation of each number using Equation (3):

• a = 204:
  • \(a_0 = \lvert 204\rvert_3 = 0\),
  • \(a_1 = \lvert 204\rvert_5 = 4\),
  • \(a_2 = \lvert 204\rvert_7 = 1\),
  • \(\lvert a\rvert_{\mathcal{B}} = (0, 4, 1)\).
• b = 47:
  • \(b_0 = \lvert 47\rvert_3 = 2\),
  • \(b_1 = \lvert 47\rvert_5 = 2\),
  • \(b_2 = \lvert 47\rvert_7 = 5\),
  • \(\lvert b\rvert_{\mathcal{B}} = (2, 2, 5)\).
• c = 99:
  • \(c_0 = \lvert 99\rvert_3 = 0\),
  • \(c_1 = \lvert 99\rvert_5 = 4\),
  • \(c_2 = \lvert 99\rvert_7 = 1\),
  • \(\lvert c\rvert_{\mathcal{B}} = (0, 4, 1)\).

Note that the RNS representations of \(a\) and \(c\) are the same since \(204 \equiv 99 \pmod{105}\).

Open this example in the calculator

Addition and Subtraction in RNS

Given an RNS system with respect to the base \(\mathcal{B}=\{m_0, m_1, \ldots, m_{k-1}\}\), two RNS numbers \(\lvert a\rvert_\mathcal{B}\) and \(\lvert b\rvert_\mathcal{B}\) can be added or subtracted as follows:

Addition

Subtraction

Note how addition and subtraction can be performed for each RNS residue (or limb) independently. On vector machines, this can be done via vectorized instructions. This illustrates the parallelism advantage of RNS we mentioned previously.

Example (7)

Calculate the sum and difference of \(\lvert a\rvert_\mathcal{B}\) and \(\lvert b\rvert_\mathcal{B}\) from Example (6).

Solution:

• Sum. Using Equation (4), the sum is \(\lvert a+b\rvert_\mathcal{B} = (\lvert 0 + 2\rvert_3, \lvert 4 + 2\rvert_5, \lvert 1 + 5\rvert_7) = (2, 1, 6)\). In fact, \(204 + 47 = 251 \equiv 41 \pmod{105}\), and \(\lvert 41\rvert_\mathcal{B} = (2, 1, 6)\) via Equation (3).
• Difference. Using Equation (5), the difference is \(\lvert a-b\rvert_\mathcal{B} = (\lvert 0 - 2\rvert_3, \lvert 4 - 2\rvert_5, \lvert 1 - 5\rvert_7) = (1, 2, 3)\). In fact, \(204 - 47 = 157 \equiv 52 \pmod{105}\), and \(\lvert 52\rvert_\mathcal{B} = (1, 2, 3)\) via Equation (3).

Open this example in the calculator

Multiplication in RNS

Similar to addition and subtraction, multiplication in RNS can be done limb-wise. More formally, given an RNS system with respect to the base \(\mathcal{B}=\{m_0, m_1, \ldots, m_{k-1}\}\), the product of two RNS numbers \(\lvert a\rvert_\mathcal{B}\) and \(\lvert b\rvert_\mathcal{B}\) can be found as follows:

Example (8)

Calculate the product of \(\lvert a\rvert_\mathcal{B}\) and \(\lvert b\rvert_\mathcal{B}\) from Example (6).

Solution:

Using Equation (6), the product is \(\lvert a\cdot b\rvert_\mathcal{B} = (\lvert 0 \cdot 2\rvert_3, \lvert 4 \cdot 2\rvert_5, \lvert 1 \cdot 5\rvert_7) = (0, 3, 5)\). In fact, \(204 \cdot 47 = 9588 \equiv 33 \pmod{105}\), and \(\lvert 33\rvert_\mathcal{B} = (0, 3, 5)\) via Equation (3).

Open this example in the calculator

A word on cost: each limb-wise product must be reduced modulo \(m_i\), and this reduction, rather than the double-word product itself, is where the cost of a limb operation lies. Practical implementations avoid a hardware division by using Barrett reduction, Montgomery multiplication, or, when one operand is a known constant (as with the twiddle factors of the NTT), Shoup’s multiplication with a precomputed quotient. These techniques are beyond the scope of this article; my NTT article shows Shoup’s method at work inside OpenFHE.

The Magnitude Problem

So far, everything has been limb-wise, and it is tempting to conclude that RNS makes all of integer arithmetic embarrassingly parallel. Here is the catch. A residue tells you the remainder of \(a\) modulo one modulus and nothing about the size of \(a\) within the dynamic range: the numbers \(5\) and \(5 + 3 \cdot 5 = 20\) have identical residues modulo \(3\) and modulo \(5\), and only the residue modulo \(7\) tells them apart. Any operation that depends on the magnitude of a number, rather than on its residue classes, therefore resists a limb-wise implementation. Comparing two numbers, detecting the sign of a number, detecting overflow beyond \(M\), rounding, and general division all require (at least partial) knowledge of where \(a\) sits in \([0, M)\).

This is the fundamental trade-off of RNS: we gave up positional information to gain carry-free parallelism. The remaining sections of this article are, in one way or another, about recovering just enough magnitude information to perform the two magnitude-dependent operations that HE cannot live without: scaling (division with rounding) and base extension.

Division in RNS

Division in RNS is more complex compared to addition, subtraction, or multiplication, for the reason we just discussed. However, certain variants of division are relatively simple. We will explore the variants of division that can be done efficiently in RNS.

Basis of Fast Division

The basic idea behind fast division is based on the following observation. Assume the integer dividend \(a\) is to be integer-divided by the integer divisor \(b\), resulting in the quotient \(c\). Then by Equation (1), we can express \(a\) as \(a = c \cdot b + \lvert a\rvert_b\), which can be rearranged to solve for the quotient \(c\) as:

where \(b^{-1}\) denotes the multiplicative inverse of \(b\) modulo the moduli of the base in which the quotient is represented (more on this below). Equation (7) forms the basis of fast division, which can be performed via subtraction and multiplication only, both of which are simple and fast in RNS.

The primary challenge in Equation (7) is computing \(\lvert a\rvert_b\) in RNS. This gives rise to three variants of division:

1. Exact multiples: When \(a\) is known to be an exact multiple of \(b\), so that \(\lvert a\rvert_b = 0\).
2. Scaling: When \(b\) is a product of one or more moduli of the underlying RNS base, that is, \(b\) is known, and \(\lvert a\rvert_b\) can be read off the RNS representation of \(a\).
3. General division: When \(b\) is an arbitrary integer, the computation becomes significantly more complex.

Fortunately, the simpler cases (exact multiples and scaling) are the ones commonly used in RNS implementations of HE. As a result, general division is beyond the scope of this article.

Exact multiples

Assuming that the dividend \(a\) is an exact multiple of the divisor \(b\), then \(\frac{a}{b}\) in RNS can be calculated as follows:

where \(b^{-1}\) is the multiplicative inverse of \(b\) in \(\mathbb{Z}_M\) satisfying:

The multiplicative inverse can be found efficiently via the extended Euclidean algorithm, and it is guaranteed to exist if and only if \(\text{GCD}(b,M)=1\).

In other words, ‘exact multiples’ division can be converted to multiplication by the multiplicative inverse of the divisor. Exact multiples division can be further optimized when the divisor \(b\) is a known constant, which allows one to precompute and cache \(\lvert b^{-1}\rvert_\mathcal{B}\) for future use.

Example (9)

Given the RNS system from Example (6), find \(\left\lvert \frac{65}{13}\right\rvert _\mathcal{B}\).

Solution:

1. Find the RNS representation of \(65\) via Equation (3): \(\lvert 65\rvert_\mathcal{B} = (2, 0, 2)\).
2. Find the multiplicative inverse of \(13\) in \(\mathbb{Z}_M\) using the extended Euclidean algorithm: \(13^{-1} \equiv 97 \pmod{105}\), since \(13\cdot 97 = 1261 = 12 \cdot 105 + 1\).
3. Find the RNS representation of \(97\) via Equation (3): \(\lvert 97\rvert_\mathcal{B} = (1, 2, 6)\).
4. Calculate the division using Equation (8): \(\left\lvert \frac{65}{13}\right\rvert _\mathcal{B} = (\lvert 2 \cdot 1\rvert_3, \lvert 0 \cdot 2\rvert_5, \lvert 2 \cdot 6\rvert_7 ) = (2, 0, 5)\).

In fact, \(\frac{65}{13} = 5\), and \(\lvert 5\rvert_\mathcal{B} = (2, 0, 5)\). Note that Steps 2 and 3 above can be combined by computing \(\lvert b^{-1}\rvert_{m_i}\) directly for each modulus, since the residue of the inverse modulo \(M\) is the inverse modulo \(m_i\).

Open this example in the calculator

Scaling

The scaling variant of division is particularly prevalent in RNS implementations of HE. In this scenario:

• The divisor is a product of one or more moduli of the RNS base, i.e., \(b = \prod_{m_i \in \mathcal{S}} m_i\) for some subset \(\mathcal{S} \subseteq \mathcal{B}\) of the moduli.
• As a result, \(b\) is a known constant.
• Since \(b\) divides \(M\), \(b\) has no inverse modulo \(M\) (nor modulo the moduli in \(\mathcal{S}\)). It does have an inverse modulo every modulus outside \(\mathcal{S}\), so the essential constant of Equation (7), \(\lvert b^{-1}\rvert_{\mathcal{B}\setminus\mathcal{S}}\), can be precomputed.
• Additionally, \(\lvert a\rvert_b\) in Equation (7) is available from the limbs in \(\mathcal{S}\): directly when \(\mathcal{S}\) contains a single modulus, and otherwise by carrying it from the limbs in \(\mathcal{S}\) to the remaining moduli, which is a small base extension of the kind covered below.

This variant is not only common but also efficient, thanks to the precomputable constants and the straightforward computation of \(\lvert a\rvert_b\). There is, however, an important consideration: the resulting quotient will be defined with respect to the reduced RNS base \(\mathcal{B}\setminus \mathcal{S}\), excluding the moduli present in \(b\). Fortunately, this can be solved via an efficient procedure known as base extension.

Example (10)

Given the RNS system from Example (6), find the integer division \(\left\lfloor\frac{83}{7}\right\rfloor\) in RNS. Here, \(a = 83\), \(b = 7\), \(\mathcal{B}=\{3, 5, 7\}\), and \(\mathcal{S}=\{7\}\).

Solution:

1. Find the RNS representation of \(83\) via Equation (3): \(\lvert 83\rvert_\mathcal{B} = (2, 3, 6)\).
2. Precompute the constant \(\lvert 7^{-1}\rvert_{\mathcal{B}\setminus\mathcal{S}}\):
   • \(\lvert 7^{-1}\rvert_{3} = 1\), since \(7\cdot 1 = 7 \equiv 1 \pmod{3}\),
   • \(\lvert 7^{-1}\rvert_{5} = 3\), since \(7\cdot 3 = 21 \equiv 1 \pmod{5}\).
3. Extract \(\lvert 83\rvert_\mathcal{S}\) from its RNS representation: \(\lvert 83\rvert_7 = 6\) (the last limb, which corresponds to the divisor modulus \(7\)).
4. Adjust the underlying RNS base to become \(\mathcal{B}' = \mathcal{B}\setminus \mathcal{S} = \{3, 5\}\).
5. Apply Equation (7) in the base \(\mathcal{B}'\):
   • Represent the remainder in \(\mathcal{B}'\): \(\lvert 6\rvert_{\mathcal{B}'} = (0, 1)\).
   • Compute the difference: \((\lvert 2 - 0\rvert_3, \lvert 3 - 1\rvert_5) = (2, 2)\).
   • Multiply the difference by the multiplicative inverse of the divisor: \(c = (\lvert 2 \cdot 1\rvert_3, \lvert 2 \cdot 3\rvert_5) = (2, 1)\).

In fact, \(\left\lfloor\frac{83}{7}\right\rfloor = 11\), and \(\lvert 11\rvert_{\mathcal{B}'} = (2, 1)\).

If necessary, one can extend the quotient \(c\) from the RNS base \(\mathcal{B}'\) to the original base \(\mathcal{B}\) via base extension, which is covered later.

Open this example in the calculator

Scaling with Rounding

The scaling above computes the floor \(\left\lfloor \frac{a}{b} \right\rfloor\). HE needs a slightly different operation: rounding to the nearest integer, denoted \(\left\lceil \frac{a}{b} \right\rfloor\). This is what BFV decryption computes, what modulus switching computes in BFV (and, up to a correction that keeps the result congruent to the input modulo the plaintext modulus, in BGV), and what rescaling computes in CKKS. The good news is that rounding is flooring in disguise: replace the non-negative remainder in Equation (7) by the centered remainder \([a]_b \in [-\frac{b}{2}, \frac{b}{2})\),

(If \(b\) is even and \(\frac{a}{b}\) lies exactly halfway between two integers, the half-open interval \([-\frac{b}{2}, \frac{b}{2})\) resolves the tie upward; a different convention for \([a]_b\) would resolve it differently.) The numerator is again an exact multiple of \(b\), so the RNS recipe is unchanged: read \([a]_b\) off the limbs in \(\mathcal{S}\) (when \(\mathcal{S} = \{m_i\}\), it is simply \(a_i\) or \(a_i - m_i\)), subtract it from every remaining limb, and multiply by \(\lvert b^{-1}\rvert_{\mathcal{B}\setminus\mathcal{S}}\). Equivalently, one can add \(\left\lfloor \frac{b}{2} \right\rfloor\) to \(a\) (limb-wise) and take the floor. In the full RNS variants of HE schemes, the divisor of CKKS rescaling (and of modulus switching by one level) is a single modulus of the modulus chain, which makes rescaling one of the cheapest operations of the whole scheme: one residue is broadcast to the other limbs, followed by one subtraction and one multiplication per limb (Cheon et al., 2018). BFV decryption, by contrast, divides by the whole ciphertext modulus, and the full RNS variants of BFV handle it with the same kind of machinery (auxiliary moduli or floating-point estimates) that the base extension sections below describe.

Example (11)

Given the RNS system from Example (6), find \(\left\lceil\frac{83}{7}\right\rfloor\) in RNS.

Solution:

1. From Example (10), \(\lvert 83\rvert_\mathcal{B} = (2, 3, 6)\), \(\mathcal{B}' = \{3, 5\}\), and \(\lvert 7^{-1}\rvert_{\mathcal{B}'} = (1, 3)\).
2. Compute the centered remainder: \(\lvert 83\rvert_7 = 6 \gt \frac{7}{2}\), hence \([83]_7 = 6 - 7 = -1\).
3. Represent it in \(\mathcal{B}'\) and subtract: \((\lvert 2 - (-1)\rvert_3, \lvert 3 - (-1)\rvert_5) = (0, 4)\).
4. Multiply by the inverse of the divisor: \((\lvert 0 \cdot 1\rvert_3, \lvert 4 \cdot 3\rvert_5) = (0, 2)\).

In fact, \(\frac{83}{7} \approx 11.86\), so \(\left\lceil\frac{83}{7}\right\rfloor = 12\), and \(\lvert 12\rvert_{\mathcal{B}'} = (0, 2)\). Compare with the floor \(11\) from Example (10), whose representation is \((2, 1)\).

Open this example in the calculator

RNS Reconstruction Map

The RNS reconstruction map is a crucial component that enables the conversion of numbers from their RNS representation to their positional representation (e.g., decimal or binary). This process is illustrated by the lower arrow in Figure 1.

There are two primary methods for converting numbers from RNS to positional representation:

1. Mixed Radix Conversion (MRC)
2. Chinese Remainder Theorem (CRT)

MRC converts the residues into mixed-radix digits using only small-modulus arithmetic. It is inherently sequential, but the mixed-radix digits make magnitude comparison easy, so it is the natural tool when numbers must be compared. In this discussion, we will focus on the CRT method due to its widespread adoption and utility in RNS applications, and because it is the seed of base extension.

CRT-Based RNS Reconstruction Map

The integer \(a\) (in positional representation) corresponding to the RNS representation \(\lvert a\rvert_\mathcal{B} = (a_0, a_1, \ldots, a_{k-1})\) with respect to the base \(\mathcal{B}=\{m_0, m_1, \ldots, m_{k-1}\}\) can be reconstructed using the CRT as:

where:

• \(M=\prod_{i=0}^{k-1}m_i\) is the product of all moduli in the base \(\mathcal{B}\),
• \(t_i = \frac{M}{m_i}\) is the product of all moduli except \(m_i\), and
• \(s_i = \left\lvert t_i^{-1}\right\rvert _{m_i}\) is the multiplicative inverse of \(t_i\) modulo \(m_i\) (a precomputed constant of the base, not to be confused with the sub-solutions \(s_i\) of Figure 1).

Although both expressions are equivalent (the two summands differ by a multiple of \(m_i t_i = M\)), the second one is the form used in practice. Both cost \(k\) big multiplications (by the constants \(t_i\)) and \(k-1\) big additions modulo \(M\). The second expression adds \(k\) cheap single-word reductions modulo \(m_i\) (the products \(\lvert a_i \, s_i\rvert_{m_i}\)), but in return every one of its summands is smaller than \(M\), so the sum before the final reduction overflows \(M\) at most \(k-1\) times (Observation 3 below). In the first expression, a summand \(a_i \, s_i \, t_i\) can be as large as about \(m_i M\), so the overflow can be much larger. Keeping the overflow small and predictable is exactly what base extension will exploit.

A few important observations can be made regarding Equation (11):

1. The constants \(s_i\) and \(t_i\) do not depend on the input. Hence, they can be precomputed and cached.
2. The magnitude of each of the terms \(\lvert a_i \, s_i\rvert_{m_i}\) is strictly less than the corresponding \(m_i\). Hence, they can be computed using a processor with a word size equal to or greater than the size of \(m_i\). Although the product may require double the word size before modular reduction, most modern processors provide intrinsics for double-word multiplication, making this a non-issue.
3. In the second expression, each summand \(\lvert a_i \, s_i\rvert_{m_i} \, t_i\) is at most \((m_i - 1) \, t_i = M - t_i\), which is strictly less than \(M\). The sum of the \(k\) summands is therefore strictly less than \(kM\): before the final reduction, it equals \(a + \alpha M\) for some integer \(0 \leq \alpha \leq k-1\). In other words, we can have at most \(k-1\) overflows beyond \(M\). Keep this \(\alpha\) in mind; it is the central character of base extension below.
4. The main challenge lies in the arithmetic involving the constants \(t_i\). Although precomputed, they can be as large as \(\frac{M}{\min_i m_i}\) and may exceed the word size of the processor, so multiplying by them and accumulating modulo \(M\) requires multi-precision arithmetic, which can be computationally expensive.

Despite this computational challenge, in most applications, the CRT reconstruction map is performed only once, at the end of a computation. As a result, the additional computational cost can be tolerated. Even better, in some applications, the problem size decreases over time, making the reconstruction map either unnecessary or simpler to compute. This alleviates the computational burden associated with the reconstruction map, making it a viable solution for many use cases, including HE.

Example (12)

Given the RNS system with base \(\mathcal{B}=\{3,5,7\}\) and the RNS representation \((a_0, a_1, a_2)=(1, 4, 1)\) of the integer \(a\), find \(a\).

Solution:

1. Find the constants \(t_i = \frac{M}{m_i}\): \(t_0 = \frac{105}{3} = 35\), \(t_1 = \frac{105}{5} = 21\), and \(t_2 = \frac{105}{7} = 15\).
2. Find the constants \(s_i = \lvert t_i^{-1}\rvert_{m_i}\): \(s_0 = \lvert 35^{-1}\rvert_3 = \lvert 2^{-1}\rvert_3 = 2\), \(s_1 = \lvert 21^{-1}\rvert_5 = \lvert 1^{-1}\rvert_5 = 1\), and \(s_2 = \lvert 15^{-1}\rvert_7 = \lvert 1^{-1}\rvert_7 = 1\).
3. Now we can compute \(a\) using the second expression of Equation (11):
   • \(a = \left\lvert \lvert 1\cdot 2\rvert_3\cdot 35 + \lvert 4\cdot 1\rvert_5\cdot 21 + \lvert 1\cdot 1\rvert_7\cdot 15 \right\rvert _{105}\),
   • \(a = \lvert 70 + 84 + 15\rvert_{105} = \lvert 169\rvert_{105}\),
   • the sum \(169 = 64 + 1 \cdot 105\) overflowed once (\(\alpha = 1\)), so \(a = 64\).

In fact, the RNS representation \((1,4,1)\) corresponds to the integer \(64\), since \(\lvert 64\rvert_3 = 1\), \(\lvert 64\rvert_5 = 4\), and \(\lvert 64\rvert_7 = 1\) via Equation (3).

Open this example in the calculator

RNS Base Extension

RNS base extension (or conversion) is a procedure that allows extending the residues of a number in one RNS base to another base.

More formally, given:

• an RNS base \(\mathcal{B}=\{m_0, m_1, \dots, m_{k-1}\}\) of length \(k\),
• the RNS representation of a number \(\lvert a\rvert_\mathcal{B}\), and
• an additional RNS base \(\mathcal{B}' = \{m_k, m_{k+1}, \ldots, m_{k+l-1}\}\) of length \(l\),

compute \(\lvert a\rvert_{\mathcal{B} \cup \mathcal{B}'}\), given that all the moduli in \(\mathcal{B}\) and \(\mathcal{B}'\) are pairwise co-prime.

Basis of Base Extension

The fundamental concept of base extension is straightforward:

1. Convert the RNS number to its positional representation using the RNS reconstruction map.
2. Apply the decomposition map to the resulting positional representation to obtain the RNS representation in the new base.

The crucial aspect of base extension lies in developing efficient methods that avoid the overhead associated with explicit conversion to positional representation and its subsequent decomposition. Observation 3 above shows where the difficulty hides: reconstruction is a cheap sum of residue-sized products minus an unknown correction \(\alpha M\), and \(\alpha\) is exactly the magnitude information that residues do not carry.

We will review the Shenoy-Kumaresan method (Shenoy & Kumaresan, 1989), a CRT-based approach for efficient base extension.

Shenoy-Kumaresan Base Extension Algorithm

The Shenoy-Kumaresan base extension algorithm incorporates an auxiliary (redundant) RNS modulus, denoted as \(m_r\), alongside the RNS base. The residue \(a_r = \lvert a\rvert_{m_r}\) is carried along through the computation, i.e., every addition and multiplication is also performed modulo \(m_r\). Note that \(m_r\) must be co-prime with every modulus in the RNS base, and, as we will see, it must satisfy \(m_r \gt k - 1\).

Consider the RNS base \(\mathcal{B}=\{m_0, m_1, \ldots, m_{k-1}\}\) together with the auxiliary modulus \(m_r\), and suppose we want to extend \(\lvert a\rvert_\mathcal{B}\) to the new RNS base \(\mathcal{B}'\). By Observation 3, the second expression of Equation (11) can be written without the final reduction modulo \(M\) as:

If we knew \(\alpha\), we could compute \(\lvert a\rvert_n\) for every modulus \(n\) in \(\mathcal{B}'\) by evaluating Equation (12) modulo \(n\), one modulus at a time, using the precomputed constants \(\lvert t_i\rvert_n\) and \(\lvert M\rvert_n\). No multi-precision arithmetic would be needed.

The auxiliary modulus \(m_r\) helps us find \(\alpha\) efficiently. Reducing Equation (12) modulo \(m_r\) and solving for \(\alpha\) gives:

where all arithmetic operations are done modulo \(m_r\), given that the constants \(\lvert t_i\rvert_{m_r}\) and \(\lvert M^{-1}\rvert_{m_r}\) are precomputed and cached in memory. Equation (13) recovers \(\alpha\) exactly because \(\alpha\) lies in \(\{0, \ldots, k-1\}\) and \(m_r \gt k-1\), so \(\alpha\) is determined by its residue modulo \(m_r\).

After calculating \(\alpha\), the extension to the new base can be done via Equation (12).

Example (13)

Given \(\mathcal{B}=\{3, 5\}\), \(M=15\), \(m_r = 8\), \(\mathcal{B}'=\{7\}\), \(\lvert a\rvert_\mathcal{B} = (2, 1)\), and \(a_r = \lvert a\rvert_{8} = 3\), find \(\lvert a\rvert_{\mathcal{B}'}\).

Solution:

The constants are \(t_0 = 5\), \(t_1 = 3\), \(s_0 = \lvert 5^{-1}\rvert_3 = 2\), \(s_1 = \lvert 3^{-1}\rvert_5 = 2\), and \(\lvert M^{-1}\rvert_8 = \lvert 15^{-1}\rvert_8 = 7\) (since \(15 \cdot 7 = 105 = 13 \cdot 8 + 1\)). The residue-sized products are \(\lvert a_0 s_0\rvert_3 = \lvert 2 \cdot 2\rvert_3 = 1\) and \(\lvert a_1 s_1\rvert_5 = \lvert 1 \cdot 2\rvert_5 = 2\).

Step 1: find \(\alpha\) via Equation (13)

Step 2: find \(\lvert a\rvert_7\) via Equation (12)

In fact, \(a = 11\), since \(\lvert 11\rvert_{\{3,5\}} = (2, 1)\), and \(\lvert 11\rvert_7 = 4\). This example completes the scaling problem in Example (10), where we extend the result \(11\) from the base \(\{3,5\}\) back to the original base \(\{3,5,7\}\). (Note that the roles of \(\mathcal{B}\) and \(\mathcal{B}'\) are swapped relative to Example (10): here \(\mathcal{B} = \{3, 5\}\) is the reduced base we start from, and \(\mathcal{B}' = \{7\}\) is the base we extend to.)

Open this example in the calculator

In this example, the sum \(1 \cdot 5 + 2 \cdot 3 = 11\) did not overflow, so \(\alpha = 0\) and the correction was not needed. The next example shows the correction at work.

Example (14)

With the same setting as Example (13), extend \(\lvert a\rvert_\mathcal{B} = (1, 4)\) with \(a_r = 4\) to \(\mathcal{B}' = \{7\}\).

Solution:

The residue-sized products are \(\lvert a_0 s_0\rvert_3 = \lvert 1 \cdot 2\rvert_3 = 2\) and \(\lvert a_1 s_1\rvert_5 = \lvert 4 \cdot 2\rvert_5 = 3\).

Step 1: find \(\alpha\) via Equation (13)

Step 2: find \(\lvert a\rvert_7\) via Equation (12)

In fact, \(a = 4\): the sum \(2 \cdot 5 + 3 \cdot 3 = 19 = 4 + 1 \cdot 15\) overflowed once, so \(\alpha = 1\), and indeed \(\lvert 4\rvert_7 = 4\). Without the correction, we would have obtained \(\lvert 19\rvert_7 = 5\), which is wrong.

Open this example in the calculator

Note that if \(m_r\) is chosen as a power-of-two modulus, the reductions modulo \(m_r\) in Equation (13) become bit-mask operations (a bitwise AND with \(m_r - 1\)).

Note that the Shenoy-Kumaresan algorithm avoids multi-precision arithmetic since the large quantities (such as \(t_i\) and \(M\)) are precomputed, reduced modulo \(m_r\) or modulo the moduli of \(\mathcal{B}'\), and cached in memory. This optimization enables efficient computation and reduces the computational overhead associated with base extension. The price is the extra residue channel \(m_r\), which must be carried through every preceding operation.

Approximate RNS Base Extension

In certain applications, base extension can tolerate the overflow \(\alpha M\) in Equation (12), enabling approximate or fast base extension. This approach omits the \(\alpha\) correction step, simplifying the process. This method provides a trade-off between accuracy and computational efficiency. For each modulus \(n\) in the new base \(\mathcal{B}'\):

Equation (14) can be efficiently evaluated, but it yields the residues of \(a + \alpha M\) rather than those of \(a\), for some unknown integer \(0\leq \alpha \leq k-1\). In the HE context, approximate base extension was first used to implement a full RNS variant of the B/FV scheme (Bajard et al., 2016). In that design, the overflow is either tolerated (it only adds a little noise to the ciphertext) or reduced using auxiliary moduli: an input-side Montgomery-style reduction with a small auxiliary modulus \(\tilde{m}\), which shrinks the overflow to a small bounded residual rather than removing it, and an output-side exact correction in the style of the Shenoy-Kumaresan technique above (generalized to signed inputs), with the redundant modulus carried through the whole multiplication pipeline.

See the overflow error concretely in the calculator

Floating-Point Base Extension

Besides the Shenoy-Kumaresan approach, other exact base extension methods exist. Notably, one exact method (Halevi, Polyakov & Shoup, 2019) computes \(\alpha\) directly with floating-point arithmetic. Dividing Equation (12) by \(M\) gives \(\frac{a}{M} = \sum_{i} \frac{\lvert a_i \, s_i\rvert_{m_i}}{m_i} - \alpha\), and since \(0 \leq \frac{a}{M} \lt 1\),

Each fraction lies in \([0, 1)\), so the sum can be accumulated in double precision with a total error of the order of \(k \cdot 2^{-53}\) (at most about \(k^2 \cdot 2^{-53}\) once the rounding of the \(k-1\) additions is counted); the estimate is wrong only when \(\frac{a}{M}\) falls within that tiny distance of an integer, which happens with negligible probability for random inputs and, in the HE context, merely adds a small amount of noise when it does. For Example (14), \(\frac{2}{3} + \frac{3}{5} \approx 1.27\), so \(\alpha = 1\), as before. This approach eliminates the need for auxiliary moduli, but it:

• requires floating-point computations, and
• in its original formulation, tied the maximum size of the moduli in the scaling procedures (not in base extension) to the available floating-point precision. This constraint was later removed (Kim, Polyakov & Zucca, 2021), so that full 60-bit moduli are supported with plain double precision.

Compute the floating-point alpha in the calculator

Which approach do libraries use? Microsoft SEAL’s full RNS variant of BFV implements the integer-only machinery of Bajard et al.; PALISADE implemented both, shipping the floating-point approach of Halevi et al. first and adding the integer-only variant of Bajard et al. later; and OpenFHE, PALISADE’s successor, uses the improved floating-point variants of Kim et al. by default. Both families achieve the same multiplicative depth in practice once implemented exactly to specification (Bajard et al., 2019), and a detailed experimental comparison on CPUs and GPUs is given in my earlier work (Al Badawi et al., 2021). In scenarios where integer-only implementations are preferred, the Shenoy-Kumaresan approach remains the more suitable option. This preference is amplified in hardware implementations, where:

• integer arithmetic is generally simpler to implement, and
• mixed integer and floating-point units incur significant hardware costs.

For the full story of how these primitives compose into modulus switching, rescaling, and key switching across BGV, BFV, and CKKS, see the survey I co-authored (Al Badawi et al., 2026).

Try It

1. Open the RNS Calculator.
2. Build the base \(\{3, 5, 7\}\) on the Base page and read off \(M\), the signed and unsigned ranges, and the GCD table. Then break it with \(\{5, 8, 16\}\).
3. Convert 204 and -20, then add, subtract, and multiply on the Arithmetic page and watch the true-integer cross-check.
4. Divide 83 by 7 twice on the Division page: once with the floor, once with rounding.
5. Reconstruct \((1, 4, 1)\) with CRT, then switch to MRC, the sequential method this article names but never demonstrates.
6. Extend \((1, 4)\) from \(\{3, 5\}\) to \(\{7\}\) on the Base extension page and watch the alpha correction fire; compare Shenoy-Kumaresan, the approximate method, and the floating-point estimate side by side.
7. Or pick any of the fourteen examples from the preset menu; each loads with this article’s exact numbers.

The calculator runs entirely in your browser with exact integer arithmetic, and no data ever leaves your machine. The self-test page replays all fourteen examples plus randomized property tests against the same engine. The source is on GitHub.

Key Takeaways

• RNS can be used to avoid slow multi-precision integer arithmetic.
• RNS decomposes large integer problems into multiple smaller, simpler ones.
• Addition, subtraction, and multiplication in RNS are efficient and embarrassingly parallel.
• Operations that depend on the magnitude of a number (comparison, sign detection, overflow detection, rounding, and general division) are the hard operations in RNS.
• Exact division, scaling, and scaling with rounding by a known divisor can be efficiently computed via additions and multiplications.
• The RNS reconstruction map is computationally intensive and requires multi-precision arithmetic; however, it is rarely needed.
• RNS base extension can be done exactly with the Shenoy-Kumaresan algorithm (one auxiliary modulus), exactly with a floating-point estimate of the overflow, or approximately by tolerating the overflow. Leading HE libraries use both integer-only and floating-point variants.

References & Further Reading

If you want the full theory behind RNS and the papers that carried it into FHE, start here:

1. RNS textbook (theory and implementation): A. R. Omondi and A. B. Premkumar, Residue Number Systems: Theory and Implementation. Imperial College Press, 2007.
   • Publisher page (DOI)
2. RNS textbook (theory and applications): P. V. Ananda Mohan, Residue Number Systems: Theory and Applications. Birkhäuser, 2016.
   • Publisher page (DOI)
3. The FHE-specific survey: A. Al Badawi, A. Alexandru, G. Arakelov, C. Gouert, S. Gomenyuk, V. Kononova, Y. Doröz, and Y. Polyakov, “Efficient Large-Integer Arithmetic for FHE”. IACR ePrint 2026.
   • Read on IACR ePrint (2026/1608)
4. Shenoy-Kumaresan base extension: A. P. Shenoy and R. Kumaresan, “Fast base extension using a redundant modulus in RNS”. IEEE Transactions on Computers, 38(2):292-297, 1989.
   • Read on IEEE Xplore (DOI)
5. The first full RNS variant of BFV (integer-only, BEHZ): J.-C. Bajard, J. Eynard, M. A. Hasan, and V. Zucca, “A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes”. SAC 2016.
   • Read on IACR ePrint (2016/510)
6. The floating-point RNS variant of BFV (HPS): S. Halevi, Y. Polyakov, and V. Shoup, “An Improved RNS Variant of the BFV Homomorphic Encryption Scheme”. CT-RSA 2019.
   • Read on IACR ePrint (2018/117)
7. Improved HPS-style variants (OpenFHE default): A. Kim, Y. Polyakov, and V. Zucca, “Revisiting Homomorphic Encryption Schemes for Finite Fields”. ASIACRYPT 2021.
   • Read on IACR ePrint (2021/204)
8. BEHZ vs. HPS on CPUs and GPUs: A. Al Badawi, Y. Polyakov, K. M. M. Aung, B. Veeravalli, and K. Rohloff, “Implementation and Performance Evaluation of RNS Variants of the BFV Homomorphic Encryption Scheme”. IEEE Transactions on Emerging Topics in Computing, 2021.
   • Read on IACR ePrint (2018/589)
9. The BEHZ noise-growth correction: J.-C. Bajard, J. Eynard, P. Martins, L. Sousa, and V. Zucca, “Note on the noise growth of the RNS variants of the BFV scheme”. IACR ePrint 2019.
   • Read on IACR ePrint (2019/1266)
10. Full RNS CKKS (RNS-friendly rescaling): J. H. Cheon, K. Han, A. Kim, M. Kim, and Y. Song, “A Full RNS Variant of Approximate Homomorphic Encryption”. SAC 2018.
    • Read on IACR ePrint (2018/931)
11. DoubleCRT representation (HElib): C. Gentry, S. Halevi, and N. P. Smart, “Homomorphic Evaluation of the AES Circuit”. CRYPTO 2012.
    • Read on IACR ePrint (2012/099)
12. The BGV scheme: Z. Brakerski, C. Gentry, and V. Vaikuntanathan, “(Leveled) Fully Homomorphic Encryption without Bootstrapping”. TOCT 2014.
    • Read on IACR ePrint (2011/277)
13. Brakerski’s scale-invariant scheme (the “B” in B/FV): Z. Brakerski, “Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP”. CRYPTO 2012.
    • Read on IACR ePrint (2012/078)
14. The FV scheme: J. Fan and F. Vercauteren, “Somewhat Practical Fully Homomorphic Encryption”. IACR ePrint 2012.
    • Read on IACR ePrint (2012/144)
15. The CKKS scheme: J. H. Cheon, A. Kim, M. Kim, and Y. Song, “Homomorphic Encryption for Arithmetic of Approximate Numbers”. ASIACRYPT 2017.
    • Read on IACR ePrint (2016/421)
16. History of the Chinese Remainder Theorem: Wikipedia, “Chinese remainder theorem”, section History.
    • Read on Wikipedia
17. Cheng Dawei and the remainder verse: Wikipedia, “Cheng Dawei”.
    • Read on Wikipedia

Suggested Citation

If you found this article useful and wish to cite it in your work, I suggest:

Ahmad Al Badawi, The Residue Number System: A Non-Comprehensive Review, 2026, https://ahmadalbadawi.com/posts/2026/08/rns-review/

Or in BibTeX:

@misc{rnsreview2026,
  author = {Al Badawi, Ahmad},
  title = {The Residue Number System: A Non-Comprehensive Review},
  year = {2026},
  month = {August},
  howpublished = {\url{https://ahmadalbadawi.com/posts/2026/08/rns-review/}},
  note = {Accessed: [Current Date]}
}

Feedback: Please direct any typos, questions, comments, or issues to me at my contact page.

License: The text and content are licensed under CC BY 4.0.