How is the set of discrete points on elliptic curves determined for ECC applications?
One common method to define a point on an elliptic curve over a suitable finite field $(\Bbb F,+,\cdot)$ is that such point is one of
- any pair of coordinates $(x,y)$ with $x$ and $y$ elements of the field that obey an equation $y^2\,=\,x^3+a\cdot x+b$, where $a$ and $b$ are suitable constant elements of the finite field;
- an extra point called the point at infinity, noted $\infty$ (or $\mathcal O\,$), often assimilated to $(0,0)$, where $0$ is the additive neutral for the field and $b\ne0$.
That defines a finite (discrete) set: in principle, we can enumerate all the $(x,y)$ (say, with two nested loops) and for each pair test if the equation is met; then throw in the extra $\infty$. That form $(x,y)$ is a standard discrete expression of a point on the curve: Cartesian coordinates.
We can define a binary law on the curve, using the same equations¹ as for a continuous elliptic curve group law, only operating in the finite field. We'll note that new law $\boxplus$ (in order to distinguish it from the addition $+$ in the field, though $+$ is often used for both laws), such that for all points $U$, $V$, $W$ on the curve (including $\infty\,$)
- $U\boxplus V$ is a well-defined point on the curve.
- $(U\boxplus V)\boxplus W\,=\,U\boxplus(V\boxplus W)$ (that is: $\boxplus$ is associative).
- $U\boxplus V\,=\,V\boxplus U$ (that is: $\boxplus$ is commutative).
- $U\boxplus\infty\,=\,U$ (that is: $\infty$ is neutral for $\boxplus\,$).
- There exists a point $I$ on the curve with $U+I\,=\,\infty$. That $I$ is uniquely defined, and can be noted $\boxminus U$ (that is: the inverse of $U$ is $\boxminus U\,$). $U\boxplus\,\boxminus U\,=\,\infty$ becomes $U\boxminus U\,=\,\infty$. When $U\ne\infty$, $U$ is $(x,y)$ with $x$ and $y$ in the field and meeting the curve's equation $y^2\,=\,x^3+a\cdot x+b$, and $\boxminus U$ is $(x,-y$), also meeting the curve's equation since $(-y)^2\,=\,y^2\,$. If holds $\boxminus\infty\,=\,\infty$. Thus when $\infty$ is noted $(0,0)$, it holds $\boxminus(x,y)\,=\,(x,-y)$ for all $(x,y)$ of the curve.
In the above construction, we "discretized" a continuous elliptic curve and it's addition operation $\boxplus$ by
- changing from an infinite field to a finite field;
- keeping the curve's equation and the addition formula.
We can define² multiplication of an integer $k$ and a point $U$ of the curve, by using repeated addition:
$$k\times U\,\underset{\text{def}}=\;\begin{cases}
\infty&\text{if }k=0\\
((k-1)\times U)\boxplus U&\text{if }k>0\\
(-k)\times(\boxminus U)&\text{if }k<0
\end{cases}$$
It follows $0\times U\,=\,\infty\,$, $1\times U\,=\,U\,$, $2\times U\,=\,U\boxplus U\,$, $-1\times U\,=\,\boxminus U\,$.
It can be shown that there exists a point $G$ such that the set of all $m$ points $U$ on the curve is precisely the set of $U=k\times G$ for $k$ from $0$ to $m-1$. And when we take any point $G$ of the curve, the set of all $k\times G$ forms a group of $n$ distinct elements of the curve under the law $\boxplus$, with $n$ dividing $m$. In cryptography, we typically arrange things so that $n$ is prime, either because $m$ is prime and $n=m$ (the whole curve is used), or by choosing an appropriate $G$ of prime order $n$ (the group is a subgroup of the whole curve).
The construction as $U=k\times G$ with $k$ from $0$ to $n-1$ is another (discrete) way to express a point of the elliptic curve (sub)group, and the one used to construct a public key $U$ from a private key $k$. However, $U$ is not made public in this form, for that would reveal the private key. $U$ can be revealed as a pair $(x,y)$.
There are other common (discrete) ways to express a point of the elliptic curve. In particular, when the field is $\Bbb F_p$ (the integers modulo prime $p\,$), any point $U$ other than $\infty$ can be expressed as $x$ and the parity of $y$ (in this construction, not all $x$ yield a valid point).
Another common way is as a triplet $(x,y,z)$ of elements of the field with $z\ne0$ and $y^2\cdot z=x^3+a\cdot x\cdot z^2+b\cdot z^3$, which makes the evaluation of $\boxplus$ simpler. We can get back to the curve in Cartesian coordinates by projecting to $(x/z,\,y/z)$ when desired.
¹ These equations are:
$$U\boxplus V\underset{\text{def}}=\,\begin{cases}
U&\text{if }V=\infty\\
V&\text{if }U=\infty\\
\infty&\text{if }(x_U,y_U)=(x_V,-y_V)\\
\big(\lambda^2-x_U-x_V,\lambda\cdot(2\cdot x_U+x_V-\lambda^2)-y_U\big)&\text{otherwise}
\end{cases}$$
with in the otherwise case
$$\lambda\,\underset{\text{def}}=\;\begin{cases}
(3\cdot {x_U}^2+a)/(2\cdot y_U)&\text{if }U=V\\
(y_V-y_U)/(x_V-x_U)&\text{otherwise}
\end{cases}$$
Note: $/$ is division in the finite field, such that for all $r$ and $s$ in the finite field with $s\ne 0$, it holds $(r/s)\cdot s=1$. Here $1$ is the multiplicative neutral for the field; $2$ is $1+1\,$; and $3$ is $2+1\,$. When the field is the integers modulo prime $p$, the quantity $r/s$ can be computed as r*pow(s,-1,p)%p in Python starting with version 3.8 ( r*pow(s,p-2,p)%p works in more versions).
² This definition involves a number of field operations linear with $k$. For efficiency, an implementation can use
$$k\times U\,=\;\begin{cases}
\infty&\text{if }k=0\\
(-k)\times(\boxminus U)&\text{if }k<0\\
U&\text{if }k=1\\
((k/2)\times U)\boxplus((k/2)\times U)&\text{if }k>1\text{ and }k\text{ is even}\\
((k-1)\times U)\boxplus U&\text{if }k>1\text{ and }k\text{ is odd}
\end{cases}$$
