On Explicit Lagrange CRT Recovery Formula


We first review the Lagrange CRT recovery formula, where we see the approximation of multiple of MM 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 MM.

For the explicit CRT formula and its applications, we refer to Bernstein and Sorenson 1, Sections 2-4.

Lagrange CRT Recovery Formula

Let mi,(1≤i≤k)m_{i}, (1\leq i\leq k) be odd co-prime moduli and M=∏i=1kmiM = \prod_{i=1}^{k} m_{i}. Let zz be a big integer and stored in RNS representation with zi=zmod⁡±miz_{i} = z \bmod^{\pm} m_{i}, where by mod⁡±\bmod ^{\pm} we mean the signed representative, i.e., we have −mi2≤zi≤mi2-\frac{m_{i}}{2}\leq z_{i}\leq \frac{m_{i}}{2}. We have the following theorem to recover zz from ziz_{i}’s: Theorem Let S=∑i=1kzi((Mmi)−1mod⁡±mi)(Mmi) S = \sum_{i=1}^{k} z_{i} \left( \left( \frac{M}{m_{i}} \right)^{-1} \bmod^{\pm} m_{i} \right)\left( \frac{M}{m_{i}} \right) then S≡zmod⁡MS \equiv z \bmod M. Furthermore, if −M2<z<M2-\frac{M}{2}<z< \frac{M}{2}, then z=Smod⁡±Mz = S \bmod^{\pm} M.

The congruence part can be proved by direct computation of Smod⁡miS \bmod m_{i}’s and the exact z=Smod⁡±Mz = S\bmod ^{\pm}M follows from the assumed range on zz.

In the context of computer arithmetic, the bound |z|<M2|z| < \frac{M}{2} is always the case. Also from some well known algorithms due to Barrett and Montgomery, we know that, when computing SS, it is always better first perform αi:=zi((Mmi)−1mod⁡±mi)mod⁡±mi \alpha_{i} := z_{i} \left( \left( \frac{M}{m_{i}} \right)^{-1} \bmod^{\pm} m_{i} \right) \bmod ^{\pm} m_{i} (so that this number is within −mi2-\frac{m_{i}}{2} and mi2\frac{m_{i}}{2}), and then perform the multiplication by Mmi\frac{M}{m_{i}} (this is a big-number). Therefore, we define αi\alpha_{i} as the product of the above single precision modular multiplication. From now on, redefine S:=∑i=1kαiMmi. S := \sum_{i=1}^{k} \alpha_{i}\frac{M}{m_{i}}. This reduced sum may differ from the original SS by an integer multiple of MM, but remains congruent to zz modulo MM. We use this redefined SS throughout the rest of the note, and the Lagrange formula can be written as z=Smod⁡±M=M∑i=1kαimimod⁡±M. z = S \bmod ^{\pm} M = M\sum_{i=1}^{k} \frac{\alpha_{i}}{m_{i}} \bmod ^{\pm}M . The remaining difficulty lies in the operation mod⁡±M\bmod ^{\pm}M, i.e., how many multiples of MM to be subtracted?

On computation of modulo MM

Suppose qq multiples of MM are to be subtracted, that is, z=S−qM=M∑i=1kαimi−qM=M(∑i=1kαimi−q). z = S-qM = M\sum_{i=1}^{k} \frac{\alpha_{i}}{m_{i}} - qM = M\left(\sum_{i=1}^{k} \frac{\alpha_{i}}{m_{i}} - q\right). Since we have |z|<M2|z|< \frac{M}{2}, this qq must satisfy |∑i=1kαimi−q|<12. \left|\sum_{i=1}^{k} \frac{\alpha_{i}}{m_{i}} - q\right| < \frac{1}{2}. That is, q=round(∑i=1kαimi). q = \mathrm{round}\left( \sum_{i=1}^k \frac{\alpha_{i}}{m_{i}}\right). At first glance this seems useful, as if we can get qq by approximating the number ∑αi/mi\sum \alpha_{i}/m_{i}. However, a second thought we found, that ∑αi/mi\sum \alpha_{i}/m_{i} can lie at slightly above the boundary of q−12q-\frac{1}{2}, and that means we need a high precision to tell whether that ∑αi/mi\sum \alpha_{i}/m_{i} approximates to qq or q−1q-1. (Similar situation occurs between qq and q+1q+1).

This happens because |∑i=1kαimi−q|<12, \left|\sum_{i=1}^{k} \frac{\alpha_{i}}{m_{i}} - q\right| < \frac{1}{2}, allow ∑αi/mi\sum \alpha_{i}/m_{i} just sit near the decision boundary between qq and q−1q-1. If, rather, we impose |∑i=1kαimi−q|<14 \left|\sum_{i=1}^{k} \frac{\alpha_{i}}{m_{i}} - q\right| < \frac{1}{4} then the number ∑αi/mi\sum \alpha_{i}/m_{i} does not touch that boundary. And if we can approximate ∑αi/mi\sum \alpha_{i}/m_{i} with error <14< \frac{1}{4}, such approximation, by rounding it, yields qq directly. However, such imposed range bound will force |z|<M4|z|< \frac{M}{4} since |z|=|M(∑i=1kαimi−q)|<M4. |z|= \left|M \left( \sum_{i=1}^{k} \frac{\alpha_{i}}{m_{i}} -q \right) \right| < \frac{M}{4}.

Now we present a concrete way to compute qq: We first approximate each summand αimi\frac{\alpha_{i}}{m_{i}} by : αimi∼12d⌊2d(αimi)⌋=12d⌊αi(2dmi)⌋∼12d⌊αi⌊2dmi⌋⌋=12d(αi⌊2dmi⌋) \frac{\alpha_{i}}{m_{i}} \sim \frac{1}{2^{d}}\left\lfloor 2^d \left( \frac{\alpha_{i}}{m_{i}} \right) \right\rfloor = \frac{1}{2^{d}}\left\lfloor \alpha_{i} \left( \frac{2^{d}}{m_{i}} \right) \right\rfloor \sim \frac{1}{2^{d}}\left\lfloor \alpha_{i} \left\lfloor {\frac{2^{d}}{m_{i}}} \right\rfloor \right\rfloor = \frac{1}{2^{d}}\left( \alpha_{i} \left\lfloor {\frac{2^{d}}{m_{i}}} \right\rfloor \right) We will select dd after the error bound analysis. The first ∼\sim corresponds to discarding the low fractional bits in a two’s-complement fixed-point representation. The second ∼\sim replaces the scaled reciprocal 2d/mi2^d/m_i by ⌊2d/mi⌋\lfloor 2^d/m_i\rfloor, which can be precomputed.

We then have |∑i=1kαimi−∑i=1k12d(αi⌊2dmi⌋)|≤∑i=1k|αi||1mi−12d⌊2dmi⌋|<∑i=1k(mi2)12d. \left|\sum_{i=1}^{k} \frac{\alpha_{i}}{m_{i}} - \sum_{i=1}^{k} \frac{1}{2^{d}}\left( \alpha_{i}\left\lfloor \frac{2^{d}}{m_{i}} \right\rfloor \right)\right|\leq \sum_{i=1}^{k} |\alpha_{i}|\left| \frac{1}{m_{i}}-\frac{1}{2^{d}}\left\lfloor \frac{2^{d}}{m_{i}} \right\rfloor \right| < \sum_{i=1}^{k} \left( \frac{m_{i}}{2} \right) \frac{1}{2^{d}}. As we mentioned above, we need approximation to ∑αi/mi\sum \alpha_{i}/m_{i} with error <14< \frac{1}{4}, hence we here need to select dd such that ∑i=1k(mi2)12d≤14 \sum_{i=1}^{k} \left( \frac{m_{i}}{2} \right) \frac{1}{2^{d}} \leq \frac{1}{4} and it turns out we can select d=⌈1+log⁡2(∑i=1kmi)⌉ d= \left\lceil 1+\log_{2}\left( \sum_{i=1}^{k}m_{i} \right) \right\rceil is enough for our need. Finally we conclude that qq can be computed as q=round(∑i=1k12d(αi⌊2dmi⌋)) q = \mathrm{round}\left( \sum_{i=1}^{k} \frac{1}{2^{d}}\left( \alpha_{i} \left\lfloor {\frac{2^{d}}{m_{i}}} \right\rfloor \right) \right) where ⌊2dmi⌋\lfloor \frac{2^{d}}{m_{i}} \rfloor is pre-computed.

Applications

We present two applications of this finding: (1) extracting low ℓ\ell bits of zz from RNS residues ziz_{i}’s and (2) extending RNS basis or changing RNS basis. In both applications, we assume |z|<M4|z|<\frac{M}{4} and compute qq by the above method. Since this qq is exact, we have z=∑i=1kαiMmi−qM. z = \sum_{i=1}^{k} \alpha_{i}\frac{M}{m_{i}} - qM. We can therefore perform the whole right-hand side modulo a target modulus, and directly obtain the residue of zz under that modulus.

For the first application, extracting low ℓ\ell bits means computing zmod⁡2ℓz\bmod 2^{\ell}. We have zmod⁡2ℓ=(∑i=1kαi(Mmimod⁡2ℓ)−q(Mmod⁡2ℓ))mod⁡2ℓ. z\bmod 2^{\ell} = \left( \sum_{i=1}^{k} \alpha_{i}\left(\frac{M}{m_{i}}\bmod 2^{\ell}\right) -q\left(M\bmod 2^{\ell}\right) \right)\bmod 2^{\ell}. Here Mmimod⁡2ℓ\frac{M}{m_{i}}\bmod 2^{\ell} and Mmod⁡2ℓM\bmod 2^{\ell} can all be precomputed. During the computation, each multiplication and addition only needs to retain the low ℓ\ell bits. Thus, after computing αi\alpha_{i}’s and qq, we can directly combine them to obtain the desired low bits. For negative zz, the nonnegative residue zmod⁡2ℓz\bmod 2^{\ell} gives the low ℓ\ell bits of its two’s-complement representation.

For the second application, let njn_{j}, (1≤j≤h)(1\leq j\leq h), be pairwise coprime odd moduli forming the new RNS basis. We can compute each new signed residue by zj′:=zmod⁡±nj=(∑i=1kαi(Mmimod⁡±nj)−q(Mmod⁡±nj))mod⁡±nj. z'_{j} := z\bmod^{\pm}n_{j} = \left( \sum_{i=1}^{k} \alpha_{i}\left(\frac{M}{m_{i}}\bmod^{\pm}n_{j}\right) -q\left(M\bmod^{\pm}n_{j}\right) \right)\bmod^{\pm}n_{j}. Again, all Mmimod⁡±nj\frac{M}{m_{i}}\bmod^{\pm}n_{j} and Mmod⁡±njM\bmod^{\pm}n_{j} can be precomputed, and the same αi\alpha_{i}’s and qq are used for every jj. Keeping the original residues together with additional residues whose moduli are coprime to MM extends the RNS basis; replacing the original representation by (z1′,…,zh′)(z'_{1},\ldots,z'_{h}) changes the RNS basis. In either case, we do not need to first recover the full big integer zz.

If the new basis is to determine the same signed integer zz uniquely, we also need |z|<N2|z|<\frac{N}{2}, where N=∏j=1hnjN=\prod_{j=1}^{h}n_{j}. The same error analysis for computing the correction multiple in the new basis applies when |z|<N4|z|<\frac{N}{4}.

References

  1. 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.