Elliptic curve point multiplication computes a new curve point by repeatedly adding a point P to itself. For an integer scalar k, Q = kP means P added k times. This operation is central to elliptic-curve cryptography: large scalar multiplications create public keys and shared secrets without exposing the scalar. section 3.1.4 section 4.1.1
Directly performing k additions is impractical for large k. Double-and-add reads the scalar from its most significant bit downward. Start with R = P; for each remaining bit, double R, then add P when that bit is 1. Doubling corresponds to multiplying the accumulated point by 2, so the loop builds the scalar's binary value one bit at a time. section 3.1.4 section 3.2.3
Figure 3.5 Double and add method
The flow diagram captures the repeated doubling step and the conditional addition used while scanning scalar bits. section 3.1.4
Implementation loop
A routine initializes R as P, finds the binary length of k, and skips the already-handled most significant bit. Each loop iteration calls the point-addition routine with R and R to double. A bit test determines whether a second call adds the original P. Finally, R is copied to the output and temporary point storage is cleared. GMP's mpz_sizeinbase() counts bits and mpz_tstbit() reads an individual bit. section 3.2.3
Point multiplication depends on group behavior that gives scalars cryptographic meaning:
- The point at infinity is the identity element, so adding it leaves a point unchanged; implementations must handle it as both an input and output case. section 3.6
- A point's order is the number m for which mP reaches the point at infinity. Points of order c form the c-torsion subgroup. section 3.1.4
- Cryptographic use seeks a large prime order, because points whose order includes extra small factors are not useful for the stated security goal. section 3.1.4
The conditional add in ordinary double-and-add can reveal scalar-bit information when power consumption distinguishes doubling from addition. A slower standard-form approach is identified as more suitable for embedded systems facing side-channel attacks. Reusing the point-addition routine for both doubling and addition also keeps the multiplication implementation structurally simple. section 3.1.4 section 3.6
In Diffie-Hellman key exchange, a participant computes a public point A = kA G from private scalar kA and public base point G. The shared point follows from multiplying the other party's public point by the local private scalar: kA B = kB A. Schnorr signatures likewise use scalar multiplication for public keys and for the fresh point Q = kB. section 4.1.1 section 4.1.4 section 5.1.1
