# Groups and Finite Fields – Crypto Theoretical Minimum

Download pdf here: Groups and Finite Fields

## 1. Introduction

Group, field and elliptic curve theories make a regular appearance in the study of crypto-assets including but not limited to cryptocurrencies. For example, the security strength of a number of crypto-specific primitives relies on the math of elliptic curve groups over finite fields. These groups constitute a robust infrastructure to generate adequate public keys from private ones.

Groups and fields are foundational pillars of modern algebra. While in elementary algebra we rely on common arithmetic operations (e.g., addition and multiplication of real numbers), in modern algebra we raise further the level of abstraction. In particular, we introduce more general counterparts to real number addition and multiplication and define them over more general sets. An important objective is to study the common properties of all sets on which a fixed number of operations are defined. These operations tend to be interrelated in some definite way (e.g., distributivity of multiplication over addition).

In this post, we provide a concise (but by no means comprehensive) introduction to group and finite-field theory at the level needed to better appreciate the mathematical foundation of crypto assets. In a subequent post we build on this material to introduce elliptic curve groups defined over finite fields. The interested reader could consult e.g., [1] for a deeper dive on the theory of finite fields and its applications.

## 2. Groups – Axiomatic formulation

A group is a set together with a binary operation on such that satisfies the following properties:

• A.1 Associativity:
• A.2 Existence of identity: such that we have
• A.3 Closure:
• A.4 Existence of inverse: an element such that We say that is the inverse of in

If in addition, the group satisfies the commutativity property:

the group is called abelian.

The aforementioned four axioms have an equivalent formulation in which the closure and existence of inverse properties get substitued with the permutation property. The axiomatic formulation becomes:

• A.1 Associativity:
• A.2 Existence of identity: such that we have
• B.3 Permutation: the set is a permutation of

Proof (): For a fixed , consider the map

Proving that the permutation property holds is equivalent to showing that the map is a bijection such that the domain and the range are one and the same. To see this, note that

• (by the closure property). Hence
• is surjective: This is clear from the definition of since any element of its range is of the form for some and hence admits as a pre-image.
• is injective: Suppose that for some The existence of inverse property, coupled with the associativity property allow us to write

Proof (): If , then by definition. Since the permutation property holds, then is a permutation of and so Consequently, the closure property holds.

Proof (): If is a permutation of then by the existence of identity property it necessarily contains the identity element of Consequently, such that In order to demonstrate that the existence of inverse property holds, we still have to show that To do so, consider the set . By the permutation property, we know that is a permutation of and so such that By invoking the associativity property, we can write

(Q.E.D.)

The alternative axiomatic definition paves the way to a convenient representation of a group using a Cayley table. Let The Cayley table is simply:

One can observe that the row in the table above is none other than which corresponds to a specific permutation of

Uniqueness results

• The group identity element is unique. To see why, suppose there exists a group with two identity elements and By definition of , it must be that Moreover, by definition of it must be that As a result, we must have have
• Similarly, the inverse of a group element is unique. To prove it, we make use of the associativity and existence of inverse properties. Let and suppose that it admits two inverses and It must be that

And so we can write:

## 3. Group examples

Group examples abound. In this post, we limit ourselves to two examples of particular importance: the group of integers modulo and the group of powers of an arbitrary element of some group. The importance of the former is partly derived from its role in building the canonical example of a finite field whenever is a prime number (see section 8 below). Finite fields are of great significance in crypto in particular because the Discrete Logarithm (DL) problem is thought to be hard on their multiplicative subgroup. This intractability is at the heart of the security strength of a vast number of crypto primitives. The importance of the latter example comes from its crucial role in the study of cyclic groups, regularly used in the context of crypto.

Example 1: The group of integers modulo

In order to define the group’s underlying set and corresponding binary operation, we will need to introduce the notions of equivalence relation, equivalence class, and modulo arithmetic.

1. Equivalence relation: An equivalence relation on a set is a subset that satisfies three properties:
• Reflexivity:
• Symmetry:
• Transitivity:
2. Equivalence class: We let denote the set and refer to it as the equivalence class of the element under the equivalence relation The set of equivalence classes forms a partition of . To see why, note the following:
• covers : (by the reflexivity property), hence As a result, belongs to at least one equivalence class.
• Equivalence classes are disjoint:
1. let and be two equivalence classes on that share an element in common. Hence and
2. Let be any other element of Hence
3. Since then (by the symmetry property). And since and then (by the transitivity property).
4. We also know that Using the transitivity property on and we conclude that As a result,

Similarly, we can show that any element of is also an element of

3. Modulo arithmetic: One says that a positive integer is congruent to another positive integer modulo if divides An equivalent statement would be that and have the same remainder upon division by We denote this by

We are now in a position to define our first group example. Consider the set of integers. define a binary relation on as follows:

One can easily see that satisfies all three properties of an equivalence relation. We can therefore define equivalence classes on under the equivalence relation We denote by the equivalence class of By definition of , we have:

Note that is equivalent to for all The equivalence classes associated with the equivalence relation form a partition of and can be listed as follows:

We let and define the binary operation on a tuple as follows:

where denotes regular addition of integers.

This relationship does not depend on a particular element within a given equivalence class. Indeed, let be any element of and any element of where and are elements of Applying the binary relation on the equivalence classes and yields:

We claim that is an abelian group. To prove this, we show that it satisfies the group axioms:

• Associativity: Let We can write

(by associativity of )

• Existence of identity: Let Clearly Moreover, we have

Similarly, we can check that Hence satisfies the attributes of the identity element.

• Closure: Let By definition of , we have And since the set forms a partition of we can be confident that corresponds to exactly one element of this set and hence
• Existence of inverse: we have Similarly, we can conclude that Noting that we conclude that each element of admits an inverse that is also an element of
• Commutativity: By definition of we have

Example 2: The group of powers of an arbitrary element of some group

Let be a group and Consider the set of all powers of defined as

where ( times)

We claim that is a group. To prove it, we show that satisfies the group axioms.

• Associativity: Let and be elements of . We get the following equalities:

(by definition of power)

(by associativity of +)

• Existence of identity: Note that since is finite, and since all powers of are elements of (because of the closure property of ), the powers of cannot yield different elements ad infinitum. Consequently, there must exist a least integer such that for some We claim that is the identity element of To see why, let be any element of We can write

(by definition of power)

(since )

(by definition of power)

Similarly, we can show that Since was arbitrary in we conclude that satisfies the properties of an identity element.

• Closure: Let be two elements of By the definition of power of we get This is clearly a power of and therefore an element of
• Existence of inverse: Let be an arbitrary element of Recall that the identity element of is equal to Since we can always find a least integer such that We get:

( times)

Since , we conclude that and qualifies as the inverse of

## 4. Subgroups, cosets and Lagrange’s theorem

Given a group and a subset we say that a subgroup of if is a group. A subgroup is mandated to be a group with respect to the same operation of the parent group. A direct consequence is that the identity element of is the same as that of Clearly, the power group previously introduced, is a subgroup of for all

If is a subgroup of one can define a relation on as follows:

such that

is an equivalence relation on because it has all three desired properties:

1. Reflexivity: Let denote the identity element of Since is a subgroup of is also the identity element of and Consequently,
2. Symmetry: Let such that We know that such that Moreover, since is a subgroup, must admit a unique inverse This implies that Therefore,
3. Transitivity: Let such that We know that such that and Consequently, By associativity of on we get Since is a group, the closure property guarantees that Hence with and so

The equivalence relation on induces a partition of into non-empty equivalent classes called left cosets of modulo For we denote its corresponding equivalence class by:

By virtue of being a group, satisfies the permutation property i.e., is a permutation of . A direct consequence is that for any subset will also be a permutation of In particular, is a permutation of This shows that every left coset of modulo has the same cardinality as We now state and prove a foundational theorem of group theory known as Lagrange’s theorem.

Lagrange’s theorem: The order of (i.e., the number of elements conained in) any subgroup of a group divides the order of

Proof: Consider the equivalence classes generated by the relation as previously defined. The classes form a partition of Moreover, they all contain the same number of elements as (as we just proved). We can then write:

order = (# of equivalence classes generated by ) order. Q.E.D

## 5. Cyclic groups

Cyclic groups play a fundamental role in in the construction of secure cryptographic primitives used in e.g., cryptocurrencies. For one thing, a generator of a cyclic group is usually used as a base point to build public keys out of private ones. But most importantly, the security of a number of crypto primitives relies on the presupposed intractability of the Discrete Logarithm problem (DL) on certain cyclic groups. These include e.g.,

• The multiplicative cyclic group of a finite field of large prime order
• An appropriately chosen cyclic subgroup of an elliptic curve group

We say that a group is cyclic if and only if it can be generated by at least one of its elements, called a generator. In other words:

A group is cyclic such that

In what follows, we state and prove relevant results about cyclic groups in general.

1. Any group of prime order is cyclic and can be generated by any of its non-identity elements

Proof:

• Let be a group and a prime number such that order
• By Lagrange’s theorem, the order of any subgroup of must divide As a result, the order of any subgroup of can either be equal to or to
• The singleton consisting of ‘s identity element yields the subgroup whose order is equal to 1. It is called the trivial subgroup.
• Any other subgroup of must be of order at least 2 because at a minimum, it must contain a non-identity element in addition to the identity.
• Consequently, the order of any subgroup of other than the trivial subgroup must be equal to
• In particular, the subgroups generated by each non-identity element must have an order equal to Therefore it must be that is a generator of i.e., Q.E.D.
2. Every subgroup of a cyclic group is cyclic

Proof:

• Let be a cyclic group. Hence such that Let be a subgroup of
• Either or contains at least one positive power of If then it is clearly cyclic. Otherwise, let be the least positive exponent such that We show that is cyclic by demonstrating that
• By definition, we have the following equivalences:

where is a positive power of

where is a positive mutiple of

• Since is a subset of anyone of its elements must be of the form where is a positive integer greater than or equal to
• Suppose however that is not a multiple of . We can write with and This implies that
• By virtue of being an element of admits an inverse The closure property implies that both and are elements of One can also easily verify that is the inverse of We then write:

• Noting that and are both elements of we conclude that
• But being the remainder of the division of by This contradicts the fact that is the least positive integer such that Consequently, we conclude that must be a multiple of
• Coupled with the fact that is of the form for some positive integer greater than or equal to we conclude that Q.E.D.
3. In a finite cyclic group of order the element generates a subgroup of order

Proof:

• Let gcd
• It is easy to see that the order of corresponds to the least integer such that (where is the identity element of the group). Similarly, is the least integer that satisfies
• We claim that divides
1. If divides then for some integer Consequently,
2. Suppose with not a multiple of i.e., where and This implies a contradiction since is the least integer that satisfies
• Next, we claim that divides divides
1. If divides then divides (note: and are both integers since gcd). Since gcd the integers and do not share a common divisor greater than 1. But divides and so it must be that divides
2. If divides it must be that divides But gcd and so divides As a result, divides
• The previous two equivalences prove that

divides

Recall that is the least integer that satisfies The equivalence then dictates that must be the least integer such that divides Consequently, it must be that Q.E.D.

4. In a finite cyclic group of order for any positive divisor of contains one and only one subgroup of order

Proof:

Existence: Consider the subgroup generated by the element (note that is an integer since is a divisor of ). By result #3 above, the order of must be equal to which is equal to This shows that (,*) admits at least one subgroup of order

Uniqueness:

• Suppose that (,*) has another subgroup of order By result #2 above, every subgroup of a cyclic group is cyclic. Therefore, this other subgroup of order must be cyclic and hence generated by a certain power of
• By result #3 above, it must be that order Consequently, gcd
• This shows that divides which allows us to write for some And so
• Since we conclude that is a subgroup of But recall that and have the same order, and so they must be the same group. Q.E.D.
5. Let be a finite cyclic group of order and a divisor of Then contains elements of order Moreover,

Note 1: The order of an element of a group is the order of the subgroup generated by that element.

Note 2: denotes the Euler’s totient function applied to which evaluates to the number of integers that are relatively prime to (i.e., integers that satisfy gcd).

Proof:

• Recall that result #3 stated that in a finite cyclic group of order the element generates a subgroup of order
• Therefore, if we’re given an integer that divides one can identify the integers such that gcd and conclude that each generates a subgroup of order equal to This implies that the total count of such ‘s corresponds to the number of elements in that generate a subgroup of order
• Since divides let so that As a result, the number of elements in that generate a subgroup of order is equal to the number of integers such that gcd
• we know that is a multiple of gcd In particular, for each valid we can write where and As a result, the number of elements in that generate a subgroup of order is equal to the number of integers of the form such that and gcd
• Next, note the following equivalences:

gcd gcd
gcd

We then conclude that the eligible integers of the form are those that correspond to integers such that is coprime to This is none other that

• Finally, by result #4 above, we know that in a finite cyclic group of order there exists one and only one subgroup of order for every divisor of Moreover, each element of the cyclic group belongs to one and only one subgroup. Consequently, Q.E.D.
6. A finite cyclic group of order contains generators. The generators, are the powers of such that gcd

Proof: This is a special case of result #5 above, applied when

## 6. Group isomorphism

When comparing the structures of two groups, the mappings between them that preserve their respective operations take on an important role.

Given groups and a mapping is called a homomorphism of into if it preserves the operation of That is:

In the context of crypto, an important application of group homomorphism takes the form of a Pedersen Commitment. In Monero for example, Pederson Commitments are used to hide the value of a transaction (refer to Part 8 of the Monero series for a detailed explanation).

If is also bijective, then it is called an isomorphism. In this case, and can be thought of as equivalent. Group isomorphisms are a special instance of the more general theory of categories and functors. The objective of the theory is to elucidate structural similarities that exist between various areas of mathematics. On a more subjective note, it may be one of the most beautiful theories of mathematics. For a very concise yet clear introduction, the interested reader may consult section 10 of [2].

## 7. Fields – Axiomatic formulation

Fields are algebraic structures that generalize arithmetics that we are used to on More specifically, a field is a set endowed with the notions of addition and multiplication as well as with their respective inverses subtraction and division.

Formally, a field is a set with at least two elements and two binary operations and such that:

• is an abelian group. We denote its identity element by 0.
• satisfies the 1) Associativity, 2) Existence of identity, 3) Closure, and 5) Commutativity group axioms. However, is not a group since the Existence of inverse axiom is not observed for all elements of More specifically, the additive identity element 0 is not required to admit a multiplicative inverse.
•  0 is an abelian group. This means that by removing the additive identity element 0, the resulting set becomes an abelian group under multiplication. We denote its identity element by 1. This group is known as the field’s multiplicative group (it turns out that it is also cyclic, but we will not prove it in this post).
• Distributivity of over : we have

It is common to refer to as the field’s addition and to as the field’s multiplication.

One implication of the aforementioned axioms is that  0  0. To see this, note the following:

1  0  1  0  0

Being an element of admits an additive inverse (i.e., with respet to ). As a result of cancelling from each side of the above equality, we get 0  0.

The order of is the number of elements that it contains. is called a finite field if its order is finite. The theory of finite fields is rich and beautiful. One of its most important results states that finite fields can only have orders of the form where is any prime number and any positive integer. Moreover, it turns out that all fields that contain the same number of elements are equivalent.

To understand and better appreciate the canonical example of a finite field of order one will need to study prime polynomials over finite fields, which is out of scope. Nevertheless, we will introduce the case of corresponding to the most basic type of a finite field, namely the field It is the canonical example of finite fields of prime order

## 8. The field of integers modulo p

Let and be as defined in section 3 when we introduced the abelian group of integers modulo Recall that

• where and
• is defined on to be where denotes regular addition of integers.

We introduce a multiplicative operation on denoted by and defined as follows:

where denotes regular multiplication of integers

Note that this relationship does not depend on a particular element within a class. Indeed, let be any element of and any element of for and elements of Applying the binary relation on the equivalence classes and yields:

We claim that is a field if and only if is prime.

Suppose were not prime. We will show that would fail to satisy the closure axiom and as a result, would not be a group. Indeed, since is composite, we can write Clearly, and are elements of However,

Q.E.D.

Let where is a prime number. We have:

is an abelian group: We previously proved in section 3 that this result holds for any positive integer and so holds true in particular when is a prime. Its identity element is  0.

satisfies the 1)Associativity, 2) Existence of identity, 3) Closure, and 5) Commutativity group axioms:

• Associativity: Let and notice that:

Q.E.D.

• Existence of identity: We claim that is the identity element. Clearly, Moreover, we have

and Q.E.D.

• Closure: Let By definition of we have And since the set forms a partition of we can be confident that corresponds to exactly one element of this set and hence Q.E.D.
• Commutativity: we can use the commutativity of regular multiplication on integers to conclude that

Q.E.D.

is an abelian group. We prove that it satisfies all five group axioms:

• Associativity: We previously proved associativity in which automatically implies associativity in
• Existence of identity: We previously showed that is the identity element in . This also implies that is the identity element in
• Closure: Let Since is prime, then If this were not true, one would be able to write for some positive integer And since is prime, it must be that boh and divide Hence divides implying that This results in being strictly greater than a contradiction. Consequently and so Q.E.D.
• Existence of inverse: Our purpose is to show that such that 1 Note that is equivalent to which in turn is equivalent to It turns out that when and are relatively prime, such an always exists. To prove this, we make use of the following theorem

Theorem: Given gcd such that

A corollary to the theorem is that if and are relatively prime, then one can find integers and such that In our case, we know that and are relatively prime because is prime and As a result, the theorem leads us to conclude that such that This in turn, proves that admits an inverse equal to

Proof:

• Since we can write with
• Next, note that gcd gcd To see this, observe that gcd divides and and hence must divide As a result, gcd must divide gcd Similarly, gcd divides and and hence must divide As a result, gcd must divide gcd Hence gcdgcd
• So instead of finding gcd one can find gcd We now write with and conclude that gcd gcd
• Repeating the above step and noting that the remainder is always a non-negative integer strictly less than the divisor, we eventually reach the case where after iterations. And so we get

gcd gcd gcd gcd

• Noting that is a linear combination of and and that is a linear combination of and we conclude that gcd is itself a linear combination of and (One can conduct a back-substitution process to find the values of the coefficients, also known as Bézout coefficients). Hence and admits an inverse in equals to Q.E.D.
• Commutativity: We previously proved commutativity in which automatically implies commutativity in

Distributivity of over : let Then

Q.E.D.

## References

[1] R. Lidl and H. Niederreiter. Introduction to Finite Fields Cambridge University Press, 1986.
[2] L. W. Tu. An Introduction to Manifolds. Springer, 2010.

Tags: ,

## No comments

Comments feed for this article