Miyaji Laboratory

A scalar value k is used as the secret key on a Elliptic Curve Cryptosystem. We compute kP = P+P+P+...+P in which P is a point on a Elliptic Curve. In order to improve the speed of the calculation, it is important to reduce the complexity of the computation down to polynomial time.

The binary method is a basic algorithm to compute a scalar multiplication in polynomial time. It expands a scalar k into binary bits. We operate additions as many times as the number of 1on a binary sequence.
Furthermore, we research methods to reduce the number of operations on a Elliptic Curve Cryptosystem. One of the methods is that expands a scalar value k into a sum of products composed of 2's exponation and 3's exponation.