Pebble Coding

ソフトウェアエンジニアによるIT関連技術や数学の備忘録

SEAアルゴリズムで使う漸化式を導く

Elliptic Curves in Cryptography の VII.23の等式から、VII.24の漸化式を導く計算

証明すべき等式は以下です。
 \sum_{i=0}^{d} \sum_{k=0}^{i} \sum_{j=0}^{k} \binom {d-i+k} {j} [ C(w)^{j} ]_{k-j} F_{l, d-i+k} w^{i} = \sum_{i=0}^{d} [ A(w) ]_{i} w^{i}
ここからVII.24が得られます。
使う材料は以下です。
 w^{d} F_l(p(z)) = A(w) = \sum_{i=0}^{d} A(w)_{i} w^{i} (式A)
 d = \frac {l-1} {2}
 w = z^{2}
 F_l(x) = \sum_{i=0}^{d} F_{l, i} x^{i}
 F_{l, d} = 1
 p(z) = \frac {1} {z^{2}} + \sum_{k=1}^{\infty} c_k z^{2k} = w^{-1} + \sum_{k=1}^{\infty} c_k w^{k}
 C(w) = p(w) - w^{-1}

最初の等式の両辺のwの0乗からd乗までの多項式を計算し、係数を等しいと置くことがこれからやることです。
計算の途中で O(w^{d+1})の項が出てきますが寄与しないので捨てます。

まず、
 \sum_{k=0}^{i} \sum_{j=0}^{k} f_{i, k, j} w^{d-i+k+j} = \sum_{k=0}^{i} w^{d-i+k} \sum_{j=0}^{k} f_{i, k, k-j} + O(w^{d+1})
が成り立ちます。
 f_{i, k, j}は任意の添字付き係数です。

次に、
 \sum_{i=0}^{d} \sum_{k=0}^{i} w^{d-i+k} g_{i, k} = \sum_{i=0}^{d} w^{d-i} \sum_{k=0}^{d-i} g_{i+k, k}
が成り立ちます。
 g_{i, k}は任意の添字付き係数です。

2つを組み合わせると、
 \sum_{i=0}^{d} \sum_{k=0}^{i} \sum_{j=0}^{k} f_{i, k, j} w^{d-i+k+j} = \sum_{i=0}^{d} w^{d-i} \sum_{k=0}^{d-i} \sum_{j=0}^{k} f_{i+k, j, k-j} (式B)
が成り立ちます。ここで O(w^{d+1})の項は省略しました。

(式A)の左辺を計算していきます。
 w^{d} \sum_{i=0}^{d} F_{l, i} p^{i}
 = w^{d} \sum_{i=0}^{d} F_{l, i} (w^{-1} + C(w))^{i}
 = \sum_{i=0}^{d} F_{l, i} w^{d} \sum_{k=0}^{i} C(w)^{k} w^{-(i-k)} \binom {i} {k}
 = \sum_{i=0}^{d} F_{l, i} \sum_{k=0}^{i} w^{d-i+k} \binom {i} {k}  C(w)^{k}
 = \sum_{i=0}^{d} F_{l, i} \sum_{k=0}^{i} w^{d-i+k} \binom {i} {k} \sum_{j=0}^{k} [C(w)^{k}]_{j} w^{j}
 =  \sum_{i=0}^{d} \sum_{k=0}^{i} \sum_{j=0}^{k}  F_{l, i} \binom {i} {k}  [C(w)^{k}]_{j} w^{d-i+k + j}

式(B)を使うと、
 = \sum_{i=0}^{d} \sum_{k=0}^{d-i}  \sum_{j=0}^{k}  w^{d-i} F_{l, i+k}  \binom {i+k} {j} [C(w)^{j}]_{k-j}
iの和を反転させると、
 =  \sum_{i=0}^{d} \sum_{k=0}^{i}  \sum_{j=0}^{k}  w^{i} F_{l, d-i+k}  \binom {d-i+k} {j} [C(w)^{j}]_{k-j}

以上です。

プライバシーポリシー

お問い合わせ

スポンサーリンク