Efficient elliptic curve arithmetic is crucial for cryptosystems based on elliptic curves. Such cryptosystems often require computing a scalar multiple kP of a base point P. Recently, some papers propose efficient algorithms to compute λP ± μQ directly for small integers A and μ from given points P and Q. We develop some programs to find the path with the minimum cost for each scalar multiplication kP under the condition that several operations of λP ± μQ can be used with relatively small costs. We have construct the minimum-cost path table in which the maximum number of k (k_(max)) is around 10~5 (2~(18)). We also show some algorithms to compute KP where k_(max) K.%楕円曲線暗号では楕円曲線上のスカラー倍算の効率化が重要な課題となっている.これまでに有理点P，Qに対してP＋Qおよび2Pの演算を基本に加算連鎖を導く幾つかの方法が研究されている.一方で，最近，比較的小さい整数入とμに対して，λP±μQを効率的に計算する方法が，Cietらや溝添らによって発表されている.本研究では，複数の基本演算が利用できる場合に，それぞれのコストを考慮した上で，任意の整数kに対してkPを最小のコストあるいはそれに近いコストで計算する加算連鎖を求める.最小コストの加算連鎖を探索するため，加算連鎖の木を生成する複数のプログラムを開発し，それらの結果をマージして，10~5（2~(18)）程度までの最小コストのスカラー倍算kPの加算連鎖パステーブルを作成した.また，最小コストとた値との関係について考察する.さらに，パステーブルで与えられる最大の整数k_(max)に対してk_(max)≪Kとなるようなスカラ一倍算KPの求め方を差分あるいは高階差分の考え方を利用して検討する.
展开▼
