# Decomposition and Approximate Decomposition
In TFHE, you constantly run into this situation:
* You have a value that is **large** (close to the ciphertext modulus `q`)
* If you multiply it directly into a ciphertext, the **noise explodes**
* So instead you **break the large value into small “digits”**, do safe operations with those small digits, and then recombine the result
That “break into digits” step is called **decomposition**. And doing it only up to some precision (ignoring some least-significant bits) is called **approximate decomposition**.
***
## 1) What is decomposition?
### The goal
Take a large value $$\gamma \in \mathbb{Z}\_q$$ and write it as a sum of **small digits** times **known scale factors**:
$$\gamma = \gamma\_1 \frac{q}{\beta^1} + \gamma\_2 \frac{q}{\beta^2} + \cdots + \gamma\_\ell \frac{q}{\beta^\ell}$$
* $$\beta$$ is a **small base** (often a power of 2)
* $$\ell$$ is the **number of levels**
* each digit $$\gamma\_j$$ is **small**, typically $$\gamma\_j \in \mathbb{Z}\_\beta$$
We denote this operation as:
$$\mathsf{Decomp}^{\beta,\ell}(\gamma) = (\gamma\_1,\ldots,\gamma\_\ell)$$
### Why this is useful
If $$\gamma\_j$$ are small, then multiplying a ciphertext by $$\gamma\_j$$ has a **small impact on noise**.
So decomposition turns “multiply by a huge number” into:
* “multiply by a few tiny digits”
* then “add the results”
That’s exactly the trick used to enable homomorphic multiplication by large constants (and later, key switching and external products).
***
## 2) How to think about the scale factors $$q/\beta^j$$
The special terms:
$$\frac{q}{\beta^1},\frac{q}{\beta^2},\ldots,\frac{q}{\beta^\ell}$$
are not random. They are chosen because TFHE also defines ciphertext structures (like **GLev**) that naturally contain encryptions of a message scaled by these exact factors.
So decomposition is designed to “match” later recomposition steps.
***
## 3) “Exact” decomposition
### Full precision condition
When you decompose with **full precision**, you choose parameters so that:
$$\beta^\ell = q$$
That means the decomposition can represent every element of $$\mathbb{Z}\_q$$ with no loss.
### Practical note about powers of 2
For simplicity (and often in practice), TFHE chooses `q` and `β` as powers of 2. If they are not, you apply rounding in the right places.
***
## 4) Toy example: what decomposition “looks like”
Let:
* $$q = 64$$
* $$\beta = 4$$
* $$\ell = 3$$
Then:
* $$q/\beta^1 = 64/4 = 16$$
* $$q/\beta^2 = 64/16 = 4$$
* $$q/\beta^3 = 64/64 = 1$$
Any $$\gamma \in {0,\ldots,63}$$ can be written as:
$$\gamma = \gamma\_1\cdot16 + \gamma\_2\cdot4 + \gamma\_3\cdot1 \quad\text{with}\quad \gamma\_j \in {0,1,2,3}$$
Example: $$\gamma = 45$$
* $$45 = 2\cdot16 + 3\cdot4 + 1\cdot1$$
| Step | Denomination | How many fit? | Digit | Remaining Value |
| ---- | ------------ | ----------------------------- | ----------------- | ---------------- |
| 1 | **16** | $$16 \times \mathbf{2} = 32$$ | $$\gamma\_1 = 2$$ | $$45 - 32 = 13$$ |
| 2 | **4** | $$4 \times \mathbf{3} = 12$$ | $$\gamma\_2 = 3$$ | $$13 - 12 = 1$$ |
| 3 | **1** | $$1 \times \mathbf{1} = 1$$ | $$\gamma\_3 = 1$$ | $$1 - 1 = 0$$ |
**Result:** $$\mathsf{Decomp}^{4,3}(45) = (2, 3, 1)$$
**Key point:** Instead of multiplying the noise by **45**, we multiply it by **2**, then **3**, then **1**, and add them up. The noise stays "quiet."
## Suppose we have a polynomial:
$$a(X) = 45X^2 + 18X + 7$$
### Step-by-Step "Coefficient-Wise" Decomposition:
We decompose each coefficient individually using our base-4 logic:
1. **For** $$45$$ **(the** $$X^2$$**term):** $$45 = \mathbf{2} \cdot 16 + \mathbf{3} \cdot 4 + \mathbf{1} \cdot 1$$
2. **For** $$18$$ (the $$X$$ term): $$18 = \mathbf{1} \cdot 16 + \mathbf{0} \cdot 4 + \mathbf{2} \cdot 1$$
3. **For** $$7$$ (the constant term): $$7 = \mathbf{0} \cdot 16 + \mathbf{1} \cdot 4 + \mathbf{3} \cdot 1$$
### Reassembling into Small Polynomials:
Now, we group the digits by their scale factors:
* $$a\_1(X)$$ (The 16s): $$2X^2 + 1X + 0$$
* $$a\_2(X)$$ (The 4s): $$3X^2 + 0X + 1$$
* $$a\_3(X)$$ (The 1s): $$1X^2 + 2X + 3$$
So, our original "large" polynomial $$a(X)$$ is now: $$a(X) = a\_1(X) \cdot 16 + a\_2(X) \cdot 4 + a\_3(X) \cdot 1$$
***
## 5) Approximate decomposition (the “precision trade-off”)
### Why approximate decomposition exists
Full precision isn’t always necessary.
Instead of $$\beta^\ell = q$$, you can choose:
$$\beta^\ell < q$$
This means you decompose only the **most significant** part of the number and ignore some least significant bits (LSBs).
### What changes in practice
> you do a rounding in the LSB part before decomposing. If parameters are chosen properly, this doesn’t affect correctness because the LSB part always contains noise, and the information we care about (the message) is in the MSB part.
So approximate decomposition is basically:
1. **Round away** (discard) some LSB precision
2. Decompose what’s left into digits $$(\gamma\_1,\ldots,\gamma\_\ell)$$
### Why this is safe
If your encoding puts the message in the MSB and noise lives in the LSB:
* losing some LSB precision is usually fine, because those bits were “fuzzy” anyway
### Why this is useful
Approximate decomposition is “very convenient” in some homomorphic operations defined later in the series (because it can reduce cost and keep noise under better control).
***
## 6) What decomposition outputs (and what to watch out for)
### Output is a vector of digits
$$(\gamma\_1,\ldots,\gamma\_\ell)$$ Digits are small, so later operations that multiply by digits stay manageable.
### But decomposition depends on your parameter choices
* `β` too small → more levels needed (bigger $$\ell$$)
* `β` too large → digits are less “small” (noise impact increases)
* approximate decomposition chooses $$\ell$$ smaller than full precision (faster) but loses some accuracy
***
## 7) ELI5 summary
* You have a huge number $$\gamma$$.
* Instead of using it directly, you rewrite it like: “a few tiny digits × big place values”
* Those tiny digits are safe to use in homomorphic computations.
* Approximate decomposition is the same, except you ignore some messy lowest bits first (because they’re noisy anyway).
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://sabanaku77.gitbook.io/fhe-handbook-for-beginners/decomposition-and-approximate-decomposition.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.