Pebble Coding

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

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

Schoofアルゴリズム

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}は任意の添字付き係数です。

２つを組み合わせると、
\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}

以上です。