Main Page   Reference Manual   Compound List   File List

# Theory: the structure of Abelian groups

## Introduction

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 Cn.

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 C5 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 C5 = { 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 Cp = { 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 C5 can then be represented with:

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

Furthermore, let Cni denote the i-th element of Cn, starting to count at 0.  So, Cni is the order of iP for any P in Cn with order n.  Then obviously Cn0 = 1 and trivially Cn1 = n.  Moreover, as was derived above, Cny = 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 Cn is not prime.  For example, let n = 15 = 3 5.  Then of course we have C150 = 1 and C151 = 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:

Cny = 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

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

but also for example,

C9 = <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 Cn with we have to choose a basis.  Consider a group isomorphic with C6.  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 Cp, 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 C15 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 C3 C5 is isomorphic with C15 (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 C3 C5 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 Cn Cmi,j denote the order of the element iP + jQ.  Then obviously Cn   Cmi,0 = Cni = n / gcd(n, i) and Cn   Cm0,j = Cmj = 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 Cni] and k = 0 [mod Cmj]. And that, dear Watson, leads us to the observation that k = Cn Cmi,j = lcm(Cni, Cmj).  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 C3 C5i,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 C315 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 C21 C15u,v where there is both, a factor 3 in C21u (the top row), as well as in C15v (the column on the left), the resulting product is devided by gcd(C21u, C15v) = 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.

THEOREM 2

Cn Cm is isomorphic with Cnm iff n and m are coprime.

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 u1m + v1n = u2m + v2n [mod nm].  This means that there exists some k such that (u1 - u2)m + (v1 - v2)n = knm.  From that it is easy to see that both, (u1 - u2)m + (v1 - v2)n = 0 [mod n], as well as (u1 - u2)m + (v1 - v2)n = 0 [mod m].  The first of those is equivalent with (u1 - u2)m = 0 [mod n] and the second with (v1 - v2)n = 0 [mod m].  Because n m and m n, it follows that respectively n (u1 - u2) and m (v1 - v2).  Then, because u1 - u2 < n it follows that u1 = u2 and because v1 - v2 < m it follows that v1 = v2.  In other words, u1m + v1n u2m + v2n [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, pi devides nm.  Suppose pi n then pi m and therefore u so that is a factor of gcd(n, u) and = .  If on the other hand pi 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, Cn Cm and Cnm, 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 Cn Cm is Cn Cmu,v = lcm(Cnu, Cnv) = 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 Cn Cmu,v = nm / (gcd(n, u) gcd(m, v)).

Using lemma 3, we can enumerate the elements of Cnm using (u, v).  The order of the element in Cnm enumerate with (u,v) can then be written as Cnm (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 Cnm (u, v) = nm / gcd(nm, (um + vn) mod nm) = nm / gcd(nm, um + vn) = nm / (gcd(n, u) gcd(m, v)), which shows that Cn Cmu,v = Cnm (u, v) which implies in turn that both groups have the same number of elements of each order.  Applying theorem 1, this proves that Cn Cm is isomorphic with Cnm if n and m are coprime.  Finally observe that if n and m are not coprime, then Cnm has an element with order nm while the highest order of any element of Cn Cm = 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 Cpn, 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 pk, because Cpni = pn / gcd(pn, i), and will thus be factors of pn. We can therefore enumerate those different orders with k where n k .

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

As an example, consider C33.  Using the fact that C33i = 27 / gcd(27, i), we find

C33 = <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 Cpn Cpn.  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 C33 C33.  Using the fact that C33 C33i,j = lcm(C33i, C33j) we find

Where the top row and the left column correspond to C33 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 pk.  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 pk in the finite group with structure Cpn Cpn ... m times ... Cpn is
[(Cpn)m]k = pkm - p(k-1)m, where 0<k n.

Time to attack a more general case now.  Consider the group (Cpa0)m0 (Cpa1)m1 ... (Cpan)mn where 0 < a0 < a1 < ... < an.  We can think of this as a vector space of m0 + m1 + ... + mn dimensions where each of the (Cpai)mi forms an orthogonal subspace of dimension mi with a known structure (theorem 3).

Let ji enumerate the elements of (Cpai)mi.  Then 0 ji < paimi.  The elements of (Cpa0)m0 (Cpa1)m1 ... (Cpan)mn can be enumerated with (j0, j1, ..., jn) because each of the subspaces (Cpai)mi are orthogonal.  The order of the points are then given by

(Cpa0)m0 (Cpa1)m1 ... (Cpan)mnj0, j1, ..., jn = lcm((Cpa0)m0j0, (Cpa1)m1j1, ..., (Cpan)mnjn)

and because each of the (Cpai)miji is of the form pk, we can write this as

(Cpa0)m0 (Cpa1)m1 ... (Cpan)mnj0, j1, ..., jn = max((Cpa0)m0j0, (Cpa1)m1j1, ..., (Cpan)mnjn)

Now note that (Cpai)mi has only one element with order 1 (namely the 0 element), so there is only one value for ji such that (Cpai)miji = 1.  Therefore there is also only one combination of (j0, j1, ..., jn) for which the order of the total group is p0 = 1 and we have

[(Cpa0)m0 (Cpa1)m1 ... (Cpan)mn]0 = 1

For arbitrary k (corresponding to the order pk) we realize that [(Cpa0)m0 (Cpa1)m1 ... (Cpan)mn]k (which is defined as the number of points with order pk) is equal to the number of combinations of (j0, j1, ..., jn) for which max((Cpa0)m0j0, (Cpa1)m1j1, ..., (Cpan)mnjn) = pk.  Inspired by the previous, we don't look for the number of combinations for which the order is exactly pk but instead for the number of combinations for which the order is less than or equal pk.  Let t(k) be the number of different combinations of (j0, j1, ..., jn) for which the order of (Cpa0)m0 (Cpa1)m1 ... (Cpan)mn is less than or equal pk and let si(k) be the number of different combinations of ji for which the order of (Cpai)mi is less than or equal pk.  Then, because max((Cpa0)m0j0, (Cpa1)m1j1, ..., (Cpan)mnjn) is only less than or equal pk when each of the (Cpai)miji is less than or equal pk, t(k) = s0(k) s1(k) ... sn(k). And that almost brings us home because we already know the structure of (Cpai)mi and therefore know si(k)

Using this we find easily that

And finally, using the fact that for k > 0, [(Cpa0)m0 (Cpa1)m1 ... (Cpan)mn]k = t(k) - t(k - 1) we find

THEOREM 4

Let us abbreviate (Cpa0)m0 (Cpa1)m1 ... (Cpan)mn with Gp(a0, m0, aa, m1, ..., an, mn) or even just Gp.  The most general structure of a finite, Abelian group is then Gp0 Gp1 ... GpN.  Note that this is possible because of theorem 2 and the fact that the cardinality of all of the Gpi are coprime!

We cannot enumerate the (number of points with a given) order with k anymore, because the orders are much more complex than pk now.  In fact, the order of a point will be of the form p0k0 p1k1 ... pNkN where ki runs over all values from 0 till the an of the corresponding Gpi.  In other words, we can enumerate the orders with (k0, k1, ..., kN).

Now realize that again the space Gp0 Gp1 ... GpNk0, k1, ..., kN can be thought of as an N-dimensional space where each of the Gpiki are orthogonal subspaces.  And the order of the point enumerated by (k0, k1, ..., kN) is just

Gp0 Gp1 ... GpNk0, k1, ..., kN = lcm(Gp0k0, Gp1k1, ..., GpNkN) = Gp0k0 Gp1k1 ... GpNkN

where the last equality holds because each of the Gpiki = piki 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 (k0, k1, ..., kN) represents a different order.  The number of points with that order can easily be deduced from the fact that the Gpiki are orthogonal subspaces.  The number of points having the order Gp0k0 Gp1k1 GpNkN is therefore precisely [Gp0]k0 [Gp1]k1 [GpN]kN.  And the formula that describes the number of points with order p0k0 p1k1 ... pNkN for an arbitrary, finite, Abelian group with known structure is given by

[Gp0 Gp1 ... GpN]k0, k1, ..., kN = [Gp0]k0 [Gp1]k1 ... [GpN]kN

where pi are distinct primes, Gpi = (Cpia0i)m0i (Cpia1i)m1i ... (Cpiani)mni according to which the [Gpi]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.