2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If you're interested in elliptic curve cryptography, you should maybe just get a book on elliptic curve cryptography in which the basic concepts of groups, elliptic curves, scalar multiplication, and the point at infinity will appear in the first act. If you're interested in cryptocurrency applications, you probably don't need to worry about elliptic curves in detail, and can just use higher-level ideas like signatures. $\endgroup$ – Squeamish Ossifrage Apr 8 at 1:54
3
$\begingroup$

The points on the Elliptic Curves ($E$) over e field $K$ are forming a commutative additive group with the identity $\mathcal{O}$; the point at infinity, also notated as $P_\infty$.

The scalar multiplication $[k]P$ this actually means adding $P$, $k$-time itself. 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 $[0]P = \mathcal{O}$, and $[k]P=[-k][-P]$ for $k<0$.

Bitcoin uses 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$.

Point addition in $\mathbb{Z}_p$ has an interesting property since the number of elements is finite 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 $P$. For security, we want this order huge.

Note 1: a point $P$ may not generate the whole group but it generates a cyclic subgroup.

Note 2: As pointed by SqueamishOssifrage, The Smart showed that if the order of the curve and order of the base field ($K$) are same then the discrete logarithm on this curves runs in linear time.

$\endgroup$
  • 1
    $\begingroup$ The order of the scalar ring is not the characteristic or order of the coordinate field. The orders are related, but are not the same except in cases that are trivially breakable as Nigel Smart showed. $\endgroup$ – Squeamish Ossifrage Apr 7 at 14:58
  • $\begingroup$ @SqueamishOssifrage thanks and for the links. $\endgroup$ – kelalaka Apr 7 at 17:00
  • $\begingroup$ I'm thinking that the points on the elliptic curve are a group and not a ring because of the lack of an absorbing element (0) for multiplication? $\endgroup$ – Andreas Yankopolus May 9 at 23:35
  • 2
    $\begingroup$ @AndreasYankopolus: there is no multiplication operation defined on two points -- only scalar x point, which is actually repeated addition -- much less a multiplicative identity. PS: although not true in general, the X9/Certicom prime curves, including secp256k1 used in Bitcoin, were chosen with group order prime so all elements generate the full group (cofactor=1) $\endgroup$ – dave_thompson_085 May 11 at 3:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.