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.

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.

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.

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 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.

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, 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.

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.

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:

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.

1. Field with 4 Elements:

   • $( \mathbb{F}_4 )$ can be constructed using the polynomial $( x^2 + x + 1 )$ over $( \mathbb{F}_2 )$.

1. Using Polynomials:

   • To construct $( \mathbb{F}_{p^n} )$, one needs an irreducible polynomial of degree $( n ) over ( \mathbb{F}_p ).$

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.

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}$

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} ).$

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.

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).$

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.

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.

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.

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 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.

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, 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.

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.

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:

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.

1. Field with 4 Elements:

   • $( \mathbb{F}_4 )$ can be constructed using the polynomial $( x^2 + x + 1 )$ over $( \mathbb{F}_2 )$.

1. Using Polynomials:

   • To construct $( \mathbb{F}_{p^n} )$, one needs an irreducible polynomial of degree $( n ) over ( \mathbb{F}_p ).$

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.

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}$

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} ).$

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.

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).$