libecc: Elliptic Curve Cryptography C++ Library

Main Page Reference Manual Compound List File List

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 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 $\equiv$ 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₅ 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 $\equiv$ 0.

Let us now look at the order of each of these elements of C₅ = { 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 $\cdot$ 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 $\cdot$ 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₅ can then be represented with:

C₅ = < 1, 5, 5, 5, 5 >

Furthermore, let C_n_i denote the i-th element of C_n, starting to count at 0. So, C_n_i is the order of iP for any P in C_n with order n. Then obviously C_n₀ = 1 and trivially C_n₁ = n. Moreover, as was derived above, C_n_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 $\cdot$ 5. Then of course we have C₁₅₀ = 1 and C₁₅₁ = 15, but the order of say 3P is 5, because 5 $\cdot$ 3P = 0. In fact, we can derive a simple formula for the order of yP:

C_n_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 $\cdot$ 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

C₁₅ = <1, 15, 15, 5, 15, 3, 5, 15, 15, 5, 3, 15, 5, 15, 15>

but also for example,

C₉ = <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 $\mathbb{Z}/n\mathbb{Z}$ . Before considering higher dimensional structures, let me first stress the fact that in order to compare the general cyclic group C_n with $\mathbb{Z}/n\mathbb{Z}$ we have to choose a basis. Consider a group isomorphic with C₆. If the real group exists of the abstract elements {0, P, 2P, 3P, 4P, 5P} and we want to compare that with $\mathbb{Z}$ /6 $\mathbb{Z}$ = {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 $\mathbb{Z}$ /6 $\mathbb{Z}$ . 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 $\mathbb{Z}/n\mathbb{Z}$ $\times$ $\mathbb{Z}/m\mathbb{Z}$ which exists of pairs (x, y) where x $\in$ $\mathbb{Z}/n\mathbb{Z}$ and y $\in$ $\mathbb{Z}/m\mathbb{Z}$ . 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:

$\left\{ \begin{array}{cccccc} 0 & (1,0) & (2,0) & (3,0) & \cdots & (n-1, 0) \\ (0,1) & (1,1) & (2,1) & (3,1) \\ (0,2) & (1,2) & (2,2) & (3,2) \\ \vdots & & & & \ddots \\ (0,m-1) & & & & & (n-1, m-1) \end{array} \right\}$

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:

$\left\{ \begin{array}{cccccc} 0 & P & 2P & 3P & \cdots & (n-1)P \\ Q & P+Q & 2P+Q & 3P+Q \\ 2Q & P+2Q & 2P+2Q & 3P+2Q \\ \vdots & & & & \ddots \\ (m-1)Q & & & & & (n-1)P + (m-1)Q \end{array} \right\}$

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₁₅ 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 $\mathbb{Z}$ /15 $\mathbb{Z}$ 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:

$\left\{ \begin{array}{ccccc} 0 & 3 & 6 & 9 & 12 \\ 5 & 8 & 11 & 14 & 2 \\ 10 & 13 & 1 & 4 & 7 \end{array} \right\}$

So, amazingly enough (at least, at first sight) the 2-dimensional group C₃ $\times$ C₅ is isomorphic with C₁₅ (which follows immediately from the fact that both are isomorphic with $\mathbb{Z}$ /15 $\mathbb{Z}$ as we just proved)!

In order to get some more insight in this, lets use our special operator on C₃ $\times$ C₅ and again use < > for denoting that we replaced each element with its order. That gives us

$\left| C_3 \times C_5 \right| = \left| \left\{ \begin{array}{ccccc} 0 & 3 & 6 & 9 & 12 \\ 5 & 8 & 11 & 14 & 2 \\ 10 & 13 & 1 & 4 & 7 \end{array} \right\}\right| = \left\langle \begin{array}{ccccc} 1 & 5 & 5 & 5 & 5 \\ 3 & 15 & 15 & 15 & 15 \\ 3 & 15 & 15 & 15 & 15 \end{array} \right\rangle$

Time for a little expansion of our notation. Let C_n $\times$ C_m_i,j denote the order of the element iP + jQ. Then obviously C_n $\times$ C_m_i,0 = C_n_i = n / gcd(n, i) and C_n $\times$ C_m_0,j = C_m_j = m / gcd(m, j). When i,j $\neq$ 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 C_n_i] and k = 0 [mod C_m_j]. And that, dear Watson, leads us to the observation that k = C_n $\times$ C_m_i,j = lcm(C_n_i, C_m_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 C₃ $\times$ C₅_i,j with i,j $\neq$ 0 is equal to lcm(3, 5) = 3 $\cdot$ 5 / gcd(3, 5) = 15.

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

$\left| C_{21} \times C_{15} \right| = \left\langle \begin{array}{ccccccccccccccccccccc} 1 & 21 & 21 & 7 & 21 & 21 & 7 & 3 & 21 & 7 & 21 & 21 & 7 & 21 & 3 & 7 & 21 & 21 & 7 & 21 & 21 \\ 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105\\ 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105\\ 5 & 105& 105& 35 & 105& 105& 35 & 15 & 105& 35 & 105& 105& 35 & 105& 15 & 35 & 105& 105& 35 & 105& 105\\ 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105\\ 3 & 21 & 21 & 21 & 21 & 21 & 21 & 3 & 21 & 21 & 21 & 21 & 21 & 21 & 3 & 21 & 21 & 21 & 21 & 21 & 21 \\ 5 & 105& 105& 35 & 105& 105& 35 & 15 & 105& 35 & 105& 105& 35 & 105& 15 & 35 & 105& 105& 35 & 105& 105\\ 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105\\ 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105\\ 5 & 105& 105& 35 & 105& 105& 35 & 15 & 105& 35 & 105& 105& 35 & 105& 15 & 35 & 105& 105& 35 & 105& 105\\ 3 & 21 & 21 & 21 & 21 & 21 & 21 & 3 & 21 & 21 & 21 & 21 & 21 & 21 & 3 & 21 & 21 & 21 & 21 & 21 & 21 \\ 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105\\ 5 & 105& 105& 35 & 105& 105& 35 & 15 & 105& 35 & 105& 105& 35 & 105& 15 & 35 & 105& 105& 35 & 105& 105\\ 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105\\ 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105& 15 & 105& 105& 105& 105& 105& 105\\ \end{array} \right\rangle$

This obviously has 21 $\cdot$ 15 = 315 elements and is therefore, also obviously, not isomorphic with C₃₁₅ 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 C₂₁ $\times$ C₁₅_u,v where there is both, a factor 3 in C₂₁_u (the top row), as well as in C₁₅_v (the column on the left), the resulting product is devided by gcd(C₂₁_u, C₁₅_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.

THEOREM 2

C_n $\times$ C_m is isomorphic with C_nm 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 $\in$ $\mathbb{Z}/n\mathbb{Z}$ and v $\in$ $\mathbb{Z}/m\mathbb{Z}$ . Then the map $\phi$ : $\mathbb{Z}/n\mathbb{Z}$ $\times$ $\mathbb{Z}/m\mathbb{Z}$ $\rightarrow$ $\mathbb{Z}/nm\mathbb{Z}$ defined by $\phi$ (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 $\phi$ (u, v) = um + vn [mod nm] $\in$ $\mathbb{Z}/nm\mathbb{Z}$ . Assume that u₁m + v₁n = u₂m + v₂n [mod nm]. This means that there exists some k $\in$ $\mathbb{Z}$ such that (u₁ - u₂)m + (v₁ - v₂)n = knm. From that it is easy to see that both, (u₁ - u₂)m + (v₁ - v₂)n = 0 [mod n], as well as (u₁ - u₂)m + (v₁ - v₂)n = 0 [mod m]. The first of those is equivalent with (u₁ - u₂)m = 0 [mod n] and the second with (v₁ - v₂)n = 0 [mod m]. Because n $\nmid$ m and m $\nmid$ n, it follows that respectively n $\mid$ (u₁ - u₂) and m $\mid$ (v₁ - v₂). Then, because $|$ u₁ - u₂ $|$ < n it follows that u₁ = u₂ and because $|$ v₁ - v₂ $|$ < m it follows that v₁ = v₂. In other words, u₁m + v₁n $\not\equiv$ u₂m + v₂n [mod nm] and each of the of the nm different combinations of (u,v) will give a different value in $\mathbb{Z}/nm\mathbb{Z}$ . 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 $\in$ $\mathbb{Z}/n\mathbb{Z}$ and v $\in$ $\mathbb{Z}/m\mathbb{Z}$ . Then gcd(n, u) gcd(m, v) = gcd(nm, um + vn).

PROOF

Let $\prod_{i=1}^{z}p_i^{\alpha_i}$ be the prime factor presentation of gcd(n, u) and let $\prod_{i=1}^{z}p_i^{\beta_i}$ 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 $\alpha_i$ = 0 or $\beta_i$ = 0. Furthermore we have gcd(n, u) gcd(m, v) = $\prod_{i=1}^{z}p_i^{\alpha_i + \beta_i}$ . Now assume that gcd(nm, um + vn) = $\prod_{i=1}^{z}p_i^{\gamma_i}$ . Then for any i for which $\gamma_i$ $\neq$ 0, p_i devides nm. Suppose p_i $\mid$ n then p_i $\nmid$ m and therefore $p_i^{\gamma_i}\mid$ u so that $p_i^{\gamma_i}$ is a factor of gcd(n, u) and $\gamma_i$ = $\alpha_i$ . If on the other hand p_i $\mid$ m then likewise $\gamma_i$ = $\beta_i$ . Finally, it is easy to see that for any i for which $\gamma_i$ = 0, $\alpha_i$ = $\beta_i$ = 0, so that adding this all up we have for any i, $\gamma_i$ = $\alpha_i$ + $\beta_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 $\times$ C_m and C_nm, is nm and can therefore be enumerated with (u,v) where u $\in$ $\mathbb{Z}/n\mathbb{Z}$ and v $\in$ $\mathbb{Z}/m\mathbb{Z}$ . For each element enumerated by (u,v), the order of that element in C_n $\times$ C_m is C_n $\times$ C_m_u,v = lcm(C_n_u, C_n_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 C_n $\times$ C_m_u,v = nm / (gcd(n, u) gcd(m, v)).

Using lemma 3, we can enumerate the elements of C_nm using $\phi$ (u, v). The order of the element in C_nm enumerate with (u,v) can then be written as C_nm_{(u, v)} = nm / gcd(nm, $\phi$ (u, v)). Filling in $\phi$ (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 C_nm_{(u, v)} = nm / gcd(nm, (um + vn) mod nm) = nm / gcd(nm, um + vn) = nm / (gcd(n, u) gcd(m, v)), which shows that C_n $\times$ C_m_u,v = C_nm_{(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 $\times$ 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 $\times$ 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_pⁿ, 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 C_pⁿ_i = pⁿ / gcd(pⁿ, i), and will thus be factors of pⁿ. We can therefore enumerate those different orders with k where n $\geq$ k $\in$ $\mathbb{N}$ .

Let [C_pⁿ]_k be the number of points in C_pⁿ with order p^k. Then [C_pⁿ]₀ = 1 because there is only one point with order p⁰ = 1; namely the 0. If k > 0 then [C_pⁿ]_k = p^k - p^k-1. To understand this, lets look at the isomorphic group $\mathbb{Z}$ /pⁿ $\mathbb{Z}$ . Assume that p^ks = 0 [mod pⁿ] (which means the order of s is a divisor of p^k), s $\in$ $\mathbb{Z}$ /pⁿ $\mathbb{Z}$ . Then there exists an l such that p^ks = lpⁿ $\rightarrow$ s = lp^n-k. Because of the restriction 0 $\leq$ s < pⁿ, this means that 0 $\leq$ l < p^k and l can take exactly p^k different values, leading to p^k different values of s for which p^ks = 0 [mod pⁿ]. 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_pⁿ]_k = p^k - $\sum_{i=0}^{k-1}$ [C_pⁿ]_i from which we can easily deduce by induction that [C_pⁿ]_k = p^k - p^k-1.

As an example, consider C_3³. Using the fact that C_3³_i = 27 / gcd(27, i), we find

C_3³ = <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_pⁿ $\times$ C_pⁿ. 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_3³ $\times$ C_3³. Using the fact that C_3³ $\times$ C_3³_i,j = lcm(C_3³_i, C_3³_j) we find

$\left| C_{3^3} \times C_{3^3} \right| = \left\langle \begin{array}{ccccccccccccccccccccccccccc} 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 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 3 & 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 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 3 & 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 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 & 9 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \end{array} \right\rangle$

Where the top row and the left column correspond to C_3³ 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:

$\left| C_{3^3} \times C_{3^3} \right| = \left\langle \begin{array}{ccccccccccccccccccccccccccc} 1 & 3 & 3 & 9 & 9 & 9 & 9 & 9 & 9 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 3 & 3 & 3 & 9 & 9 & 9 & 9 & 9 & 9 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 3 & 3 & 3 & 9 & 9 & 9 & 9 & 9 & 9 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 & 27 \\ \end{array} \right\rangle$

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_pⁿ $\times$ C_pⁿ $\times$ ... m times ... $\times$ C_pⁿ is
[(C_pⁿ)^m]_k = p^km - p^(k-1)m, where 0<k $\leq$ n.

Time to attack a more general case now. Consider the group (C_p^a₀)^m₀ $\times$ (C_p^a₁)^m₁ $\times$ ... $\times$ (C_{p^a_n})^m_n where 0 < a₀ < a₁ < ... < a_n. We can think of this as a vector space of m₀ + m₁ + ... + m_n dimensions where each of the (C_{p^a_i})^m_i forms an orthogonal subspace of dimension m_i with a known structure (theorem 3).

Let j_i enumerate the elements of (C_{p^a_i})^m_i. Then 0 $\leq$ j_i < p^a_im_i. The elements of (C_p^a₀)^m₀ $\times$ (C_p^a₁)^m₁ $\times$ ... $\times$ (C_{p^a_n})^m_n can be enumerated with (j₀, j₁, ..., j_n) because each of the subspaces (C_{p^a_i})^m_i are orthogonal. The order of the points are then given by

(C_p^a₀)^m₀ $\times$ (C_p^a₁)^m₁ $\times$ ... $\times$ (C_{p^a_n})^m_n_{j₀, j₁, ..., j_n} = lcm((C_p^a₀)^m₀_j₀, (C_p^a₁)^m₁_j₁, ..., (C_{p^a_n})^m_n_{j_n})

and because each of the (C_{p^a_i})^m_i_{j_i} is of the form p^k, we can write this as

(C_p^a₀)^m₀ $\times$ (C_p^a₁)^m₁ $\times$ ... $\times$ (C_{p^a_n})^m_n_{j₀, j₁, ..., j_n} = max((C_p^a₀)^m₀_j₀, (C_p^a₁)^m₁_j₁, ..., (C_{p^a_n})^m_n_{j_n})

Now note that (C_{p^a_i})^m_i has only one element with order 1 (namely the 0 element), so there is only one value for j_i such that (C_{p^a_i})^m_i_{j_i} = 1. Therefore there is also only one combination of (j₀, j₁, ..., j_n) for which the order of the total group is p⁰ = 1 and we have

[(C_p^a₀)^m₀ $\times$ (C_p^a₁)^m₁ $\times$ ... $\times$ (C_{p^a_n})^m_n]₀ = 1

For arbitrary k (corresponding to the order p^k) we realize that [(C_p^a₀)^m₀ $\times$ (C_p^a₁)^m₁ $\times$ ... $\times$ (C_{p^a_n})^m_n]_k (which is defined as the number of points with order p^k) is equal to the number of combinations of (j₀, j₁, ..., j_n) for which max((C_p^a₀)^m₀_j₀, (C_p^a₁)^m₁_j₁, ..., (C_{p^a_n})^m_n_{j_n}) = 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₀, j₁, ..., j_n) for which the order of (C_p^a₀)^m₀ $\times$ (C_p^a₁)^m₁ $\times$ ... $\times$ (C_{p^a_n})^m_n 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_{p^a_i})^m_i is less than or equal p^k. Then, because max((C_p^a₀)^m₀_j₀, (C_p^a₁)^m₁_j₁, ..., (C_{p^a_n})^m_n_{j_n}) is only less than or equal p^k when each of the (C_{p^a_i})^m_i_{j_i} is less than or equal p^k, t(k) = s₀(k) s₁(k) ... s_n(k). And that almost brings us home because we already know the structure of (C_{p^a_i})^m_i and therefore know s_i(k)

$s_i(k) = \begin{cases} p^{k m_i} & k \leq a_i \\ p^{a_i m_i} & k \geq a_i \end{cases}$

Using this we find easily that

$t(k) = \begin{cases} p^{k (m_0 + m_1 + ... + m_n)} & k \leq a_0 \\ p^{a_0 m_0 + k(m_1 + ... + m_n)} & a_0 \leq k \leq a_1 \\ p^{a_0 m_0 + a_1 m_1 + k(m_2 + ... + m_n)} & a_1 \leq k \leq a_2 \\ \vdots & \vdots \\ p^{a_0 m_0 + a_1 m_1 + ... + a_n m_n} & k \geq a_n \end{cases}$

And finally, using the fact that for k > 0, [(C_p^a₀)^m₀ $\times$ (C_p^a₁)^m₁ $\times$ ... $\times$ (C_{p^a_n})^m_n]_k = t(k) - t(k - 1) we find

THEOREM 4

$[(C_{p^{a_0}})^{m_0} \times (C_{p^{a_1}})^{m_1} \times \ldots \times (C_{p^{a_n}})^{m_n}]_k = \begin{cases} 1 & k = 0 \\ p^{k(m_0+\ldots+m_n)} - p^{(k-1)(m_0+\ldots+m_n)} & 0 < k \leq a_0 \\ p^{a_0m_0+k(m_1+\ldots+m_n)} - p^{a_0m_0+(k-1)(m_1+\ldots+m_n)} & a_0 < k \leq a_1 \\ p^{a_0m_0+a_1m_1+k(m_2+\ldots+m_n)} - p^{a_0m_0+a_1m_1+(k-1)(m_2+\ldots+m_n)} & a_1 < k \leq a_2 \\ \vdots & \vdots \\ p^{a_0m_0+a_1m_1+\ldots+a_{n-1}m_{n-1}+km_n} - p^{a_0m_0+a_1m_1+\ldots+a_{n-1}m_{n-1}+(k-1)m_n} & a_{n-1} < k \leq a_n \\ 0 & k > a_n \end{cases}$

Let us abbreviate (C_p^a₀)^m₀ $\times$ (C_p^a₁)^m₁ $\times$ ... $\times$ (C_{p^a_n})^m_n with G_p(a₀, m₀, a_a, m₁, ..., a_n, m_n) or even just G_p. The most general structure of a finite, Abelian group is then G_p₀ $\times$ G_p₁ ... $\times$ G_{p_N}. Note that this is possible because of theorem 2 and the fact that the cardinality of all of the G_{p_i} 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₀^k₀ p₁^k₁ ... p_N^k_N where k_i runs over all values from 0 till the a_n of the corresponding G_{p_i}. In other words, we can enumerate the orders with (k₀, k₁, ..., k_N).

Now realize that again the space G_p₀ $\times$ G_p₁ ... $\times$ G_{p_N}_{k₀, k₁, ..., k_N} can be thought of as an N-dimensional space where each of the G_{p_i}_{k_i} are orthogonal subspaces. And the order of the point enumerated by (k₀, k₁, ..., k_N) is just

G_p₀ $\times$ G_p₁ ... $\times$ G_{p_N}_{k₀, k₁, ..., k_N} = lcm(G_p₀_k₀, G_p₁_k₁, ..., G_{p_N}_{k_N}) = G_p₀_k₀ $\cdot$ G_p₁_k₁ $\cdot$ ... $\cdot$ G_{p_N}_{k_N}

where the last equality holds because each of the G_{p_i}_{k_i} = p_i^k_i 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₀, k₁, ..., k_N) represents a different order. The number of points with that order can easily be deduced from the fact that the G_{p_i}_{k_i} are orthogonal subspaces. The number of points having the order G_p₀_k₀ G_p₁_k₁ $\cdots$ G_{p_N}_{k_N} is therefore precisely [G_p₀]_k₀ [G_p₁]_k₁ $\cdots$ [G_{p_N}]_{k_N}. And the formula that describes the number of points with order p₀^k₀ p₁^k₁ ... p_N^k_N for an arbitrary, finite, Abelian group with known structure is given by

[G_p₀ $\times$ G_p₁ ... $\times$ G_{p_N}]_{k₀, k₁, ..., k_N} = [G_p₀]_k₀ $\cdot$ [G_p₁]_k₁ $\cdot$ ... $\cdot$ [G_{p_N}]_{k_N}

where p_i are distinct primes, G_{p_i} = (C_{p_i^a₀ⁱ})^m₀ⁱ $\times$ (C_{p_i^a₁ⁱ})^m₁ⁱ $\times$ ... $\times$ (C_{p_i^a_nⁱ})^m_nⁱ according to which the [G_{p_i}]_{k_i} 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.

Theory: the structure of Abelian groups

Introduction