# How does batching in FHE work?

Let's say we have a BGV style homomorphic encryption scheme. The message space will be the ring $$R_p = \mathbb Z_p[x]/(x^d + 1)$$ where $$p$$ is a prime congruent to $$1$$ modulo $$2d$$. Now let's say we say messages $$m_1(x), m_2(x) \in R_p.$$ How do we obtain a ciphertext encrypting both $$m_1(x)$$ and $$m_2(x)$$? The BGV paper mentions the CRT isomorphism $$R_p \cong R_{\mathscr{p_1}} \times ... \times R_{\mathscr{p_d}}.$$ Under this isomorphism, we have the mapping $$m_1(x) \to ((m_{1,1})(x),...,(m_{1,d})(x))$$ and we have a similar representation for $$m_2(x)$$. I'm still not sure how we use this mapping to get a ciphertext encrypting both $$m_1(x)$$ and $$m_2(x)$$ at the same time however.

Any clarification would be greatly appreciated.

Your isomorphism implies that you are factoring the prime $$p$$ into several primes $$p_1,...p_d$$, but of course, what you actually factor is the cyclotomic polynomial modulo $$p$$, i.e., $$x^d + 1 = f_1(x) \cdot ... \cdot f_u(x) \pmod p$$. Because of the properties of the cyclotomic polynomial, every $$f_i$$ has the same degree $$o$$, which is actually equal to the order of $$p$$ in $$\mathbb{Z}_{2d}^*$$. And then, the number of slots is $$u = d / o$$.
So, you cannot encrypt two polynomials of degree $$d$$ into a single ciphertext. What you can do is to choose $$u$$ polynomials $$m_1,...,m_u$$ of degree up to $$o-1$$, then "pack" them with CRT, obtaining $$m \in R_p$$, and finally encrypt $$m$$.