Double and Add Method

Computing a new point on an elliptic curve Q = kP for given k and P could be performed by combination of point addition and point doubling. Thus, computation is performed by less than k steps. This approach is called as addition chains. Finding the optimum addition chain is NP-Complete problem.

In this post, we’ll mention the double and add method (a.k.a. binary method) and implement the concept in Java.

public static int multiplyScalarPoint(int k){

String kAsBinary = Integer.toBinaryString(k);

int step = 0;

//decimal to binary conversion
System.out.println("k = ("+k+")10 = ("+kAsBinary+")2\n");

int q = 1, p = 1;
int a = 0, b = 0;


for(int i=1;i<kAsBinary.length();i++){


int currentBit = Integer.parseInt(kAsBinary.substring(i, i+1));


q = q+q;
a = q;


if(currentBit == 1){


q = q + p;
b = q;



b = 0;



System.out.println("\nQ=kP is calculated in "+step+"th step");

return step;


scalar point multiplication

Suppose that k = 1017. Then, going to Q = 1017P is implemented rapidly by 16 steps as shown above. However, brute force attack has to be applied to calculate k for given points Q and P. This means k = 1017 steps required to implement the brute force attack for the worst case scenario. (a.k.a. Discrete Logarithm Problem for Elliptic Curves)

Let’s monitor the change of k over required steps for computing kP.

Change of k over required steps for computing kP (x-axis: k, y-axis: cost)

The figure illustrates the easiness of computing Q = kP for given k and P with binary method. Also, it shows the difficulty of computing k for given P and Q=kP with brute force method. Step(kP) remains stable while k increased dramatically. That is the power of the elliptic curve cryptography.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s