DeFi

Privacy Scaling Ethereum – Lecture 5

In this 5th lecture of the Elliptic Curve Cryptography hosted by Privacy Scaling Ethereum, we continued our journey of Groups. We saw the order of elements in a group, as well as Cauchy Theorem for checking the existence of subgroups with a specific order. We also saw what Cyclic Groups are, the concept of generator and some examples using Cayley Tables. Finally, we revised existence of Cyclic Groups of Order ‘n’ up to Isomorphism and the Euler Totient Function.

The order of elements in a group

Let G be a group and g € G, the order of g denoted as O(g) is the minimal positive integer such that:

g^n= e

If no such number exists, then the order is infinity:

O(g) = ∞

Cauchy Theorem

If G is a finite abelian group and p a prime, such that p divides the order of the group G. Then it exists g in G with order exactly p (g^p = e).

Here are some of the key implications and applications of Cauchy’s theorem in group theory, generated with ChatGPT:

  1. Existence of Subgroups: Cauchy’s theorem guarantees the existence of subgroups of a given order (in this case, subgroups of order p) within a finite group. This is a useful tool for understanding the structure of finite groups.
  2. Sylow Theorems: Cauchy’s theorem is one of the foundational results used in the proof of Sylow’s theorems, which provide further insight into the structure of finite groups. Sylow’s theorems are important for studying the subgroups of a group, as they describe the number and properties of subgroups of a specific order within a group.
  3. Cyclic Groups: Cauchy’s theorem can be applied to prove the existence of elements of a specific order in a finite group. In the case where p is a prime number, the theorem implies the existence of subgroups isomorphic to the cyclic group of order p within G.
  4. Classification of Groups: Cauchy’s theorem, along with Sylow’s theorems and other group theory results, contributes to the classification of finite groups. It helps mathematicians understand the possible structures and properties of finite groups of different orders.

Cyclic Groups

A cyclic group is a type of group characterized by the property that the group’s elements can be generated by a single element, known as a generator, through repeated application of the group’s operation. In other words, in a cyclic group, you can start with a specific element, and by repeatedly combining it with itself using the group operation, you can generate all the elements of the group.

If G is cyclic, then it is abelian. Key characteristics:

  1. Generator: In a cyclic group, there exists at least one element, denoted as “g,” such that the entire group can be generated by repeatedly applying the group operation to g. A generator does not need to be unique. A cyclic group can be generated by different elements.
  2. Notation: Cyclic groups are often denoted as “Cₙ” or “Zₙ,” where “n” represents the number of elements in the group. For example, C₆ or Z₆ represents a cyclic group with six elements.
  3. Group Operation: The group operation in a cyclic group can be addition, multiplication, or any other operation, depending on the specific group. In additive notation, a typical cyclic group operation is modular addition (addition modulo n), while in multiplicative notation, it’s often modular multiplication (multiplication modulo n).

Examples:

  • Cyclic Group of Integers (Additive Notation):
    • Example: C₆ (or Z₆)
    • Elements: {0, 1, 2, 3, 4, 5}
    • Operation: Modular addition (addition modulo 6)
    • Generator: 1 (or any element that, when added repeatedly, cycles through all elements)
    • It forms a cyclic group because starting from 1 and adding it repeatedly modulo 6 generates all the elements: 1, 2, 3, 4, 5, 0, 1, 2, …
  • Cyclic Group of Residue Classes (Additive Notation):
    • Example: C₈ (or Z₈)
    • Elements: {0, 1, 2, 3, 4, 5, 6, 7}
    • Operation: Modular addition (addition modulo 8)
    • Generator: 1 (add 1 repeatedly)
    • It’s cyclic because starting from 1 and adding it repeatedly modulo 8 generates all the elements: 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, …
  • Cyclic Group of Nonzero Integers Modulo Prime (Multiplicative Notation):
    • Example: C₅ (or Z₅)*
    • Elements: {1, 2, 3, 4}
    • Operation: Modular multiplication (multiplication modulo 5)
    • Generator: 2 (multiply 2 repeatedly)
    • It’s cyclic because starting from 2 and multiplying it repeatedly modulo 5 generates all the elements: 2, 4, 3, 1, 2, 4, 3, 1, …

Cayley Table

C₂ × C₃: a cyclic group that is the Cartesian product of two cyclic groups, one modulo 2 (Z₂) and the other modulo 3 (Z₃). The resulting group will be C₂ × C₃, representing the direct product of two cyclic groups.

  • C₂ represents the cyclic group modulo 2: {0, 1} with modular addition.
  • C₃ represents the cyclic group modulo 3: {0, 1, 2} with modular addition.

To construct the Cayley table (also known as the group table) for the group C₂ × C₃, which is the Cartesian product of the cyclic groups C₂ (mod 2) and C₃ (mod 3), you need to consider all possible pairs of elements from the two groups and apply the group operation component-wise.

Steps to build the Cayley table:

  1. List the Elements: First, list all the elements of C₂ and C₃.
    • C₂ = {0, 1} (mod 2) with modular addition.
    • C₃ = {0, 1, 2} (mod 3) with modular addition.
  2. Pairs of Elements: Form pairs by taking one element from C₂ and one element from C₃. These pairs represent the elements of C₂ × C₃.
    • Possible pairs from C₂ × C₃: {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)}
  3. Apply the Group Operation: For each pair, apply the group operation component-wise. Since C₂ and C₃ both use modular addition, you should add the components of the pairs modulo 2 for the first component and modulo 3 for the second component.For example, consider the pair (1, 1):
    • First component (mod 2): 1 + 1 ≡ 0 (mod 2).
    • Second component (mod 3): 1 + 1 ≡ 2 (mod 3).
    So, for the pair (1, 1), the result is (0, 2).
  4. Complete the Cayley Table: Continue this process for all pairs to fill in the entire Cayley table. Each element in the table represents the result of applying the group operation to the corresponding pair.

Here’s the Cayley table for C₂ × C₃:

C₂ × C₃:
(0, 0) (1, 0) (0, 1) (1, 1) (0, 2) (1, 2)

(0, 0)  (0, 0)  (1, 0)  (1, 0)  (0, 1)  (1, 1)
(1, 0)  (1, 0)  (0, 1)  (0, 1)  (1, 2)  (0, 2)
(0, 1)  (0, 1)  (1, 2)  (1, 2)  (0, 0)  (1, 0)
(1, 1)  (1, 1)  (0, 2)  (0, 2)  (1, 1)  (0, 1)
(0, 2)  (0, 2)  (1, 0)  (1, 0)  (0, 1)  (1, 1)
(1, 2)  (1, 2)  (0, 1)  (0, 1)  (1, 0)  (0, 0)

Existence of Cyclic Groups of Order ‘n’ up to Isomorphism

For any natural number n, there exists a cyclic group of order n and it is unique up to isomorphism.

Existence of Cyclic Groups of Order n:

  1. For Any Natural Number n: this part of the proposition assures us that given any positive integer n, there is at least one cyclic group with n elements. In other words, you can always find a group with n elements that can be generated by a single element.
  2. Cyclic Group: a cyclic group is characterized by the fact that it can be generated by a single element. This element, called a generator, can be combined with itself using the group operation to produce all other elements of the group. The cyclic group is essentially a “circular” structure, where you start with a generator and repeatedly apply the group operation to generate all other elements.

Uniqueness of Cyclic Groups of Order n (Up to Isomorphism):

  1. Unique Up to Isomorphism: The second part of the proposition states that while there may be multiple cyclic groups of order n, they are all isomorphic to each other. Isomorphism is a concept in group theory that describes a one-to-one correspondence between two groups, where the group operation is preserved. In the case of cyclic groups of the same order, they are isomorphic because they have the same group structure.

Intuition Behind Uniqueness (Up to Isomorphism):

To understand the uniqueness up to isomorphism, consider the following:

  • All cyclic groups of the same order n have the same basic structure. They are generated by a single element, and their group operation is essentially addition or multiplication modulo n.
  • The choice of generator may vary, but the fundamental group structure is the same. Changing the generator doesn’t change the underlying group structure; it simply reorders the elements.
  • Isomorphism preserves this structure. If you have two cyclic groups of order n with different generators, you can find an isomorphism that relates them. This isomorphism essentially “renames” the elements of one group to match the elements of the other, while preserving the group operation.

So, the proposition tells us that while there may be different ways to write down cyclic groups of order n (by choosing different generators), they are all fundamentally the same in terms of group structure. This is why they are considered unique up to isomorphism. It’s a powerful and elegant result in group theory that simplifies the study of cyclic groups.

How many generators are there

An element k in integers modulo n is a generator (the group generated by k is the whole abelian group) if and only if the greatest common divisor of n, k, gcd(n, k) is equal to 1.

When gcd(n, k) is 1, k can generate all elements of the group because it has no common factors with n.

Coprime numbers are numbers which have no common divisors except 1. We need a coprime number to the modulus in order to generate everything.

Example

Let’s consider an example to illustrate the concept of an element being a generator in the integers modulo n (Zₙ) when the greatest common divisor (gcd) between the element and n is 1. We’ll use n = 8 for this example.

In Z₈ (integers modulo 8), we want to determine whether a specific element k is a generator. To do this, we check the gcd(n, k).

  1. Choose an element k. Let’s say we want to test k = 3.
  2. Calculate the gcd(n, k):
    • gcd(8, 3) = 1

In this case, the gcd between 8 and 3 is 1, which means that k and 8 are relatively prime. This is what we are looking for.

Now, let’s see what happens when we repeatedly combine the element k = 3 with itself using modular addition (addition modulo 8) to generate the entire group:

3 (k)
6 (3 + 3)
1 (6 + 3)
4 (1 + 3)
7 (4 + 3)
2 (7 + 3)
5 (2 + 3)
0 (5 + 3)

As you can see, by repeatedly adding 3 to itself modulo 8, we generate all elements of Z₈: {0, 1, 2, 3, 4, 5, 6, 7}. Element 3, in this case, is a generator of the group Z₈.

This example demonstrates that an element with a gcd of 1 with n can generate the entire cyclic group, which is a key property of generators in Zₙ. Elements that are not relatively prime with n would not generate the entire group when combined with themselves modulo n.

The Euler Totient Function

The Euler’s totient function, often denoted as φ(n) or simply “phi of n,” is a mathematical function that counts the number of positive integers less than or equal to a given positive integer n that are relatively prime to n. In other words, it calculates the number of positive integers that share no common factors (other than 1) with n. The Euler’s totient function is defined as follows:

φ(n) = Number of positive integers less than or equal to n that are relatively prime to n.

Matter

  • Given 2 groups calculate the Cayley table
  • Calculate the Euler Totient function

Leave a comment