その商の多項式がdenseかどうかに依存して（denseであるほどok），test polynomial や look-up table を構成することができます．
しかし，どの程度denseであればいいのかは論文中からは不明ですし，そもそも多項式がdenseであることの定義もよく分からないので，ここはスルーしてもいい気がします．

4.3 Sample Extraciton

（何をやりたいのかも全然分からないのでパスで・・・）

5章でやりたいこと

今まで触れてこなかったんですが，negacyclic という概念についてまず説明します．
$N$ を2べきとして，mod $X^N + 1$ で掛け算を行うことを negacyclic な多項式の積（negacyclic polynomial multiplication）と言います．なお，mod $X^N - 1$ で掛け算を行うことを cyclic な多項式の積（cyclic polynomial multiplication）と言います
これらは， $X^N$ を1とみなすか-1とみなすか，ということですが， $X^N + 1$ 内で考えると， $X^N$ が現れるたびに-1となるので，そのたびに符号が逆転します．一方で， $X^N - 1$ では， $X^N$ のたびに1が出てくるので，符号はそのままです．これが nega かどうかを表していると思えます

この概念を拡張して，PBS での look-up について思い出します．

＊上の写真はプログラマブルブートストラップの原著論文を理解する回　4/4「4.2の議論」

setup
$v_i \in \mathbb{Z} / q \mathbb{Z}$ に対して，look-up table の $i$ 番目の要素に $T[i]$ に対応づけることを考えます．過程として， $v_i$ は $2N$ 個しか値を取れないため $T$ の要素数も $2 N$ 個です．
上記の look-up という関数を構成するために，任意の定義域と値域 $\tilde{D}, \tilde{I}$ を考えて， $f$ を $\tilde{D}$ から $\tilde{I}$ への関数とします．

さて，要素が $2N$ 個の look-up table $T$ と $1 \leq i \leq N$ に対して， $T[i + N] = - T[i]$ なる look-up table を使った Blind Rotation のことを negacyclic rotation と言います
＊恐らくですが， $T[i + N] = T[i]$ なる look-up table を使った Blind Rotation を cyclic rotation と言うはず

そして，negacyclic rotation を構成するのに使われる $f$ を negacyclic function と言います
＊ですから，厳密には negacyclic function set という関数の集合があって，その要素を negacyclic function というのだと思います（上記の定義だと negacyclic function が曖昧なので）
＊cyclic rotation を構成するのに使われる $f$ を cyclic funtion と呼ぶことにします（cyclic function set とかを考えるのは同様）

本章では，negacyclic funtion（cyclic function）の中でも，4.3で出てきた trinomial に注目します

＊論文中の「PBS-friendly」は，一見すると章のタイトルで使われるぐらい重要な用語に見えますが，この章でしか使わないし，定義も曖昧なので，この記事内では使わないこととします
＊論文中の「function table」とは，恐らく look-up table のことですが，変えてもあれなので，この記事内では，look-up table と記載します

5.1 Negative Trinomials

$\alpha, \beta \geq 1$ で $M = 2^{\alpha} 3^{\beta}$ とし， $N = \frac{M}{3}$ とします
$X^N - X^{N / 2} + 1$ を $M$ 次の円分多項式としたとき，negative trinomial と呼ばれます
＊ $X^{3 N / 2} - 1$ を割り切るため

$\underline{\mathrm{Prop5}}$
$\alpha, \beta \geq 1$ で $M = 2^{\alpha} 3^{\beta}$ とし， $N = \frac{M}{3}$ とする．要素数が $M$ の look-up table $K$ が $K[0]$ から $K[N - 1]$ まで与えられていて，

\begin{align*} K[t] = \begin{cases} -K[t - N] + K[t - \frac{N}{2}] \hspace{10pt} & N \leq t < \frac{3 N}{2} \\ -K[t - \frac{3N}{2}] \hspace{10pt} & \frac{3 N}{2} \leq t < 2 N \\ -K[t - \frac{3N}{2}] \hspace{10pt} & 2 N \leq t < \frac{5 N}{2} \\ K[t - \frac{5N}{2}] - K[t - 2 N] \hspace{10pt} & \frac{5 N}{2} \leq t < 3 N \end{cases} \end{align*}

を満たす（ $1 \leq t \leq M$ に対して， $K[t]$ で $K$ の $t$ 番目の要素を表す）とする．つまり， $a = \{ K_i \ | \ 0 \leq i \leq \frac{N}{2} - 1 \}, b = \{ K_i \ | \ \frac{N}{2} \leq i \leq N - 1 \}$ として， $K = [a \ | \ b \ | \ b - a \ | \ - a \ | \ - b \ | \ a - b]$ と表されるとする．
このとき， $\Phi_M(X) = X^N - X^{N / 2} + 1$ として， $v(X) = \sum_{i = 0}^{N - 1} \in v_i X^i \in R[X] / (\Phi_M(X))$ 　とおくと，任意の $0 \leq t \leq N - 1$ に対して， $(X^{-t}v(X))_0 = K_t$ である．

p.f.) 地道に場合分けするだけなので略

5.2 Positive Trinomials

ここでは， $\beta \geq 1$ で $M = 3^{\beta}$ とし， $N = \frac{2 M}{3}$ とします
$X^N + X^{N / 2} + 1$ を $M$ 次の円分多項式としたとき，positive trinomial と呼ばれます
＊ $X^{3 N / 2} + 1$ を割り切るため

$\underline{\mathrm{Prop6}}$
$\beta \geq 1$ で $M = 3^{\beta}$ とし， $N = \frac{2 M}{3}$ とする．要素数が $M$ の look-up table $K$ が $K[0]$ から $K[N - 1]$ まで与えられていて， $N \leq t < \frac{3 N}{2}$ に対して， $K[t] = K[t - N] + k[t - N/2]$ を満たす（ $1 \leq t \leq M$ に対して， $K[t]$ で $K$ の $t$ 番目の要素を表す）とする．
つまり， $a = \{ K_i \ | \ 0 \leq i \leq \frac{N}{2} - 1 \}, b = \{ K_i \ | \ \frac{N}{2} \leq i \leq N - 1 \}$ として， $K = [a \ | \ b \ | \ a + b]$ と表されるとする．
このとき， $\Phi_M(X) = X^N + X^{N / 2} + 1$ として， $v(X) = \sum_{i = 0}^{N - 1} v_i X^i \in R[X] / (\Phi_M(X))$ 　とおくと，任意の $0 \leq t \leq N - 1$ に対して， $(X^{-t}v(X))_0 = K_t$ である．

p.f.) 地道に場合分けするだけなので略

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

いよいよ次回でこの Liberating TFHE の連載もラストです
その前にFFTやNTTに関する記事を独立で１本出したいと思います

全４回通しでの目次

4.2.4 Other polynomials

4.3 Sample Extraciton

5章でやりたいこと

5.1 Negative Trinomials

5.2 Positive Trinomials

Discussion