Pebble Coding

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

Velu's Formula の証明の一部

Velu's Formulaの証明の最後の部分で悩んでいたのですが、解決したのでメモしておきます。

https://eprint.iacr.org/2011/430.pdf

こちらの説明でeasyだって書いてあり、数学者のeasyはちょっと計算をすればという意味なので、
ちょっとした計算って何だろうと考えたところ、思いつきました。
数学者がclear, obvious, trivialというときは本当に明らかなのですが、easyは信用してはいけません。

Cは楕円曲線Eの部分群です。
部分群に入っていない点 P(x_P, y_P)を楕円曲線E'に写すisogeny写像を \phiとします。
 P \notin C
isogeny写像なので、 Q \in Cに対しては、 \phi(Q) = \inftyです。

 \phi(P) = (x_{P} + \sum_{\infty \ne Q \in C} (x_{P+Q} - x_Q), y_{P} + \sum_{\infty \ne Q \in C} (y_{P+Q} - y_{Q}))
これがisogeny写像であることを示します。
部分群Cの任意の無限遠点でない点 Q_A \ne \inftyを使って、
 \phi(P-Q_A) = \phi(P)であることを示します。
x, yどちらも同じなので、xの方だけ考えます。
 \phi_x(P-Q_A) = x_{P-Q_A} + (x_{P-Q_A+Q_1} + ... + x_{P-Q_A+Q_A} + ... + x_{P-Q_A+Q_{LAST}}) - \sum_{\infty \ne Q \in C} x_Q
1項目と和の中の一つを入れ替えます。
 = x_{P-Q_A+Q_A} + (x_{P-Q_A+Q_1} + ... + x_{P-Q_A} + ... + x_{P-Q_A+Q_{LAST}}) - \sum_{\infty \ne Q\in C} x_Q
和の部分は
 Q_1 - Q_A, Q_2 - Q_A, ..., O - Q_A, ..., Q_{LAST} - Q_A Q'に置き換えられることが分かります。
 Q_A \ne \inftyとしているのとCが群なので、どの要素も \inftyにならない。
したがって、
 = x_{P} + \sum_{\infty \ne Q'\in C} x_{P + Q'} - \sum_{\infty \ne Q \in C} x_Q = \phi(P)
つまり、
 \phi(P-Q_A) = \phi(P)
が言えました。

残りの証明はこちらにあります。

Elliptic Curves: Number Theory and Cryptography, Second Edition (Discrete Mathematics and Its Applications)

Elliptic Curves: Number Theory and Cryptography, Second Edition (Discrete Mathematics and Its Applications)

  • 作者:Lawrence C. Washington
  • 出版社/メーカー: Chapman and Hall/CRC
  • 発売日: 2008/04/07
  • メディア: ハードカバー

補足

どうでもいいんですが、Exercise 12.6 の(b)の式の一部は分母の冪乗が間違っていますのでご注意。