Scalar multiplication

When $G$ is a cyclic group of order $n$ and $g ∈ G$ is a generator of $G$, then there exists a so-called exponential map, which maps the additive group law of the remainder class group $(Z_n, +)$ onto the group law of $G$ in a one-to-one correspondence. The exponential map can be formalized as in below (where $g^x$ means “multiply $g$ by itself $x$ times” and $g^0 = e$):

$$g^{(·)} : Z_n → G ; x → g^x$$

To see how the exponential map works, first observe that, since $g^0 := e$ by definition, the neutral element of $Z_n$ is mapped to the neutral element of $G$. Furthermore, since $g^{x+y} = g^x · g^y$, the map respects the group law.

If a group $(G, +)$ is written in additive notation, then the exponential map is often called scalar multiplication, and written as follows:

$$(·) · g : Z_n → G ; x → x·g$$

In this notation, the symbol $x · g$ is defined as “add the generator $g$ to itself $x$ times” and the symbol $0 ·$g is defined to be the neutral element in $G$.

Cryptographic applications often utilize finite cyclic groups of a very large order $n$, which means that computing the scalar multiplication by repeated addition of the generator with itself is infeasible for very large remainder classes. Algorithm, called double and add, solves this problem by computing the scalar multiplication in approximately $k$ steps, where $k$ is the bit length of the scalar.

Sage example:

# finite field
F = GF("21888242871839275222246405745257275088696311157297823662689037894645226208583")
# finite cyclic group
E = EllipticCurve(F,[0,3])

def double_and_add(s, G):
    h = G
    y = E(0)
    while s != 0:
        b = s % 2
        s = s >> 1
        if b == 1:
            y = y + h
        h = 2 * h
    return y
    
s = F.random_element()
G = E.random_element()
print(Integer(s) * G)
print(double_and_add(Integer(s), G))