The double-and-add algorithm computes point multiplication Q = kP without adding P to itself k times. It scans the binary representation of k from the most significant bit: each bit position doubles the current point, then a set bit adds the original point. section 3.1.4
A typical implementation follows this execution flow:
- Initialize the running result R with P. section 13.2.6
- Determine the remaining bit positions of k and process them from high to low. section 3.1.4 section 13.2.6
- Double R using the point-addition routine, test the current bit, and add P when the bit is set. section 13.2.6
- Copy R to the destination and clear the local temporary point. section 13.2.6
Figure 3.5 Double and add method
Follow the bit-by-bit flow of the double-and-add method. section 3.1.4
The same addition routine handles both doubling and adding, while input and output checks account for the point at infinity. This uniformity improves resistance to power-consumption side-channel attacks on embedded systems, although it can be slightly slower. section 3.1.4 section 3.6
