# Elliptic Curve Groups

By [Bless Hukporti](https://paragraph.com/@bless-hukporti) · 2024-07-10

---

The goal of this research based article is to help us understand group theory the backbone of cryptography. This would be a primer for further study on elliptic curve groups, BLS signatures, zkSNARKS, and amongst others.

**Goals**

1.  **Understanding groups**
    
2.  **Understanding fields, finite fields, generators and the discrete logarithm problem**
    
3.  **Elliptic curve groups**
    

Group theory as we all know is a branch of mathematics that studies algebraic structures known as groups. The concept of a group is central to abstract algebra and has applications in various fields such as physics, chemistry, and computer science. Group theory is very fundamental in cryptography.

Understanding group theory gives you a strong fundamental understanding of the math behind cryptography and zk proofs. Before reading further I assume you have refreshed yourself with basic modular arithmetic. If not I would advice you refresh yourself on it before continuing.

You will see me using these quite a lot

∈ which means belongs to

∀ which means For all or for any

∃ which means there exists

↦ which also means maps to

Now that you know these we’re now set to roll.

### Definition of a Group

A group $$( G )$$ is a set with a single binary operation (usually called multiplication, but it could be any operation such as addition) that satisfies four fundamental properties : closure, associativity, identity, and invertibility (inverse).

or

Let G be a non-empty set together with the operation \* is said to be a group if the following conditions or axioms are satisfied:

1.  Closure: For all a and b which belong to the non-empty set G, there exists the product of a and b which also belongs to the non-empty set G. Expressed mathematically as ∀ a, b ∈ G ∃ a \* b ∈ G.
    
2.  Associativity: For all, ∀ a, b, c ∈ G , (a \* b) \* c = b \* (a \* c)
    
3.  Identity: For all, ∀ a ∈ G there exists some element e such that a \* e = e \* a = a
    
4.  Inverse: For all, ∀ a ∈ G there exist some element b ∈ G such that a \* b = b \* a = e
    

If these four conditions hold then the non-empty set together with the operation \* is said to be a group.

### Types of Groups

Groups can be classified in several ways based on additional properties they may have.

1.  **Abelian (or Commutative) Groups**: A group $$( G )$$ is called Abelian if the operation is commutative, i.e., for all $$( a, b ∈ G )$$: $$ a \\cdot b = b \\cdot a$$
    
2.  **Finite and Infinite Groups**: Groups can have a finite number of elements (finite groups) or an infinite number (infinite groups). The number of elements in a group is called the order of the group.
    
3.  **Cyclic Groups**: A group is cyclic if there exists an element $$( g ∈ G )$$ such that every element of the group can be written as $$( g )$$ raised to some integer power. This $$( g )$$ is called a generator of the group.
    
4.  **Subgroups**: A subgroup $$( H )$$ of a group $$( G )$$ is a subset of $$( G )$$ that is itself a group under the operation defined on $$( G )$$.
    
    Remark: The operation \* is mostly a binary operation i.e. \* is a map \* : $$G ↦ G$$.
    
    Alternatively \* takes in two elements in G and produces a third element in $$G$$.
    

### Examples of Groups

1.  **The Integers under Addition**: The set of integers ℤ with the operation of addition is an infinite Abelian group. The identity element is 0, and the inverse of any integer n is -n.
    
2.  **Symmetric Group**: The set of all permutations of a finite set {1, 2, …, n} forms a group under the operation of composition of permutations. This group is called the symmetric group.
    

Now that we know what a group is and its characteristics, let solve some problems.

**Prove whether the additive integers mod 6 is a group.**

Answer

Now based on the definition of groups above, we need to show that the members or elements of the additive integer mod 6 is

1.  Closed under the operation \*
    
2.  Associative under the operation \*
    
3.  Has an identity element
    
4.  Has an inverse
    

We let G = the set of elements of the additive integer mod 6. The set of elements of the additive integer mod 6 are G = { 0, 1, 2, 3, 4, 5 }.

Now proving that it is closed under the operation \* i.e. ∀ a, b ∈ G ∃ a \* b ∈ G. We let a = 2, b = 5 ∈ G. Now 2 \* 5 = ( 10 mod 6 ) = 4 ∈ G . Since 4 is in the set G the first condition is satisfied.

Proving that the non-empty set G is associative i.e. ∀ a, b, c ∈ G , ( a \* b ) \* c = b \* ( a \* c ). We let a = 2, b = 5 and c = 1, ∈ G. Now ( 2 \* 5 ) \* 1 = 5 \* ( 2 \* 1 ) which is equal to ( 10 mod 6 ) = ( 10 mod 6 ) which is 4 ∈ G. Hence associativity holds.

Proving that there exist an identity element in G i.e. ∀ a ∈ G there exists some element e such that a \* e = e \* a = a. We let a = 2 ∈ G now we want an element that when we multiply it to a we get the same value of a. Not that generally the multiplicative identity of any element is 1, hence e = 1. This implies that 2 \* 1 = 1 \* 2 = 2 ∈ G. Hence identity element exists.

Proving that there exists a multiplicative inverse in G i.e. ∀ a ∈ G there exist some element b ∈ G such that a \* b = b \* a = e. Here we realize that G has no inverse under mod 6 because there is no two element in G when we multiply them we get e.

Hence since the fourth condition is not satisfied the set G is not a group.

**Fields**
----------

Fields are fundamental algebraic structures that generalize the familiar concepts of arithmetic operations like addition, subtraction, multiplication, and division.

Fields are set of elements that are abelian under + and \* operation and has the distributive property.

Abelian groups are groups that are commutative, i.e. ∀ a, b ∈ G if a \* b = b \* a ∈ G then G is an abelian group.

### Examples of Fields

1.  **Rational Numbers (ℚ**): The set of rational numbers with the usual addition and multiplication operations is a field.
    
2.  **Real Numbers (ℝ**): The set of real numbers with standard addition and multiplication forms a field.
    
3.  **Complex Numbers (ℂ**): The set of complex numbers is a field under the usual operations of addition and multiplication.
    
4.  **Finite Fields**: Fields with a finite number of elements are called finite fields or Galois fields. The simplest example is the field with two elements, $$( \\mathbb{F}\_2 = {0, 1} )$$, where the operations are defined modulo 2.
    

### FINITE FIELDS

Finite fields, also known as Galois fields (after the mathematician Évariste Galois), are fields that contain a finite number of elements.

A finite field is a commutative ring with only finitely many elements. For example, $$Z/pZ$$ with p prime is a field, which we denote $$Fp$$. Let take a quick look on the properties of finite fields.

### Basic Properties of Finite Fields

1.  **Order of a Finite Field**:
    
    *   The number of elements in a finite field is called its order. If a finite field $$( F )$$ has $$( q )$$ elements, we say that the order of $$( F )$$ is $$( q ).$$
        
    *   A fundamental result is that the order $$( q )$$ of a finite field is always a power of a prime number. Hence, $$( q = p^n ),$$ where $$( p )$$ is a prime number (called the characteristic of the field) and $$( n )$$ is a positive integer.
        
2.  **Existence and Uniqueness**:
    
    *   For each prime power $$( q = p^n ),$$ there exists a finite field with $$( q )$$ elements, denoted $$( GF(q) ).$$
        
    *   All finite fields of a given order are isomorphic, meaning there is essentially only one finite field of each order up to isomorphism.
        

### Structure of Finite Fields

1.  **Prime Fields**:
    
    *   The simplest finite fields are those with $$(p)$$ elements, where $$( p )$$ is a prime number. These fields are denoted $$( \\mathbb{F}\_p ) or ( GF(p) ).$$
        
2.  **Extension Fields**:
    
    *   For $$( q = p^n ),$$ the field $$( \\mathbb{F}\_{p^n} )$$ is an extension field of $$( \\mathbb{F}\_p )$$. It contains $$( p^n )$$ elements and can be constructed using a polynomial $$f(x)$$ of degree $$( n )$$that is irreducible over $$( \\mathbb{F}\_p )$$.
        

### Arithmetic in Finite Fields

1.  **Addition and Multiplication**:
    
    *   Addition in a finite field is performed element-wise, modulo the characteristic $$( p )$$.
        
    *   Multiplication is performed using polynomial arithmetic, followed by reduction modulo the irreducible polynomial $$f(x).$$
        
2.  **Inverses**:
    
    *   Every non-zero element in a finite field has a multiplicative inverse. The inverse can be found using the Extended Euclidean Algorithm.
        

### Examples of Finite Fields

1.  **Field with 4 Elements**:
    
    *   $$( \\mathbb{F}\_4 )$$ can be constructed using the polynomial $$( x^2 + x + 1 )$$ over $$( \\mathbb{F}\_2 )$$.
        
    *   Elements can be represented as $$( {0, 1, \\alpha, \\alpha + 1} ),$$ where $$( \\alpha )$$ is a root of the polynomial.
        

### Construction of Finite Fields

1.  **Using Polynomials**:
    
    *   To construct $$( \\mathbb{F}\_{p^n} )$$, one needs an irreducible polynomial of degree $$( n ) over ( \\mathbb{F}\_p ).$$
        
    *   For example, to construct $$( \\mathbb{F}\_4 )$$, one can use the polynomial $$( x^2 + x + 1 )$$ over $$( \\mathbb{F}\_2 )$$.
        
2.  **Representation of Elements**:
    
    *   Elements of $$( \\mathbb{F}\_{p^n} )$$ can be represented as polynomials of degree less than $$( n )$$ with coefficients in $$( \\mathbb{F}\_p )$$.
        

### Generators in Group Theory

A generator of a group is an element from which every other element of the group can be derived by repeatedly applying the group operation (and its inverse, if applicable). A group can have one or more generators.

1.  **Cyclic Groups**:
    
    *   A group $$( G )$$ is cyclic if there exists an element $$( g \\in G )$$ such that every element in $$( G )$$ can be written as $$( g^n )$$ for some integer $$( n ).$$ This element $$( g )$$ is called a generator of the cyclic group.
        
    *   The cyclic group generated by $$( g )$$ is denoted $$ \\langle g \\rangle .$$
        
    *   For example, the integers under addition, $$(\\mathbb{Z}, +)$$, form a cyclic group with 1 as a generator since every integer can be written as $$( n \\cdot 1 )$$ where $$( n \\in \\mathbb{Z} ).$$
        
2.  **Multiple Generators**:
    
    *   Not all groups are cyclic, and some groups require more than one generator.
        
    *   For example, the Klein four-group $$( V = {e, a, b, ab} )$$ can be generated by the elements $$( a )$$ and $$( b )$$ since $$( e = aa )$$ and $$( ab )$$ are already in the group.
        

### Generators in Finite Fields

In the context of finite fields (or Galois fields), generators are related to the multiplicative group of the field.

1.  **Multiplicative Group of a Finite Field**:
    
    *   The non-zero elements of a finite field forms a cyclic group under multiplication.
        
    *   A generator of this multiplicative group is an element $$( g )$$ such that every non-zero element of the field can be written as $$( g^n )$$ for some integer $$( n )$$.
        
    *   For instance, in the field $$( \\mathbb{F}\_7 ),$$ which has elements $$( {0, 1, 2, 3, 4, 5, 6} )$$, the element 3 is a generator of the multiplicative group since the powers of 3 modulo 7 generate all non-zero elements of the field: $$ 3^1 \\equiv 3, ; 3^2 \\equiv 2, ; 3^3 \\equiv 6, ; 3^4 \\equiv 4, ; 3^5 \\equiv 5, ; 3^6 \\equiv 1 \\pmod{7}$$
        
2.  **Additive Group of a Finite Field**:
    
    *   The additive group of a finite field $$( \\mathbb{F}\_{p^n} )$$ is not cyclic for $$( n > 1 )$$. Instead, it is isomorphic to the direct sum of $$( n )$$ cyclic groups of order $$( p ).$$
        

### Finding Generators

1.  **For Cyclic Groups**:
    
    *   To find a generator of a cyclic group, identify an element whose powers produce all elements of the group.
        
    *   For example, in the group $$( \\mathbb{Z}/7\\mathbb{Z} )$$ (integers modulo 7), the element 3 is a generator since $$( {3^0, 3^1, 3^2, 3^3, 3^4, 3^5, 3^6} \\equiv {1, 3, 9, 27, 81, 243, 729} \\pmod{7} \\equiv {1, 3, 2, 6, 4, 5} ).$$
        
2.  **For Finite Fields**:
    
    *   To find a generator of the multiplicative group of a finite field $$( \\mathbb{F}\_{p^n} )$$, look for an element $$( g )$$ such that $$( g^k \\neq 1 )$$ for all $$( k < p^n - 1 ).$$
        
    *   Typically, algorithms such as brute force (checking elements one by one) or more sophisticated methods like using properties of field extensions are used.
        

Elliptic Curves
---------------

Elliptic curve groups are algebraic structures used in number theory and cryptography. They are defined by the set of points that satisfy a given elliptic curve equation, which typically takes the form $$ y^2 = x^3 + ax + b$$ for some constants $$(a)$$ and $$(b)$$ over a field. The points on this curve, together with a defined point at infinity, form a group under a defined addition operation.

### Properties of Elliptic Curve Groups

1.  **Group Operation**: The addition of two points on the curve is defined geometrically. Given two points $$(P)$$ and $$(Q)$$ on the elliptic curve, the sum $$(P + Q)$$ is found by drawing a line through $$(P)$$ and $$(Q).$$ This line intersects the curve at a third point, which is then reflected over the x-axis to get the result $$(P + Q).$$
    
2.  **Identity Element**: The point at infinity $$(O)$$ serves as the identity element for the group. For any point $$(P)$$ on the curve, $$(P + O = P).$$
    
3.  **Inverse Element**: For any point $$(P = (x, y))$$ on the curve, its inverse is $$( -P = (x, -y)).$$ This means that $$(P + (-P) = O).$$
    
4.  **Elliptic Curve over Finite Fields**: When elliptic curves are used in cryptography, they are often defined over finite fields (also known as Galois fields). The curve equation is considered modulo a prime $$(p)$$ or $$(2^m)$$ for some integer $$(m)$$.

---

*Originally published on [Bless Hukporti](https://paragraph.com/@bless-hukporti/elliptic-curve-groups)*