We first review the Lagrange CRT recovery formula, where we see the approximation of multiple of is the main difficulty. And then we will see that by imposing bound on the represented big number, there will be a significant reduction on the cost of approximating that multiple of .
For the explicit CRT formula and its applications, we refer to Bernstein and Sorenson 1, Sections 2-4.
Lagrange CRT Recovery Formula
Let be odd co-prime moduli and . Let be a big integer and stored in RNS representation with , where by we mean the signed representative, i.e., we have . We have the following theorem to recover from ’s: Theorem Let then . Furthermore, if , then .
The congruence part can be proved by direct computation of ’s and the exact follows from the assumed range on .
In the context of computer arithmetic, the bound is always the case. Also from some well known algorithms due to Barrett and Montgomery, we know that, when computing , it is always better first perform (so that this number is within and ), and then perform the multiplication by (this is a big-number). Therefore, we define as the product of the above single precision modular multiplication. From now on, redefine This reduced sum may differ from the original by an integer multiple of , but remains congruent to modulo . We use this redefined throughout the rest of the note, and the Lagrange formula can be written as The remaining difficulty lies in the operation , i.e., how many multiples of to be subtracted?
On computation of modulo
Suppose multiples of are to be subtracted, that is, Since we have , this must satisfy That is, At first glance this seems useful, as if we can get by approximating the number . However, a second thought we found, that can lie at slightly above the boundary of , and that means we need a high precision to tell whether that approximates to or . (Similar situation occurs between and ).
This happens because allow just sit near the decision boundary between and . If, rather, we impose then the number does not touch that boundary. And if we can approximate with error , such approximation, by rounding it, yields directly. However, such imposed range bound will force since
Now we present a concrete way to compute : We first approximate each summand by : We will select after the error bound analysis. The first corresponds to discarding the low fractional bits in a two’s-complement fixed-point representation. The second replaces the scaled reciprocal by , which can be precomputed.
We then have As we mentioned above, we need approximation to with error , hence we here need to select such that and it turns out we can select is enough for our need. Finally we conclude that can be computed as where is pre-computed.
Applications
We present two applications of this finding: (1) extracting low bits of from RNS residues ’s and (2) extending RNS basis or changing RNS basis. In both applications, we assume and compute by the above method. Since this is exact, we have We can therefore perform the whole right-hand side modulo a target modulus, and directly obtain the residue of under that modulus.
For the first application, extracting low bits means computing . We have Here and can all be precomputed. During the computation, each multiplication and addition only needs to retain the low bits. Thus, after computing ’s and , we can directly combine them to obtain the desired low bits. For negative , the nonnegative residue gives the low bits of its two’s-complement representation.
For the second application, let , , be pairwise coprime odd moduli forming the new RNS basis. We can compute each new signed residue by Again, all and can be precomputed, and the same ’s and are used for every . Keeping the original residues together with additional residues whose moduli are coprime to extends the RNS basis; replacing the original representation by changes the RNS basis. In either case, we do not need to first recover the full big integer .
If the new basis is to determine the same signed integer uniquely, we also need , where . The same error analysis for computing the correction multiple in the new basis applies when .
References
- Daniel J. Bernstein and Jonathan P. Sorenson. “Modular exponentiation via the explicit Chinese remainder theorem.” Mathematics of Computation 76(257): 443-454, 2007. DOI: 10.1090/S0025-5718-06-01849-7.