Scalar multiplication
Let $\mathbb{G}$ be a commutative group under the addition law ($+$) and let $G
\in \mathbb{G}$ be its generator. The group has an order $p$. We define a
scalar multiplication $k \cdot G$ as $\underbrace{G+…+G}_\text{$k$~times}$.
- Consider $105 \cdot G$. How many additions does it involve?
- Now consider the binary decomposition of $105 = 2^6 + 2^5 + 2^3 + 2^0$. It can be written as
$105 = ((((((((((1 · 2 + 1) · 2) + 0) · 2) + 1) · 2) + 0) · 2) + 0) · 2) + 1$.
Given that a doubling (multiplication by 2) has the same cost as an addition, how many additions $105 \cdot G$ involves?