:={k*P | k = 0, 1, 2,...} of the curve. (Here, k*P denotes the sum of k copies of P, where 0*P is the identity element O of the curve; k*P is commonly referred to as scalar multiplication of P by k.) If

has cardinality l, then l is called the order of P and l is the smallest positive integer so that l*P=O. The order of curve E is the cardinality of the set of its points, commonly denoted by |E|. A curve is cyclic if it is generated by some point of this curve. All curves of prime order are cyclic, while all curves of order h*n, where n is a large prime number and where h is a small number (the so-called co-factor), have a large cyclic subgroup of prime order n. In this case, a generator of order n is called a base point, commonly denoted by G, while a point of order dividing h is said to be in the small subgroup (or said to be a low-order point). For curves of prime order, this small subgroup is the singleton set, consisting of only the identity element O. A point that is not in the small subgroup is said to be a high-order point (since it has order at least n). A point P of the curve is in the small subgroup if h*P=O (and is a high-order point otherwise); this point P has order n if n*P=O and if it is not the identity element O. (The latter order check is commonly called full public key validation.) The above definitions extend to curves with a relatively large co-factor, by defining n to be the size of its largest prime-order subgroup. If R is a point of the curve that is also contained in

, there is a unique integer k in the interval [0, l-1] so that R=k*P, where l is the order of P. This number is called the discrete logarithm of R to Struik Expires July 25, 2022 [Page 37] Internet-Draft lwig-curve-representations Jan 2022 the base P. The discrete logarithm problem is the problem of finding the discrete logarithm of R to the base P for any two points P and R of the curve, if such a number exists. Random points R of

, where P has order l, can be computed by
generating a random integer k in the interval [0, l-1] and by
subsequently computing R:=k*P, where R then has order l/gcd(k,l). In
particular, if P is a high-order point (of curve E of order h*n),
then so is R, unless k is a multiple of n (in which case R is a low-
order point). For methods for generating k, see Appendix P.
If P is a fixed base point G of the curve, the pair (k, R:=k*G) is
commonly called a public-private key pair, the integer k the private
key, and the point R the corresponding public key. The private key k
can be represented as an integer in the interval [0,n-1], where G has
order n. If this representation is nonzero, R has order n;
otherwise, it has order one and is the identity element O of the
curve.
A curve E defined over the field GF(q) has order |E| relatively close
to q. More precisely, |E|=q+1-t for some integer t (the so-called
trace) with absolute value at most 2*|sqrt(q)|. This is commonly
referred to as the Hasse bound.
In this document, a quadratic twist of a curve E defined over a field
GF(q) is a specific curve E' related to E defined over the same
field, with cardinality |E'|, where |E|+|E'|=2*(q+1). If E is a
curve in one of the curve models specified in this document, a
quadratic twist E' of this curve can be expressed using the same
curve model, although (naturally) with its own curve parameters (see
Appendix A). Points that are points of both E and E' have order one
or two. Two curves E1 and E2 defined over the field GF(q) are said
to be isogenous if these have the same order and are said to be
isomorphic if the defining equation of E1 can be transformed into the
defining equation of E2 via a so-called admissible change of
variables. Note that isomorphic curves have necessarily the same
order and are, thus, a special case of isogenous curves. Isomorphic
curves have the same group structure, whereas this is not necessarily
the case for isogenous curves. Further details are out of scope.
Curves in short-Weierstrass form can have prime order, whereas
Montgomery curves and twisted Edwards curves always have an order
that is a multiple of four (and, thereby, a small subgroup of
cardinality four).
An ordered pair (x, y) whose coordinates are elements of GF(q) can be
associated with any ordered triple of the form [x*z: y*z: z], where z
is a nonzero element of GF(q), and can be uniquely recovered from
Struik Expires July 25, 2022 [Page 38]
Internet-Draft lwig-curve-representations Jan 2022
such a representation. The latter representation is commonly called
a representation in projective coordinates. Sometimes, yet other
representations are useful (e.g., representation in Jacobian
coordinates). Further details are out of scope.
The group laws in Appendix C are mostly expressed in terms of affine
points, but can also be expressed in terms of the representation of
these points in projective coordinates, thereby allowing clearing of
denominators. The group laws may also involve non-affine points
(such as the point at infinity O of a Weierstrass curve or of a
Montgomery curve). Those can also be represented in projective
coordinates. Further details are out of scope.
B.2. Finite Fields
The field GF(q), where q is a prime power, is defined as follows.
If q:=p is a prime number, the field GF(p) consists of the integers
in the interval [0,p-1] and two binary operations on this set:
addition and multiplication modulo p. This field is commonly called
a prime field. The additive and multiplicative identity elements are
0 and 1, respectively.
If q:=p^m, where p is a prime number and where m>0, the field GF(q)
is defined in terms of an irreducible polynomial f(z) in z of degree
m with coefficients in GF(p) (i.e., f(z) cannot be written as the
product of two polynomials in z of lower degree with coefficients in
GF(p)): in this case, GF(q) consists of the polynomials in z of
degree smaller than m with coefficients in GF(p) and two binary
operations on this set: polynomial addition and polynomial
multiplication modulo the irreducible polynomial f(z). By
definition, each element x of GF(q) is a polynomial in z of degree
smaller than m and can, therefore, be uniquely represented as a
vector (x_{m-1}, x_{m-2}, ..., x_1, x_0) of length m with
coefficients in GF(p), where x_i is the coefficient of z^i of
polynomial x. Note that this representation depends on the
irreducible polynomial f(z) of the field GF(p^m) in question (which
is often fixed in practice). Note that GF(q) contains the prime
field GF(p) as a subset. If m=1, the definitions of GF(p) and
GF(p^1) above coincide, since each nonzero element of GF(p) can be
viewed as a polynomial in z of degree zero. If m>1 (i.e., if q is a
strict prime power), then GF(q) is called a (nontrivial) extension
field of GF(p). The number p is called the characteristic of GF(q).
Any nonzero element g of GF(q) is a generator of the cyclic
multiplicative subgroup