Group Theory

Groups are a foundational algebraic concept used across many different branches of both pure and applied mathematics. In particular, the ECDSA and newer Schnorr digital signature algorithms used by Bitcoin are based on group theory. I will go over a small amount of the theory here, including the parts that are relevant for the signature algorithms.

Simple examples of groups include the real (or, rational, integer, complex, etc) numbers under the operation of addition, or the nonzero real (or rational, or complex) numbers under multiplication. Generally, a group is a set G together with a binary operator, which I will denote by ‘·’,

G × G → G,

(a, b) ↦ a · b.

For elements a,b of the group, the value a·b is referred to as their product or group product and, for brevity, it is also often written as ab. There are certain algebraic properties or axioms that are required in order for G to be a group. The first is associativity,

(a · b) · c = a · (b · c),

(1)

which must hold for all a,b,c in G. A consequence of associativity is that, when writing a product of more than two group elements, it is not necessary to include parentheses to indicate the order of the operations, since all orders give the same result. For example, for four elements,

abcd = ((ab)c)d = a(b(cd)) = (ab)(cd) = a((bc)d) = (a(bc))d.

The second group axiom is identity. This states that there exists an element I of G satisfying

I · a = a · I = a

(2)

for all a in G. Then I is called the identity element, and is often written simply as 1 (although this can sometimes cause confusion with the number 1, if they are different objects).

The third and final group axiom is the existence of inverses. For any element a, there should exist another element a^-1 satisfying

a-1 · a = a · a-1 = I.

(3)

Then, a^-1 is called the inverse of a.

This completes the mathematical definition of a group. Any set G together with a binary operator satisfying (1,2,3) is a group. However, there is an important sub-category known as commutative or abelian groups satisfying an additional axiom. Two elements a,b of the group are said to commute if,

a · b = b · a.

(4)

Then, a group is abelian or commutative if all pairs of elements commute.

I mentioned above that the real numbers under addition is a group, as is the set of nonzero real numbers under multiplication. In fact, these are abelian groups Some examples of abelian groups are,

1. Any field under the operation of addition. The identity element is 0, and the inverse of an element a is –a.
2. The nonzero elements of any field under the operation of multiplication. The identity element is 1 and the inverse of an element a is 1/a.
3. Any vector space under the operation of addition.
4. Elliptic curves, which I will describe in a later post.
5. For any integer N, the set of integers modulo N under addition is a group.
6. For any integer N, the set of integers coprime to N modulo N is a group under multiplication.

For the final two examples, the integers modulo N can be denoted by ℤ/(N) or, simply, ℤ_N. If, for each integer x, we write [x] for its value modulo N then [x] = [y] if and only if x – y is a multiple of N, which we also write as x = y (mod N). Addition and multiplication modulo N is just the same as integer addition and multiplication, except that we take the result modulo N,

[x] + [y] = [x + y],

[x][y] = [xy].

It is straightforward to show that addition modulo N is a group, with identity [0] and the inverse of [x] is -[x] = [-x]. Multiplication is not a group though, since elements need not have an inverse. In fact, so long as N is nonzero, then [0] has no multiplicative inverse, nor does [x] for any integer x which has a common factor with N. However, if x is coprime to N, then the Euclidean algorithm provides an integer y such that xy – 1 is a multiple of N. This means that [y] is the multiplicative inverse of [x]. The collection of all elements [x] of ℤ_N, for x coprime to N, is written as ℤ_N^* and does indeed form an abelian group under multiplication. In fact, the group ℤ_N^* is used in some cryptographic methods such as RSA.

I will not be concerned with non-abelian groups here, but examples include,

• The space of nxn invertible matrices under matrix multiplication.
• The space of permutations of a set.
• The space of symmetries of a geometric shape.

An important concept in group theory is that of isomorphism. If we have two groups, G and H, then an isomorphism from G to H is an invertible function f mapping G to H which preserves the group operator,

f(a · b) = f(a) · f(b).

If there exists an isomorphism between the groups, then they are said to be isomorphic. In many ways two isomorphic groups can be viewed as being the same group, just with the elements labelled differently. From that viewpoint, f is just mapping one labelling of the group elements to another. A well known example is the exponential function, which takes the group of real numbers under addition to the group of positive real numbers under multiplication,

exp(x+y) = exp(x)exp(y).

This isomorphism is used by logarithm tables in order to convert calculations involving products to the relatively more simple operation of addition. Sometimes, we may be able to prove that an isomorphism exists, but actually computing the map between the groups can be computationally infeasible, or its inverse may be infeasible. Then, although theoretically we could treat the two groups as being the same, we cannot practically convert calculations in one group to the equivalent calculations in the other. This is an important observation for cryptographic algorithms, which rely on the difficulty of computing discrete logarithms.

---

Powers

A group element a raised to a positive integer power n is just a multiplied by itself n times (so that a appears in the product n times),

	n times
	{
an =	a · a · · · a

This satisfies the identities

am + n = aman,

a1 = a,

which can also be used as the defining properties for all integer powers of a, including for the zeroth and negative powers. It can be seen from this that,

a0 = 1,

a–n = (an)-1 = (a-1)n.

The following simple identity holds in any group,

(am)n = amn.

The identity

(ab)n = anbn

holds if a and b commute, but need not hold in general.

The collection of all integer powers of a forms a subgroup of G,

⟨a⟩ = {…, a-2, a-1, 1, a, a2, …}

That is, ⟨a⟩ is a subset of G and forms a group under the same binary operation. In fact, it is the subgroup generated by a or, equivalently, the smallest subgroup containing a. One of the following two possibilities must hold.

1. ⟨a⟩ is infinite. In this case, the powers aⁿ are all distinct for distinct values of n. We say that a has infinite order.
2. ⟨a⟩ is finite. Then, there exists a positive N such that a^N = 1. We say that a has finite order. More specifically, if N is the minimum positive integer satisfying a^N = 1, then we say that a has order N or, equivalently, ⟨a⟩ has size N.

For the finite order case, two powers of a are equal if and only if the exponents are equal modulo the order N. So, we have identities

am = an  iff  m=n (mod N),

aman = am + n.

In fact, this also holds for the infinite order case if we take N = 0, in which case ℤ_N is the same as ℤ. The above identities mean that the map from ℤ_N to ⟨a⟩ given by

[n] ↦ an

is one-to-one and onto, and preserves the group action, so that it maps the sum of two elements in ℤ_N to the group product in ⟨a⟩. This means that the group ℤ_N is isomorphic to ⟨a⟩.

For cryptographic purposes, we generally use a group element whose order is a large prime number, which requires first finding a group whose order (i.e., size) is either a large prime number or a multiple of one. This is because the order of any group element always divides the order of the group.

Theorem 1 If a is an element of a finite group G, then the order of a divides the size of G.

As the order of a is equal to the size of the subgroup ⟨a⟩, theorem 1 is just a special case of Lagrange’s theorem,

Theorem 2 (Lagrange) If H is a subgroup of finite group G, then the size of H divides the size of G.

The ratio between the size of the group and the subgroup is called the index of H in G, and is written as [G:H]. So,

|G| = [G : H] |H|.

For a group element a and integer power n, the equality aⁿ = 1 holds if and only if the order of a divides n, giving an alternative way of stating theorem 1.

Theorem 3 If G is a finite group of size n, then aⁿ = 1 for all a in G.

There are some well known results that are just special cases of theorem 3. For example, Fermat’s little theorem. This states that if p is a prime number and a is an integer not divisible by p then,

ap – 1 = 1.  (mod p)

This follows from the fact that ℤ_p^* under multiplication is a group of size p – 1, so [a]^p – 1 = [1]. In fact, the more general Euler’s theorem is also a special case of theorem 3. For positive integer N, we let φ(N) be Euler’s totient function, equal to the number of integers in the range 1 to N which are coprime to N. This is just the size of the group ℤ_N^* and, hence, [a]^φ(N) = 1 for all integers a coprime to N. Equivalently,

aφ(N) = 1.  (mod N)

This is the statement of Euler’s theorem and, when N = p is prime, we have φ(p) = p – 1 so that it reduces to Fermat’s little theorem.

I noted above that, if we want a group to contain an element of prime order p, then the size of the group must be a multiple of p. The converse to this statement holds, so that if the size of a group is a multiple of p then it does contain an element of order p. This is Cauchy’s theorem.

Theorem 4 (Cauchy) A finite group G has an element of prime order p if and only if its size is a multiple of p.

---

Cyclic Groups

A group is said to be cyclic if it is generated by a single element. To be more explicit, an element g of a group G generates the subgroup ⟨g⟩ of integer powers of g. If this subgroup is the whole group, G = ⟨g⟩, then G is cyclic and g is a generator. Equivalently, every element of G is an integer power of g. Since multiplying powers of a single element commutes,

gmgn = gm + n = gn + m = gngm,

cyclic groups are automatically abelian. We can go further and describe all cyclic groups up to isomorphism.

Theorem 5 Let G be a cyclic group with generator g. Then, either,

• G is isomorphic to the integers ℤ under addition. This is true whenever G is infinite, and the isomorphism is given by,
  

  ℤ → G,

  n ↦ gn.

• For some positive integer N, G is isomorphic to the integers modulo N under addition, ℤ_N. This is true whenever G is finite of size N, and the isomorphism is given by,
  

  ℤN → G,

  n ↦ gn.

The infinite cyclic groups described in the first point of theorem 5 can also be described in the same way as for the finite groups in the second point, simply by taking N to be zero. This is because the integer arithmetic modulo 0 is just standard integer arithmetic.

Corollary 6 If G is a cyclic group with generator g, then there is a unique nonnegative integer N such that it is isomorphic to ℤ_N under addition. The isomorphism can be defined by

ℤN → G,

n ↦ gn.

So, all cyclic groups are, up to isomorphism, of the form ℤ_N under addition. If this is the case, you may wonder why we would be interested in any other cyclic groups. The reason is that, although the isomorphism described above exists in theory, it can be computationally impractical to calculate. Given an element a of the group G, the isomorphism requires finding an integer n satisfying gⁿ = a, known as the discrete logarithm problem.

A cyclic group generated by an element of order n is of size n. For groups whose size is prime, the converse holds. Finding a cyclic group generated by an element of prime order p is the same as finding a group of size p.

Theorem 7 Every finite group G whose size is prime, is cyclic. Furthermore, every element of G besides the identity is a generator.

Given what we already know from above, this result is straightforward to prove. If G has size p then the order of any element g must divide p so, by primality, is equal to 1 or p. If the order was 1 then g = g¹ = 1 would be the identity. Otherwise, if it is of order p then ⟨g⟩ has size p and, so, is all of G.

---

Computing with large exponents

The groups used in cryptographic algorithms are usually finite, but very large. For example, the ECDSA and Schnorr signature algorithms used by Bitcoin are cyclic of size a 256 bit prime number. It is then necessary to raise elements of the group by exponents up to this order, so it is usual to have exponents which are themselves 256 bit numbers. At first sight, it might seem impractical to compute with such huge powers. If we were to do this by trying to multiply the element by itself up to 2²⁵⁶ times, then it would be impossible even with the all the computing power in the world and the entire age of the universe to perform the calculation in. Actually, with some simple manipulations, it is easy for a computer to handle exponents of such large sizes. The idea is that if we want to compute a group element a raised to some very large power n, then it can be expressed recursively as,

an =	{	(an/2)2,	if n is even,
		(a(n - 1)/2)2a,	if n is odd.

The right hand side only involves one or two group multiplications and a raised to a power of no more than n/2. If, to start with, n had 256 binary digits, so is bounded by 2²⁵⁶ then, 256 iterations of the above expression is sufficient to compute the power.

The process of computing the n‘th power can also be expressed more explicitly in the following way, although it is effectively the same as applying the recursive formula above. We start by iteratively computing the power-of-2 powers of a,

a20 = a,

a21 = aa,

a22 = a2a2,

⋯

a2d = a2d - 1a2d - 1.

Computing all the powers up to a^2d in this way only takes d applications of the group operator. Now, if n is less than 2^d + 1 (i.e., has d + 1 binary digits), by binary expansion we can write

n = 2r1 + 2r2 + ⋯ + 2rm

for m ≤ d + 1 distinct nonnegative integers r_k ≤ d. Writing

an = a2r1a2r2⋯a2rm

we can compute the nth power by substituting in the power-of-2 powers in this product. Note that the total number of group operations in the product is no more than d, so we require no more than 2d group multiplications in total.

Number of applications of group operator ≤ 2log2n

Computing powers with 256 bit exponents then requires at most 510 actual group multiplications, which is very easily performed on a computer. This means that the isomorphism described in corollary 6 is easily computed, even if its inverse is computationally impossible.

The calculation described here does not really require any of the properties of a group other than associativity. For example, we can compute large integer powers of any integer a modulo N which, if a and N are not coprime, is not a group operation. Python3 uses variable length integers by default, so handles numbers of the order of 2²⁵⁶ with no problem. The function pow(a, n, N) computes a to the n‘th power modulo N, and handles 256 bit exponents with no problems.

---

Additive Groups

Sometimes groups are written additively. This is no different to the theory described above, being just a slightly different notational convention. For an additive group, the group operation is written with the symbol ‘+’. Then, for two group elements a and b, we write a + b for the group sum. We no longer refer to the group product, using the word sum instead, and no longer use the shorthand ab. The group identity is commonly written as ‘0’ (rather than 1), or similar, and the additive inverse of an element is written as –a rather than a^-1. By convention, additive groups are always abelian, so the group axioms (1,2,3,4) are,

(a + b) + c = a + (b + c),

a + b = b + a,

a + 0 = a,

–a + a = 0.

We also usually write a – b to mean a + (-b). The value of a group element a raised to an integer power n is, in the case of additive groups, described as the product of n and a or as n times a or n multiplied by a. It is also written multiplicatively as n.a or na instead of exponentially as aⁿ. So, for positive integer n,

	n times
	{
n · a =	a + a + ⋯ + a

The defining properties for all integer n are, with his notation,

(m + n).a = m.a + n.a,

1.a = a.

The additional algebraic properties described above are now written as,

0.a = 0,

(-n).a = -(n.a) = n.(-a),

m.(n.a) = (mn).a,

n.(a + b) = n.a + n.b.

When working exclusively with abelian groups, the additive notation is common. However, often it is necessary to switch between the two. This can occasionally cause some odd terminology, such as the discrete logarithm problem being a ‘division’ problem when using additively expressed groups. This is entirely down to notation, so should not cause any problems to anyone who understands this.