baby-step_giant-stepアルゴリズム

baby-step giant-step

• $p(t)={\sum }_{i=0}^d{c}_i{T}_i(t)$ を評価するアルゴリズム.

• bootstrappingでの暗号文同士の乗算数を最小化するためのアルゴリズム

• $d$ 次元多項式 $p(t)$, $m:=\lceil \log (d+1)\rceil$, $I:=\lfloor \frac{m}{2}\rfloor$

• まず, $p(t)$ を ${\sum }_{i=0}^{\lfloor d/I\rfloor }{u}_{i,2^I}(t)\cdot T_{2^{i\cdot I}}(t)$

  • ($u_{i,2^I}(t)={\sum }_{j=0}^{2^I-1}{c}_{i,j}\cdot T_j(t)$) $c_{i,j}\in \mathbb{C}$
  • $T_{0\le j<2^I}$ は事前に計算するpowerの基底
  • $u_{\lfloor d/l\rfloor ,2^I}(t)$ を $u_{\max }$

• BSGSアルゴリズムは単項式 $u_{i,2^{j+1}}(t)=u_{i+1,2^j}(t)\cdot T_{2^j}(t)+u_{i,2^j}(t)$ を木のように再帰的に結合する

• $T_{2^{I\le i<m}}(t)$ はスカラでない乗算を最小化するための基底で事前に計算する.

• 深さ $m$ に対して, $2^{m-l}+2^l+m-l-3+\lceil (d+1)/2^l\rfloor$ の乗算を必要とする

• 例 $p(t)=1+2t+5t^2,t=3$ を計算する

  • $d=2,m=2,I=1$
  • $T_0(t)=1,T_1(t)=t$
  • $T_2(t)=T_{1+1}(t)=2\cdot T_1(t)\cdot T_1(t)-T_{|1-1|}(t)=2t^2-1=17$
  • $p(t)=q(t)\cdot T_{2^{m-1}}+r(t)$
  • $q(3)=\frac{5}{2},r(t)=(2t+\frac{7}{2})=\frac{19}{2}$
  • $p(3)=52$

• 平方分割らしい