Canonical Embedding

松岡　航太郎

Canonical Embeddingとは

  • Embeddingは日本語で言えば埋め込みでwikiによると数学的構造間の構造を保つような単射のことらしい
  • ここで扱うのはBGVやCKKSで出てくるXN+1X^N+1の零点に値を埋め込むこと
  • TRLWEでは係数に値を入れていたので違う
  • どうやって埋め込むかを考えてそれからその特性を見る

多項式の補間

  • まずNN個の点{(x0,y0),(x1,y1),...,(xN−1,yN−1)}\{(x_0,y_0),(x_1,y_1),...,(x_{N-1},y_{N-1})\}をN−1N-1次の多項式で補間することを考えよう
  • つまりある多項式ppがあって、∀i∈[0,N),p(xi)=yi∀i∈[0,N),p(x_i)=y_iとなるppをつくる
  • そのためには以下の性質を満たすNN個の多項式gig_iを構成すれば良い

gi(xj)={1ifi==j0otherwiseg_i(x_j)=\begin{cases}1\qquad if\quad i==j\\ 0\qquad otherwise\end{cases}

  • これがあれば明らかにp=∑i=0N−1yigip=∑_{i=0}^{N-1}y_ig_iでよい
  • h(x)=∏i=0N−1(x−xi),hi=h(x)(x−xi),gi(x)=hi(x)hi(xi)h(x)=∏_{i=0}^{N-1}(x-x_i),h_i=\frac{h(x)}{(x-x_i)},g_i(x) = \frac{h_i(x)}{h_i(x_i)}

剰余環との関係

  • 実はこの多項式の補間が剰余環と対応していることを見よう
  • x≡xi mod x−xix≡x_i \bmod{x-x_i}なのでx−xix-x_iによる剰余はxxにxix_iを代入する
  • ∴p(x)≡yi mod x−xi∴p(x)≡ y_i \bmod{x-x_i}
  • 多項式補間がある種の中国剰余定理になっていることがわかる
  • q(x)≡zi mod x−xiq(x)≡z_i \bmod{x-x_i}となる多項式を考えよう
  • p(x)+q(x)≡yi+zi mod x−xi,p(x)q(x)≡yizi mod x−xip(x)+q(x)≡y_i+z_i \bmod{x-x_i},p(x)q(x)≡y_iz_i \bmod{x-x_i}
  • 乗算に関してもSIMDっぽい並列計算ができる

参考文献

page_number: true