楕円曲線暗号のための数学2（バイナリ法によるスカラー倍算）

初めに 前回、楕円曲線暗号に必要な楕円曲線の点の加算を高速化するために射影座標を導入しました。 今回は楕円曲線の点の整数倍を計算する方法を紹介します。 スカラー倍算の定義 楕円曲線の点 P をとり、 n 個の和 P+P\cdots + P を nP と書きます。 楕円曲線の点の集合は加法群で、結合則が成り立つのでこの表記が使えます。 n が負のときは -((-n)P) とすることで、一般に点 P の整数 n 倍 nP を計算できます。 この操作をスカラー倍算と呼びます。 ECDH鍵共有や楕円ElGamal暗号などで必須の演算です。 バイナリ法 以降、プログラムの中では楕円曲線の点のクラスを Ec, 点 P, Q の和を add(P, Q), 点 P の2倍を dbl(P) と書くことにします。 単に n 個足せばよいのだから（以下簡単にするため n > 0 とします）、 def mul(P