vanilla encoding

decode (coeff -> slots)

• $\sigma :\mathbb{C}[X]/(X^{N+1}){\to }^{\mathrm{bi}}{\mathbb{C}}^N$
• $X^M+1$ の $N$個の根 $\zeta ,{\zeta }^3,\cdots {\zeta }^{2N-1}$ を多項式に代入する
  • $\sigma (m)=(m(\zeta ),m({\zeta }^3),\cdots ,m({\zeta }^{2N-1}))\in {\mathbb{C}}^N$

encode (slots -> coeff)

• 平文 $b\in {\mathbb{C}}^N$
• $\zeta =e^{\frac{\pi i}{N}}$
• vandermonde行列 $A_{i,j}={\zeta }^{(2i-1)(j-1)}\in {\mathbb{C}}^{N\times N}$
• $Ax=b$ を解く $Ax=b\iff x=U^{-1}b={\sigma }^{-1}(b)$

参考文献