Double and Add Algorithm

아래 수식처럼 scalar multiplication을 하는 함수를 작성하는 가장 단순한 방법은 G를 k번 더하는 방법이다.

$k * G$

하지만 k를 2진수로 변환했을 때 1이 256bits만큼 있는 수라고 가정한다면 단순한 방법으로는 굉장히 오랜 시간 걸리는 문제가 존재한다.

이때 double and add 알고리즘을 사용하면 대략 512(256의 2배)번의 계산만으로 결괏값을 얻을 수 있다.

Double and Add Algorithm

사실 이전에 포스팅한 fast exponentiation algorithm을 조금 변형하면 scalar multiplication을 효율적으로 할 수 있다.

다만 double and add algorithm이 더욱 공간적으로 효율성이 있다.

$26 * G$

위 수식을 double and add 알고리즘을 통해 계산해보자.

Double and Add 알고리즘의 과정은 아래와 같다.

1. $26(11010_{2})$을 2진수로 변경한다.
2. MSB to LSB 흐름으로 bit를 조사한다.
   3-1. 만약 bit가 0이면 G를 2배한다. (Double Operation)
   3-2. 만약 bit가 1이면 G를 2배하고 G를 더해준다. (Double and Add Operation)

수식을 double and add 알고리즘을 통해 계산하는 과정은 아래와 같다.

1. bit1 (1): G (Initialize)
2. bit2 (1): G + G = 2G (Double)
   2G + G = 3G (Add)
3. bit3 (0): 3G + 3G = 6G (Double)
4. bit4 (1): 6G + 6G = 12G (Double)
   12G + G = 13G (Add)
5. bit5 (0): 13G + 13G = 26G (Double)