The points on an elliptic curve over a finite field form a finite Abelian group (a commutative group). But, unlike in the case of finite fields, it is not enough to just know the number of points of such a group in order to know everything about its structure. In this chapter we will examine the Abelian group and its structure. At all times we will use (vector fields of) integers with some modulo as example. Understanding the structure of those (while ignoring multiplication) means that you also understand addition of points on elliptic curves: the structure will be the same. Nevertheless, we will continue to call the elements of our group points rather than elements.

Lets start with a few definitions. The *order* n of a point P is the smallest positive integer n for which nP = 0. The subset of points generated by P this way, { 0, P, 2P, 3P, ... (n-1)P } is also a group (either a subgroup of the original or the complete orginal) and is called a *cyclic* group, denoted with C_{n}.

Unlike with fields, a cyclic group does not need to have exactly a prime number of elements. Lets look at an example, using integers as said before. Let P be the integer 3 and let n = 5, then we obtain the cyclic group (which are always finite and Abelian by the way):

{ 0, 3, 6, 9, 12 }

and apparently, since 12 + 3 = 0, we have 15 0. And indeed, adding any two elements a and b gives again an element of this group, a + b = b + a and (a + b) + c = a + (b + c) (it is associative). For example 9 + 12 = 6 [mod 15]. This is a group.

We can denote this group with C_{5} because its structure is completely determined by the fact that it is cyclic and that it has 5 elements. If we pick any other integer for P then we will get a group that is isomorphic with this one (remember, isomorphic means that there is a one-on-one correspondence between every element of both groups that retains the algebraic relationships between the elements (addition in this case): no matter what you pick for P, it will always be that 2P + P = 3P, etc. Therefore, we might as well have picked the integer 1 for P. In that case we get the following isomorphic group:

{ 0, 1, 2, 3, 4 }

and now we have 5 0.

Let us now look at the order of each of these elements of C_{5} = { 0, P, 2P, 3P, 4P }. Obviously, the order of P is 5 (as per our definition). The order of 0 is 1, since 1 is the smallest positive integer such that 1 0 = 0. But what are the orders of 2P, 3P and 4P? In order (haha) to answer that we have to find the smallest positive integer x, such that x yP = 0, where 0 < y < n = 5. In other words, such that xy = 0 [mod 5]. Because y and 5 are coprime (obviously so: 5 is a prime!) there will exist integers s and t such that sy + tn = 1 (Bezout's lemma; follows from the Euclidean Algorithm. It goes too far to explain that in detail here), we can multiply both sides with s and then add nxt to both sides to get: xys + nxt = nxt [mod n] = 0 = x (sy + tn) = x [mod n]. And therefore the smallest positive integer such that x = 0 [mod n] is of course x = n. In other words, the order of every non-zero element of a cyclic group with a prime number of elements is equal to that prime.

Let me introduce a new notation (that is not commonly used in literature, but just for the convenience of this text) and denote the orders of a cyclic group C_{p} = { 0, P, 2P, 3P, ... (p-1)P } with < > by replacing every element with its order. And lets use to denote the operator that converts a group into this sequence of orders. Then the orders of C_{5} can then be represented with:

= < 1, 5, 5, 5, 5 >

Furthermore, let _{i} denote the i-th element of , starting to count at 0. So, _{i} is the order of iP for any P in C_{n} with order n. Then obviously _{0} = 1 and trivially _{1} = n. Moreover, as was derived above, _{y} = n for every y relatively prime with respect to n (which is another way of saying that gcd(y, n) = 1).

Next, lets look at what happens when the number of elements n of a cyclic group C_{n} is not prime. For example, let n = 15 = 3 5. Then of course we have _{0} = 1 and _{1} = 15, but the order of say 3P is 5, because 5 3P = 0. In fact, we can derive a simple formula for the order of yP:

_{y} = n / gcd(n, y)

which can be derived in exactly the same way as above by using the full form of Bezout's lemma; for arbitrary y and n there exists integers s and t such that sy + tn = gcd(n, y). Let x be the smallest positive integer for which x yP = 0 then it follows that xy = 0 [mod n]. Multiply both sides with s and add nxt to both sides to get xys + nxt = 0 [mod n] = x(ys + tn) = x gcd(n, y) which means that x gcd(n, y) has to be a multiple of n and therefore that the smallest positive integer for x for which this holds is n / gcd(n, y) (note that this is an integer as gcd(n, y) always devides n, ofcourse).

Using this formula we can write out

= <1, 15, 15, 5, 15, 3, 5, 15, 15, 5, 3, 15, 5, 15, 15>

but also for example,

= <1, 9, 9, 3, 9, 9, 3, 9, 9>

It is easy to verify this.

All of the above is about 1-dimensional cases: cyclic groups isomorphic with . Before considering higher dimensional structures, let me first stress the fact that in order to compare the general cyclic group C_{n} with we have to choose a basis. Consider a group isomorphic with C_{6}. If the real group exists of the abstract elements {0, P, 2P, 3P, 4P, 5P} and we want to compare that with /6 = {0, 1, 2, 3, 4, 5}, then we could chose P as a basis. Subsequently we then can generate all elements of the group by adding P repeatedly to itself, just as is the case with the element 1 of /6 . However, we could also have chosen the element 5P as a basis. Repeatedly adding 5P to itself generates the same group: {0, (5P), 2(5P), 3(5P), 4(5P), 5(5P)} = {0, 5P, 4P, 3P, 2P, P}.

Understanding the concept of a basis, we can easily extend the structure of a general group by comparing them with vector spaces of more than one dimension. For example, consider the group which exists of pairs (x, y) where x and y . A basis for this is {(1, 0), (0, 1)}. Adding (1, 0) repeatedly to itself would generate the elements {(1, 0), (2, 0), (3, 0), ..., (n - 1, 0)} and adding (0, 1) repeatedly to itself generates the elements {(0, 1), (0, 2), (0, 3), ..., (0, m - 1)}. Those n + m - 1 elements clearly are not all elements yet; adding any two elements of a group must give yet again an element of the group. Therefore, adding for example (0, 3) + (2, 0) = (2, 3) must be an element of this group too. By repeatedly adding every element to every element until there is no new element that we can generate, we end up with the following elements:

Likewise we can chose two points P and Q as a basis. Suppose that P has order n and Q has order m then we might end up with the following structure:

Of course this can only happen when Q is a distinct point that is not generated by P. In other words, there exists no integer k such that Q = kP. Consequently, a group C_{p}, where p is prime has truely only a single dimension: every non-zero point has order p and it is not possible to choose a point P, as an element of the basis, that doesn't generate all existing elements.

This is not true however for a cyclic group with a number of elements that isn't prime. Consider again C_{15} that we analyzed above. This group has elements with an order less than 15 and thus we can chose a point P that doesn't generate all points! Lets use /15 as an example again. Then we could chose P = 3 as one element of the basis, generating {0, 3, 6, 9, 12}, and chose Q = 5 as the second element, generating {0, 5, 10}. Using those as a basis and working out the structure as given above will give us:

So, amazingly enough (at least, at first sight) the 2-dimensional group C_{3} C_{5} is *isomorphic* with C_{15} (which follows immediately from the fact that both are isomorphic with /15 as we just proved)!

In order to get some more insight in this, lets use our special operator on C_{3} C_{5} and again use < > for denoting that we replaced each element with its order. That gives us

Time for a little expansion of our notation. Let _{i,j} denote the order of the element iP + jQ. Then obviously _{i,0} = _{i} = n / gcd(n, i) and _{0,j} = _{j} = m / gcd(m, j). When i,j 0 then the order of iP + jQ is the smallest positive integer k such that k(iP + jQ) = 0. And because P and Q are linearly independent, that can only be the case when both, kiP = 0 and kjQ = 0. In other words, when k = 0 [mod _{i}] and k = 0 [mod _{j}]. And that, dear Watson, leads us to the observation that k = _{i,j} = lcm(_{i}, _{j}). Please take a moment the time to understand what this means in terms of the < > notation above. These formulas are really not difficult once you can "visualize" their meaning. Basically, it means that each of the 15's above are the lcm (least common multiple) of what is in left column (3) and the top row (5). Because 3 and 5 are coprime (meaning that gcd(3, 5) = 1) and since lcm(a, b) = ab / gcd(a, b), each of the orders _{i,j} with i,j 0 is equal to lcm(3, 5) = 3 5 / gcd(3, 5) = 15.

Lets do one more example, where n and m are not coprime.

This obviously has 21 15 = 315 elements and is therefore, also obviously, not isomorphic with C_{315} which has 210 elements with order 315, and this has 0 such elements. The reason for the missing orders with value 315 is precisely the fact that 15 and 21 are not coprime. Each order _{u,v} where there is both, a factor 3 in _{u} (the top row), as well as in _{v} (the column on the left), the resulting product is devided by gcd(_{u}, _{v}) = 3 and gives an order of 105 instead of 315.

The following theorem should now be intuitively correct, and is therefore given without further prove.

**THEOREM 1**

Two finite, Abelian groups are isomorphic iff they have the same number of elements of each order.

Using this, we can prove the following theorem.

Before we can prove this we need a few lemmas.

**LEMMA 3**

Let n and m be two positive integers that are relative prime. Let u and v . Then the map : defined by (u, v) = um + vn [mod nm] is a bijection.

**PROOF**

There are in total nm different combinations to chose the pair (u,v). As a result of the modulo nm, we obviously have (u, v) = um + vn [mod nm] . Assume that u_{1}m + v_{1}n = u_{2}m + v_{2}n [mod nm]. This means that there exists some k such that (u_{1} - u_{2})m + (v_{1} - v_{2})n = knm. From that it is easy to see that both, (u_{1} - u_{2})m + (v_{1} - v_{2})n = 0 [mod n], as well as (u_{1} - u_{2})m + (v_{1} - v_{2})n = 0 [mod m]. The first of those is equivalent with (u_{1} - u_{2})m = 0 [mod n] and the second with (v_{1} - v_{2})n = 0 [mod m]. Because n m and m n, it follows that respectively n (u_{1} - u_{2}) and m (v_{1} - v_{2}). Then, because u_{1} - u_{2} < n it follows that u_{1} = u_{2} and because v_{1} - v_{2} < m it follows that v_{1} = v_{2}. In other words, u_{1}m + v_{1}n u_{2}m + v_{2}n [mod nm] and each of the of the nm different combinations of (u,v) will give a different value in . Since the latter has precisely nm different elements, the bijection is proven.

**LEMMA 4**

Let n and m be two positive integers that are relative prime. Let u and v . Then gcd(n, u) gcd(m, v) = gcd(nm, um + vn).

**PROOF**

Let be the prime factor presentation of gcd(n, u) and let be the prime factor presentation of gcd(m, v). Then observe that any prime factor that occurs in one does not occur in the other because n and m are coprime and therefore do not share any factor. In other words, for any i either = 0 or = 0. Furthermore we have gcd(n, u) gcd(m, v) = . Now assume that gcd(nm, um + vn) = . Then for any i for which 0, p_{i} devides nm. Suppose p_{i} n then p_{i} m and therefore u so that is a factor of gcd(n, u) and = . If on the other hand p_{i} m then likewise = . Finally, it is easy to see that for any i for which = 0, = = 0, so that adding this all up we have for any i, = + and thus gcd(n, u) gcd(m, v) = gcd(nm, um + vn).

**PROOF OF THEOREM 2**

The total number of elements in each group, C_{n} C_{m} and C_{nm}, is nm and can therefore be enumerated with (u,v) where u and v . For each element enumerated by (u,v), the order of that element in C_{n} C_{m} is _{u,v} = lcm(_{u}, _{v}) = lcm(n / gcd(n, u), m / gcd(m, v)) = nm / (gcd(n, u) gcd(m, v) gcd(n / gcd(n, u), m / gcd(m, v))). When n and m are coprime then so are n/gcd(n, u) and m/gcd(m, v) of course, therefore we have _{u,v} = nm / (gcd(n, u) gcd(m, v)).

Using lemma 3, we can enumerate the elements of C_{nm} using (u, v). The order of the element in C_{nm} enumerate with (u,v) can then be written as _{ (u, v)} = nm / gcd(nm, (u, v)). Filling in (u, v), using the fact that gcd(a, b mod a) = gcd(a, b + ka) = gcd(a, b) and applying lemma 4, we can write _{ (u, v)} = nm / gcd(nm, (um + vn) mod nm) = nm / gcd(nm, um + vn) = nm / (gcd(n, u) gcd(m, v)), which shows that _{u,v} = _{ (u, v)} which implies in turn that both groups have the same number of elements of each order. Applying theorem 1, this proves that C_{n} C_{m} is isomorphic with C_{nm} if n and m are coprime. Finally observe that if n and m are not coprime, then C_{nm} has an element with order nm while the highest order of any element of C_{n} C_{m} = nm / gcd(n, m) so that the two groups are obviously not isomorphic, concluding the proof of theorem 2.

Lets investigate the structure of cyclic groups of the form C_{pn}, where p is prime.

As a result of theorem 1 we can concentrate solely on the number of elements for each occuring order. Obviously, the only possible orders are of the form p^{k}, because _{i} = p^{n} / gcd(p^{n}, i), and will thus be factors of p^{n}. We can therefore enumerate those different orders with k where n k .

Let [C_{pn}]_{k} be the number of points in C_{pn} with order p^{k}. Then [C_{pn}]_{0} = 1 because there is only one point with order p^{0} = 1; namely the 0. If k > 0 then [C_{pn}]_{k} = p^{k} - p^{k-1}. To understand this, lets look at the isomorphic group /p^{n} . Assume that p^{k}s = 0 [mod p^{n}] (which means the order of s is a divisor of p^{k}), s /p^{n} . Then there exists an l such that p^{k}s = lp^{n} s = lp^{n-k}. Because of the restriction 0 s < p^{n}, this means that 0 l < p^{k} and l can take exactly p^{k} different values, leading to p^{k} different values of s for which p^{k}s = 0 [mod p^{n}]. Because for each of these values of s, the order is a divisor of p^{k} this means that there are p^{k} points with order p^{k} or less. That gives us the result [C_{pn}]_{k} = p^{k} - [C_{pn}]_{i} from which we can easily deduce by induction that [C_{pn}]_{k} = p^{k} - p^{k-1}.

As an example, consider C_{33}. Using the fact that _{i} = 27 / gcd(27, i), we find

= <1, 27, 27, 9, 27, 27, 9, 27, 27, 3, 27, 27, 9, 27, 27, 9, 27, 27, 3, 27, 27, 9, 27, 27, 9, 27, 27>

in which we count 1 time a 1, 3 - 1 times a 3, 9 - 3 times a 9 and 27 - 9 times a 27.

Next lets consider groups of the form C_{pn} C_{pn}. At this point I am getting a bit tired of formulas (as no doubt you are too). This document is not intended to prove anything, but merely to make things intuitively clear, making someone ready for further self-study. Therefore, lets reverse things now - and first give an example/picture and "deduce" the end formula from that.

Consider C_{33} C_{33}. Using the fact that _{i,j} = lcm(_{i}, _{j}) we find

Where the top row and the left column correspond to and every other value in the middle is the least common multiple of the two numbers in the top row and the left column. Now before even attempting to count this, lets rearrange the rows and columns a bit so that the smallest numbers are against the 1 in the top-left:

Surprised? Now imagine an axis perpendicular to this, also with one 1, two 3's, six 9's and eighteen 27's. Then the image appears of a cubes inside cubes, each with a side of p^{k}. And so on for higher dimensions.

And so we deduced, a lot faster than with non-insightful formulas, the following theorem.

**THEOREM 3**

The number of points with order p^{k} in the finite group with structure C_{pn} C_{pn} ... m times ... C_{pn} is

[(C_{pn})^{m}]_{k} = p^{km} - p^{(k-1)m}, where 0<k n.

[(C

Time to attack a more general case now. Consider the group (C_{pa0})^{m0} (C_{pa1})^{m1} ... (C_{pan})^{mn} where 0 < a_{0} < a_{1} < ... < a_{n}. We can think of this as a vector space of m_{0} + m_{1} + ... + m_{n} dimensions where each of the (C_{pai})^{mi} forms an orthogonal subspace of dimension m_{i} with a known structure (theorem 3).

Let j_{i} enumerate the elements of (C_{pai})^{mi}. Then 0 j_{i} < p^{aimi}. The elements of (C_{pa0})^{m0} (C_{pa1})^{m1} ... (C_{pan})^{mn} can be enumerated with (j_{0}, j_{1}, ..., j_{n}) because each of the subspaces (C_{pai})^{mi} are orthogonal. The order of the points are then given by

_{j0, j1, ..., jn} = lcm(_{j0}, _{j1}, ..., _{jn})

and because each of the _{ji} is of the form p^{k}, we can write this as

_{j0, j1, ..., jn} = max(_{j0}, _{j1}, ..., _{jn})

Now note that (C_{pai})^{mi} has only one element with order 1 (namely the 0 element), so there is only one value for j_{i} such that _{ji} = 1. Therefore there is also only one combination of (j_{0}, j_{1}, ..., j_{n}) for which the order of the total group is p^{0} = 1 and we have

[(C_{pa0})^{m0} (C_{pa1})^{m1} ... (C_{pan})^{mn}]_{0} = 1

For arbitrary k (corresponding to the order p^{k}) we realize that [(C_{pa0})^{m0} (C_{pa1})^{m1} ... (C_{pan})^{mn}]_{k} (which is defined as the number of points with order p^{k}) is equal to the number of combinations of (j_{0}, j_{1}, ..., j_{n}) for which max(_{j0}, _{j1}, ..., _{jn}) = p^{k}. Inspired by the previous, we don't look for the number of combinations for which the order is exactly p^{k} but instead for the number of combinations for which the order is less than or equal p^{k}. Let t(k) be the number of different combinations of (j_{0}, j_{1}, ..., j_{n}) for which the order of (C_{pa0})^{m0} (C_{pa1})^{m1} ... (C_{pan})^{mn} is less than or equal p^{k} and let s_{i}(k) be the number of different combinations of j_{i} for which the order of (C_{pai})^{mi} is less than or equal p^{k}. Then, because max(_{j0}, _{j1}, ..., _{jn}) is only less than or equal p^{k} when each of the _{ji} is less than or equal p^{k}, t(k) = s_{0}(k) s_{1}(k) ... s_{n}(k). And that almost brings us home because we already know the structure of (C_{pai})^{mi} and therefore know s_{i}(k)

Using this we find easily that

And finally, using the fact that for k > 0, [(C_{pa0})^{m0} (C_{pa1})^{m1} ... (C_{pan})^{mn}]_{k} = t(k) - t(k - 1) we find

Let us abbreviate (C_{pa0})^{m0} (C_{pa1})^{m1} ... (C_{pan})^{mn} with G_{p}(a_{0}, m_{0}, a_{a}, m_{1}, ..., a_{n}, m_{n}) or even just G_{p}. The most general structure of a finite, Abelian group is then G_{p0} G_{p1} ... G_{pN}. Note that this is possible because of theorem 2 and the fact that the cardinality of all of the G_{pi} are coprime!

We cannot enumerate the (number of points with a given) order with k anymore, because the orders are much more complex than p^{k} now. In fact, the order of a point will be of the form p_{0}^{k0} p_{1}^{k1} ... p_{N}^{kN} where k_{i} runs over all values from 0 till the a_{n} of the corresponding G_{pi}. In other words, we can enumerate the orders with (k_{0}, k_{1}, ..., k_{N}).

Now realize that again the space _{k0, k1, ..., kN} can be thought of as an N-dimensional space where each of the _{ki} are orthogonal subspaces. And the order of the point enumerated by (k_{0}, k_{1}, ..., k_{N}) is just

_{k0, k1, ..., kN} = lcm(_{k0}, _{k1}, ..., _{kN}) = _{k0} _{k1} ... _{kN}

where the last equality holds because each of the _{ki} = p_{i}^{ki} is coprime to the others. Please note that while before we enumerated over each point separately, now we are enumerating over groups of points with the same order! And indeed every different combination of (k_{0}, k_{1}, ..., k_{N}) represents a different order. The number of points with that order can easily be deduced from the fact that the _{ki} are orthogonal subspaces. The number of points having the order _{k0} _{k1} _{kN} is therefore precisely [G_{p0}]_{k0} [G_{p1}]_{k1} [G_{pN}]_{kN}. And the formula that describes the number of points with order p_{0}^{k0} p_{1}^{k1} ... p_{N}^{kN} for an arbitrary, finite, Abelian group with known structure is given by

[G_{p0} G_{p1} ... G_{pN}]_{k0, k1, ..., kN} = [G_{p0}]_{k0} [G_{p1}]_{k1} ... [G_{pN}]_{kN}

where p_{i} are distinct primes, G_{pi} = (C_{pia0i})^{m0i} (C_{pia1i})^{m1i} ... (C_{piani})^{mni} according to which the [G_{pi}]_{ki} are given by theorem 4.

I wrote code that does the inverse of this. Given a list with orders and the number of points having that order, the code determines the structure of the group. This code can be found in the file `testsuite/point/decode_group_structure.cc`

, part of libecc.