Fast Base Conversion: FastBConv

Suppose we have

x \in ℤ_{q}

(where

q

is a big modulus). Then, we can express

x

by using RNS (§A-13.1) as

(x_{1}, x_{2}, \dots, x_{k})

, where each

x_{i} \in ℤ_{q_{i}}

\prod_{i = 1}^{k} q_{i} = q

, and

{q_{1}, q_{2}, \dots, q_{k}}

are co-prime. In RNS, we define base conversion as an operation of converting the RNS residues

(x_{1}, x_{2}, \dots, x_{k}) \in ℤ_{q_{1}} \times ℤ_{q_{2}} \times \dots \times ℤ_{q_{k}}

into

(c_{1}, c_{2}, \dots, c_{k}) \in ℤ_{b_{1}} \times ℤ_{b_{2}} \times \dots \times ℤ_{b_{l}}

, where

{b_{1}, b_{2}, \dots, b_{l}}

are a new base, and

{q_{1}, q_{2}, \dots, q_{k}}

and

{b_{1}, b_{2}, \dots, b_{l}}

are all co-prime. The relationship between

x

and

c

is:

c = | x |_{b}

(where

x \in ℤ_{q}

and

c \in ℤ_{b}

). The standard way of performing base conversion is assembling

(x_{1}, x_{2}, \dots, x_{k})

into

x

by computing

x = \sum_{i = 1}^{k} | x_{i} z_{i} |_{q_{i}} \cdot y_{i} mod q

(where

y_{i} = \frac{q}{q_{i}} and z_{i} = y_{i}^{- 1} mod q_{i}

), and then computing

c_{j} \equiv x mod b_{j}

for

j \in [1, l]

. However, this computation is slow if the modulus

q

is large. To compute the base conversion fast, we design the fast base conversion operation

𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏

as follows:

$⟨$ Summary D-5.1 $⟩$ Fast Base Conversion: FastBConv

Input: $(x_{1}, x_{2}, \dots, x_{k}) \in ℤ_{q_{1}} \times ℤ_{q_{2}} \times \dots \times ℤ_{q_{k}}$ # which represents the big value $x \in ℤ_{q}$ , where $q = \prod_{i = 1}^{k} q_{i}$ , and ${q_{1}, q_{2}, \dots, q_{k}}$ are co-prime

$𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 (x, q, b) = 𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 ({x_{i}}_{i = 1}^{k}, {q_{i}}_{i = 1}^{k}, {b_{i}}_{i = 1}^{l})$

$= {(\sum_{i = 1}^{k} | x_{i} \cdot z_{i} |_{q_{i}} \cdot y_{i} mod b_{j})}_{j \in [1, l]}$

# where $y_{i} = \frac{q}{q_{i}}, z_{i} = y_{i}^{- 1} mod q_{i}$ , and $b = \prod_{i = 1}^{l} b_{i}$

$= (c_{1}, c_{2}, \dots, c_{l}) \in ℤ_{b_{1}} \times ℤ_{b_{2}} \times \dots \times ℤ_{b_{l}}$ # which represents the big value $c \in ℤ_{b}$

The input to this FastBConv function is a list of RNS residues $(x_{1}, x_{2}, \dots, x_{k})$ having the prime moduli $(q_{1}, q_{2}, \dots, q_{k})$ as the base. This RNS vector represents the big value:

$x = (\sum_{i = 1}^{k} x_{i} \cdot y_{i} \cdot z_{i}) mod q = (\sum_{i = 1}^{k} | x_{i} \cdot z_{i} |_{q_{i}} \cdot y_{i}) mod q$ # Theorem A-13.1

The output of this FastBConv function is a list of RNS residues $(c_{1}, c_{2}, \dots, c_{l})$ having the prime moduli $(b_{1}, b_{2}, \dots, b_{l})$ as the base. This RNS vector represents the big value

$c = (\sum_{i = 1}^{l} c_{i} \cdot y_{i}^{'} \cdot z_{i}^{'}) mod b = (\sum_{i = 1}^{l} | c_{i} \cdot z_{i}^{'} |_{b_{i}} \cdot y_{i}^{'}) mod b$ # where $y_{i}^{'} = \frac{b}{b_{i}}$ and $z_{i}^{'} = {y_{i}^{'}}^{- 1} mod b_{i}$

The relationship between $c$ and $x$ is as follows:

$c = x + 𝑢𝑞 mod b$ (where $u$ is an integer with the magnitude $| u | \leq \frac{k}{2} + 1$ )

# i.e. the fast-base-converted $c$ gets noise $| 𝑢𝑞 |_{b}$

Proof.

We will prove why a fast base conversion of $x$ into $c$ gets an additional noise $| u \cdot q |_{b}$ (where integer $| u | \leq \frac{k}{2} + 1$ ) compared to a standard base conversion. If we did a standard (i.e., exact) base conversion of $x$ from base moduli $(q_{1}, \dots, q_{k})$ to $(b_{1}, \dots, b_{l})$ , then we would compute the following:

{((\sum_{i = 1}^{k} | x_{i} \cdot z_{i} |_{q_{i}} \cdot y_{i} mod q) mod b_{j})}_{j \in [1, l]} = {(x mod b_{j})}_{j \in [1, l]}

But $𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏$ omits the intermediate (big) reduction modulo $q$ and directly applies (small) reduction modulo $b_{j}$ for the sake of fast computation, so that our conversion process does not need to handle large values whose magnitude can be as large as $\pm \frac{q}{2}$ . In this approach of fast base conversion, for each $i \in [1, k]$ , the computation result of $| x_{i} \cdot z_{i} |_{q_{i}} \cdot y_{i}$ is some value between $[- ⌈ \frac{q}{2} ⌉, ⌊ \frac{q}{2} ⌋]$ , because $| x_{i} \cdot z_{i} |_{q_{i}}$ is some integer between $[- ⌈ \frac{q_{i}}{2} ⌉, ⌊ \frac{q_{i}}{2} ⌋]$ and $y_{i} = \frac{q}{q_{i}}$ . Therefore, $- \frac{q + 1}{2} \leq | x_{i} \cdot z_{i} |_{q_{i}} \cdot y_{i} \leq \frac{q}{2}$ . If we sum $k$ such values for $i \in [1, k]$ , then the total sum $x^{'} = \sum_{i = 1}^{k} | x_{i} \cdot z_{i} |_{q_{i}} \cdot y_{i} = x + u \cdot q$ (Summary A-13 in §A-13) for some integer $u$ (where $u \cdot q$ represents the $q$ -multiple overflows). And since we have shown that $- \frac{q + 1}{2} \leq | x_{i} \cdot z_{i} |_{q_{i}} \cdot y_{i} \leq \frac{q}{2}$ for each $i \in [1, k]$ , $𝑢𝑞$ has to be greater than $- k \cdot \frac{q + 1}{2}$ and smaller than $k \cdot \frac{q}{2}$ (i.e., $u$ is an integer between $- \frac{k}{2} - 1 \leq u \leq \frac{k}{2}$ ). Therefore, $\sum_{i = 1}^{k} | x_{i} \cdot z_{i} |_{q_{i}} \cdot y_{i}$ can have maximum $- (\frac{k}{2} + 1) \cdot q$ underflows and $\frac{k}{2} \cdot q$ overflows. Thus, while standard (i.e., exact) base conversion computes each residue as ${\hat{c}}_{j} = (\sum_{i = 1}^{k} | x_{i} \cdot z_{i} |_{q_{i}} \cdot y_{i} mod q) mod b_{j}$ (i.e., ${\hat{c}}_{j} = x mod b_{j}$ ), fast (i.e., approximate) base conversion computes each residue as $c_{j} = (\sum_{i = 1}^{k} | x_{i} \cdot z_{i} |_{q_{i}} \cdot y_{i}) mod b_{j}$ (i.e., $c_{j} = x + 𝑢𝑞 mod b_{j}$ , where integer $| u | \leq \frac{k}{2} + 1$ ). Notice that the residual difference (i.e., error) between each ${\hat{c}}_{j}$ and $c_{j}$ is $𝑢𝑞 mod b_{j}$ , and the collective noise generated by fast base conversion from $q \to b$ is $𝑢𝑞 mod b$ . Also, note that the RNS residue vector $(c_{1}, c_{2}, \dots, c_{l}) \in ℤ_{b_{1}} \times ℤ_{b_{2}} \times \dots \times ℤ_{b_{l}}$ represents the big value $c = x + 𝑢𝑞 mod b$ .

Importantly, FastBConv does not guarantee the correctness of base conversion, because the $q$ -multiple overflow would generate a non-negligible error. Yet, FastBConv is used as an essential building block for various RNS-based operations such as ModRaise_RNS (§D-5.2) and ModSwitch_RNS (§D-5.4). □

D-5.1 Fast Base Conversion: FastBConv