A-6.3 Approximate Decomposition

PIC

Figure 2: An illustration of approximate decomposition

If the base β does not divide the modulo q, then there exists no level l such that βl | q, thus some lower bits of q have to be drawn away during decomposition, as shown in Figure 2. Such lower bits can be rounded to the nearest multiple of q βl during decomposition. In such a case, the decomposition is an approximate decomposition.