以下ではまた $M$ を正整数（ePrintでは $M \in \mathbb{Z}$ となっていますが・・・）として， $p(X)$ を円分多項式で $p(X) q(X) = X^M - 1$ を満たす $q(X)$ が存在するような $p(X)$ を考えます．
このとき，本来 $(\mathbb{Z} / q \mathbb{Z})[X] / (p(X))$ で考えている演算は $(\mathbb{Z} / q \mathbb{Z})[X] / (X^M - 1))$ で考えてから，その結果を $(\mathbb{Z} / q \mathbb{Z})[X] / (p(X))$ に帰着させることができます（広い空間から狭い空間にしている）．
すると， $(\mathbb{Z} / q \mathbb{Z})[X] / (p(X))$ や $(\mathbb{Z} / q \mathbb{Z})[X] / (X^M - 1))$ は環なので，その中での足し算や掛け算は特に問題なさそうに思えます．
問題になりそうなのが，非線型な演算で，bootstrap では，四捨五入などの操作（Decrypt）を行います．
そしてもう１つの問題があり，それは， $(\mathbb{Z} / q \mathbb{Z})[X] / (X^M - 1)$ 　で考えていたものを $(\mathbb{Z} / q \mathbb{Z})[X] / (p(X)))$ で考えるため，多項式の各係数が大きくなる可能性があります．
＊前者から後者になると，多項式の次数が小さくなるためその分が係数に影響します

上記２つの問題を次の章で上手く解消することを試みます．

6 Noise Growth

＊非線型な演算の方は APPENDIX A に記載されているのですが，よく分からなかったので飛ばします・・・

$f \in (\mathbb{Z} / q \mathbb{Z})[X] / (X^M - 1)$ に対して， $f = \sum_{i = 0}^{M - 1} f_i X^i$ とします．

まず， $M = 3^{\beta}$ の場合を考えます．このとき， $N = 2 \cdot 3^{\beta - 1}$ で， $p(X) = X^N + X^{N / 2} + 1$ となります．
そして， $f$ を変形した $f^{\prime} \in (\mathbb{Z} / q \mathbb{Z})[X] / (p(X)))$ の係数がどうなるかを考察します．これは

\begin{align*} f(X) & = \sum_{i = 0}^{M - 1} f_i X^i \\ & = \sum_{i = 0}^{3 N / 2 - 1} f_i X^i \\ & = \sum_{i = 0}^{N - 1} f_i X^i + \sum_{i = N}^{3 N / 2 - 1} f_i X^i \\ & = \sum_{i = 0}^{N - 1} f_i X^i + \sum_{i = 0}^{N/ 2 - 1} f_{i + N} X^{i + N} \\ & = \sum_{i = 0}^{N - 1} f_i X^i + \sum_{i = 0}^{N/ 2 - 1} f_{i + N} X^{i} \cdot (- X^{N / 2} - 1) \\ & = \sum_{i = 0}^{N - 1} f_i X^i - \sum_{i = 0}^{N/ 2 - 1} f_{i + N} X^{i + N / 2} -\sum_{i = 0}^{N/ 2 - 1} f_{i + N} X^{i} \\ & = \sum_{i = 0}^{N - 1} f_i X^i - \sum_{i = N / 2}^{N - 1} f_{i + N / 2} X^{i} -\sum_{i = 0}^{N/ 2 - 1} f_{i + N} X^{i} \\ & = \sum_{i = 0}^{N / 2 - 1} (f_i - f_{i + N}) X^i + \sum_{i = N / 2}^{N - 1} (f_i - f_{i + N / 2}) X^{i} \\ \end{align*}

となりますので，係数のサイズは高々２倍になることがわかります．

また， $M = 2^{\alpha} \cdot 3^{\beta}$ の場合， $N = 2^{\alpha} \cdot 3^{\beta - 1}$ で， $p(X) = X^N - X^{N / 2} + 1$ となります．
この場合も同様に計算できますが，結構めんどくさいので論文を参照してください・・・（やり方は上と同じです）

7 Example Parameters

次数が2べきとは限らない一般の円分多項式での議論をこれまでしてきましたが，その変更をすることでパラメタがどのように変わるのかをこの章では見ていきます．

気になるところとしては，多項式の掛け算でNTTを使っていた箇所についてになります．
ここでは $M$ が3べきの場合を考えます．

まず， $q$ が2べきのとき， $q$ と $M$ は互いに素ですから， $\mathbb{Z} / q \mathbb{Z}$ に1の原始 $M$ 乗根は存在しないため， $(\mathbb{Z} / q \mathbb{Z})[X] / (X^M - 1))$ の多項式の係数の掛け算にNTTを適用することはできません．
しかし，NTTが適用できないだけで，他の高速化の手法は採用でき，それが Schonhage の定理や Nussbanumer の定理と呼ばれるものらしいです．

1のM乗根が存在しない理由

$a$ が $\mathbb{Z} / q \mathbb{Z}$ の1の原始 $M$ 乗根とすると $a^M \equiv 1 \ (\mathrm{mod} \ q)$ が成り立ちます．また，Eulerの定理から $a^{\varphi(q)} \equiv 1 \ (\mathrm{mod} \ q)$ が成り立ち， $\varphi(q) = q / 2$ です．よって， $M$ が $q / 2$ ，つまり，2べきの約数である必要がありますが，これは $M$ と $q$ が互いに素である条件に矛盾します．
よってこのような $a$ は存在しません．

続いて， $q$ が素数の場合を考えます．また以下では $M = 3^7$ とします．
このとき次の条件を満たす $q$ を考えることになります:

$q$ は素数
$M \ | \ q - 1$ （Fermatの小定理）
$q$ は32bit or 64 bit程度 i.e. $2^{31} < q < 2^{32}$ or $2^{63} < q < 2^{64}$

ePrintではこれらを満たす $q$ の例が与えられています（探すの大変そう）

今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！

理論的によくわかっていない箇所があるので，そこを理解できたらリメイク記事を作りたいなぁ・・・

全４回通しでの目次

6章でやりたいこと

6 Noise Growth

7 Example Parameters

Discussion