# Elliptic Curve Scalar Multiplication ## Metadata **Status**:: #x **Zettel**:: #zettel/fleeting **Created**:: [[2024-03-30]] **Topic**:: [[♯ Cryptography]] ## Synopsis When s is an integer, and $G$ is a point in the [[Elliptic Curve]], the scalar multiplication $sG$ is defined as [[Elliptic Curve Addition|adding]] G to itself s times. $sG = \underbrace{G + G + \ldots + G}_{s}$ Rather than doing s additions, an algorithm to alternate addition and doubling can reduce to $\log(s)$ operations. ![[RareSkills Authors - Elliptic Curve Point Addition (Highlights)#^692194220]] A recursive implementation example in Python: ```python def scalar_mul(s, g): if s % 2 == 0: half = scalar_mul(s / 2, g) return half + half elif s == 1: return g else: return g + scalar_mul(s-1, g) ``` ## Cyclic Group For [[Elliptic Curve Over Finite Field]], $sG$ is a cyclic [[Group]]. The number of the points in the set $sG$ is the order of the point $G$. The special point at the infinity is always in the set, and $rG = \mathrm{Infinity}$ where r is the number of points in $sG$. If [[Elliptic Curve Paring]] is defined, $sG$ is a field which can be called [[Elliptic Curve Scalar Field]]. Attention that number of points in $sG$, number of points in the curve, and the modulus used to define the curve are three [[Different Orders in Elliptic Curve|different numbers]]. Since $sG$ is a cyclic group, the operation can be simplified using [[Modular Arithmetic]] on s with the modulus r. $sG = \overline{s}_rG$ ## ECDLP The elliptic curve discrete logarithm problem (ECDLP) is a problem to find $s$ when known $sG$. The order $r$ determines the difficulty of the problem. With sufficient $r$, the base assumption is that solving ECDLP is infeasible. Since $sG$ with a pairing algorithm is a field, and is isomorphic to the field of integers modulus $r$, it is wildly used in [[♯ Cryptography]]. ## References - [Elliptic curve point multiplication - Wikipedia](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication)