Can you tell me why doing scalar multiplication of a point on a Elliptic curve over a finite field gets to a point at infinity?

Question

I am reading Programming Bitcoin. The author said:

Another property of scalar multiplication is that at a certain multiple, we get to the point at infinity (remember, the point at infinity is the additive identity or $0$). If we imagine a point $G$ and scalar-multiply until we get the point at infinity.

He doesn't explain why. So I don't understand why. I would like you to give me a plain explanation, without a serious mathematical proof, if that could be possible.

Answer 1

The points of an Elliptic Curves $E$ over a finite field $K$ are forming a finite commutative additive group ( finite Abelian group) with the point addition as the group operation. The group needs an identity element and is usually represented as $\mathcal{O}$. In most curves, this is the point at infinity and also notated as $P_\infty$. In the Edwards curves, the identity is an affine point $(0,1)$.

The scalar multiplication $[k]P$ this actually means adding the $P$ itself $k$-times. More formally;

let $k \in \mathbb{N}\backslash\{ 0\}$

\begin{align} [k]:& E \to E\\ &P\mapsto [k]P=\underbrace{P+P+\cdots+P}_{\text{$k$ times}}.\end{align}

and by being identity $[0]P = \mathcal{O}$.

When $k< 0$ and $[k]P=[-k](-P)$ since $[-1]P = -P$.

The number of points ( donated by $\#E(K)$) on Elliptic curves over a finite field is finite then if you add a point $P$ itself many times eventually you will get the identity $\mathcal{O}$.

$$\underbrace{P+P+\cdots+P}_{\text{$t$ times}} = [t]P= \mathcal{O}$$

The smallest $t$ will be the order of the subgroup generated by the point $P$. For security, we want this order huge and prime due to the attacks. If we consider the expected attack cost for Pollard's $\rho$ is $O(\sqrt{\#E(K)})$, i.e. we need to double the point size in bits ( use 256-bit curve to achieve 128-bit classical security).

Bitcoin uses the prime cure Secp256k1 which has characteristic $p$ and it is defined over the prime field $\mathbb{Z}_p$ with the curve equation $y^2=x^3+7$.

The order $n$ of the base point in the compressed form

G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

is

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Note 1: a point $P$ may not generate the whole group but it always generates a cyclic subgroup. In prime curves ( order is a prime) and this implies all elements, except the identity element, are a generator. For non-prime curves, one has to check the $[k]P \stackrel{?}= \mathcal O$ where $k\mid \#E(K)$ to find the order of $P$ by Lagrange's Theorem on Group Theory.

Note 2: As pointed by SqueamishOssifrage, The Smart showed that if the order of the curve and order of the base field ($K$) is the same (i.e. $\#E(\mathbf{F}_q ) = q$) then the discrete logarithm on this curves runs in linear time. Such curves are called anomalous curves.

Answer 2

In a secp256k1 context (including bitcoin), multiplying a point $P$ on the curve by an integer $k$ leads to the point at infinity $\mathcal O$ if and only if:

• $k$ is a multiple of the group order $n$, including when $k=0$. This $n$ is a large (prime) integer part of the secp256k1 characteristics. That's the number of points on the curve, including the point at infinity.
• or point $P$ is the point at infinity $\mathcal O$. That can't occur when $P$ is the generator $G$.

Mathematically: $k\times P=\mathcal O\iff k\bmod n=0$ or $P=\mathcal O$.

A good analogy is multiplication modulo prime $n$: multiplication by $k$ yields zero (modulo $n$) when $k$ is a multiple of $n$, or when what we multiply was already zero (modulo $n$). The analogy goes further: adding something that's zero (modulo $n$) changes nothing (modulo $n$), and that's the definition of zero (modulo $n$); much like adding the point at infinity $\mathcal O$ to any point on the curve leaves it unchanged, and that's the definition of the point at infinity.

Even simpler analogy: when in clock arithmetic we repeatedly add the current time (expressed as a whole number of hours), or equivalently multiply the current time by increasingly large integers, we eventually get to 12 o'clock (even if we did not start from 12 o'clock, that can occur before we multiplied by 12; that's because 12 is not prime).

Notice that when multiplying by $k$ not a multiple of $n$, some point multiplication algorithms might still internally encounter the point at infinity. For example when $k=8n-1$, some algorithms to compute $k\times P$ could compute it as $2\times\bigl(2\times\bigl(2\times\bigl(((k+1)/8)\times P\bigr)\bigr)\bigr)\,-\,P$. This is mathematically correct, but encounters the point at infinity in the computation of $((k+1)/8)\times P$.

When $P$ is not on the curve, multiplying it by an integer is not mathematically defined, and what happens can only we stated by examining how the multiplication is attempted.

Some point multiplication algorithms avoid both issues by special-casing multiplying the point at infinity; validating that the point is on the curve; reducing $k$ modulo $n$, then special-casing $k=0$; and making sure that they internally manipulate $j\times P$ only with $|j|<n$ (perhaps with an exception for even $j$ with $|j|<2n$ ).