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.
- Equivalence relation: An equivalence relation on a set
is a subset
that satisfies three properties:
- Reflexivity:
- Symmetry:
- Transitivity:
- Reflexivity:
- 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:
- let
and
be two equivalence classes on
that share an element
in common. Hence
and
- Let
be any other element of
Hence
- Since
then
(by the symmetry property). And since
and
then
(by the transitivity property).
- 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
- let
-
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:
- Reflexivity: Let
denote the identity element of
Since
is a subgroup of
is also the identity element of
and
Consequently,
- Symmetry: Let
such that
We know that
such that
Moreover, since
is a subgroup,
must admit a unique inverse
This implies that
Therefore,
- 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.
- 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.
- Let
-
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.
- Let
- 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
If
divides
then
for some integer
Consequently,
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
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
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.
- Let
- 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.
- Suppose that (
- 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.
- Recall that result #3 stated that in a finite cyclic group
- 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
1
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 gcd
gcd
- 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.
- Since
- 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: finite field, Group
No comments
Comments feed for this article
Trackback link: https://delfr.com/theoretical-minimum-group-finite-fields/trackback/