Exact Fast Base Conversion: FastBConvEx

FastBConv (§D-5.1) converts an input value

x

’s base moduli from

q \to b

, but generates a noise equivalent to

𝑢𝑞 mod b

where integer

| u | \leq \frac{k}{2} + 1

. If we use FastBConv with SmallMont (§D-5.7), we can reduce the generated noise from

𝑢𝑞

u^{'} q

where

u^{'} \in {- 1, 0, 1}

. In this subsection, we introduce FastBConvEx, an algorithm for an exact fast base conversion that can eliminate the entire noise. However, using FastBConvEx has a restriction that the input value

x

should be relatively much smaller than its modulus. This is different from the case of using FastBConv with SmallMont which has no restriction on the input

x

(i.e.,

x

can be any value within its modulus range). FastBConvEx is designed as follows:

$⟨$ Summary D-5.8 $⟩$ Fast Exact Base Conversion: FastBConvEx

Input: $x = (x_{1}, x_{2}, \dots, x_{l}, x_{α}) \in ℤ_{b_{1}} \times ℤ_{b_{2}} \times \dots \times ℤ_{b_{l}} \times ℤ_{b_{α}}$

Requirement: The size of $b_{α}$ should be $b_{α} \geq 2 \cdot (l + λ)$ , where $| x |_{b} = x + μ \cdot b$ , and $μ \in [- λ, λ]$ (i.e., $λ$ and $- λ$ are the maximum and minimum possible values of $μ$ ).

# The constraint that $b_{α} > μ$ implies that the input $x$ should be much smaller than its modulus $b b_{α}$ (i.e., $| x | ≪ \frac{b b_{α}}{2}$ )

Main Steps

1.: $\hat{x} = | x |_{b} = 𝖬𝗈𝖽𝖣𝗋𝗈𝗉 (x, b b_{α}, b)$
2.: $x_{α} = | x |_{b_{α}} = 𝖬𝗈𝖽𝖣𝗋𝗈𝗉 (x, b b_{α}, b_{α})$
3.: $γ = | (𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 (\hat{x}, b, b_{α}) - x_{α}) \cdot b^{- 1} |_{b_{α}}$
4.: $𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏𝖤𝗑 (x, b b_{α}, q) = | 𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 (\hat{x}, b, q) - γ \cdot b |_{q} = | x |_{q}$

We will prove why

| 𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 (\hat{x}, b, q) - γ \cdot b |_{q} = | x |_{q}

Proof.

1.

𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 (\hat{x}, b, b_{α})

$= | \hat{x} + 𝑢𝑏 |_{b_{α}}$ # where integer $| u | \leq \frac{l}{2} + 1$

$= | | x |_{b} + 𝑢𝑏 |_{b_{α}}$ # since $| x |_{b} = \hat{x}$ by definition

$= | x + 𝜇𝑏 + 𝑢𝑏 |_{b_{α}}$ # since $| x |_{b} = x + 𝜇𝑏$ by definition

2.

γ = | (𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 (\hat{x}, b, b_{α}) - x_{α}) \cdot b^{- 1} |_{b_{α}}

$= | (𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 (\hat{x}, b, b_{α}) - x_{α} - 𝜇𝑏) \cdot b^{- 1} + μ |_{b_{α}}$ # by adding $| (- 𝜇𝑏 + 𝜇𝑏) \cdot b^{- 1} |_{b_{α}}$

$= | (x + 𝜇𝑏 + 𝑢𝑏 - x_{α} - 𝜇𝑏) \cdot b^{- 1} + μ |_{b_{α}}$ # step 1 proved $𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 (\hat{x}, b, b_{α}) = | x + 𝜇𝑏 + u \cdot b |_{b_{α}}$

$= | u + μ |_{b_{α}}$

$= u + μ$ # because $- \frac{b_{α}}{2} \leq u + μ \leq \frac{b_{α}}{2} - 1$ (since $u + μ < l + λ \leq \frac{b_{α}}{2}$ , and $- \frac{b_{α}}{2} \leq - (l + λ) < u + μ$ )

3.

𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏𝖤𝗑 (x, b, q) = | 𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 (\hat{x}, b, q) - γ \cdot b) |_{q}

$= | \hat{x} + 𝑢𝑏 - γ \cdot b) |_{q}$ # applying $𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 (\hat{x}, b, q) = \hat{x} + 𝑢𝑏$

$= | (x + 𝜇𝑏) + 𝑢𝑏 - γ \cdot b) |_{q}$ # applying $\hat{x} = | x |_{b} = x + 𝜇𝑏$

$= | (x + 𝜇𝑏) + 𝑢𝑏 - (u + μ) \cdot b) |_{q}$ # applying $γ = u + μ$ from proof step 2

$= | x + 𝜇𝑏 + 𝑢𝑏 - 𝑢𝑏 - 𝜇𝑏 |_{q}$

$= | x |_{q}$

□

Necessity of the Centered (i.e., Signed) Residue Representation: In the proof step 2, we treated

| u + μ |_{b_{α}} = u + μ

. To remove the modulo reduction operation, the canonical (i.e., unsigned) residue representation is inappropriate, because if

u + μ

becomes negative, then the residue will underflow and have to be wrapped around, which requires a modulo reduction operation. To prevent the occurrence of both overflow and underflow cases, we need the centered (i.e., signed) residue representation.

D-5.8 Exact Fast Base Conversion: FastBConvEx