Privacy Scaling Ethereum – Lecture 6

In this 6th lecture of the Elliptic Curve Cryptography hosted by Privacy Scaling Ethereum, we finished the chapter of Groups.

Contents

Subgroup of a Cyclic Group

Proposition: a subgroup of a cyclic group is cyclic.

From the Cyclic Group Definition: a group G is cyclic if there exists an element g in G such that every element of G can be expressed as a power of g. In other words, G is cyclic if it can be generated by a single element g.

Now, let’s consider a subgroup H of a cyclic group G. Since G is cyclic, it means there is a generator g in G that can generate all the elements of G. This means that all elements of G can be written as powers of g.

Now, let’s consider the subgroup H. If H is a subgroup of G, then every element of H must also be an element of G, and the group operation in H must be the same as that in G. So, every element in H can still be expressed as powers of the generator g, because g is also in G and therefore in H.

In other words, if you take any element h in H, you can express it as g^n, where n is an integer. Since all elements in H can be expressed this way, H is also generated by the same element g.

So, the intuition behind “a subgroup of a cyclic group is cyclic” is that if you have a group where every element can be generated by a single element, and you take a subset of that group that still obeys the group axioms, it will also be generated by that same element. This means that the subgroup is itself a cyclic group, generated by the same element that generates the whole group.

Order of Elements in the Cartesian Product of two Groups

If G and H are groups, and ‘g’ in ‘G’ has order ‘n’ and ‘h’ in ‘H’ has order ‘m,’ then the order of (g, h) is the least common multiple of ‘n’ and ‘m’ in ‘G x H.
Lemma

This means that if you have an element (g, h) in the Cartesian product group ‘G x H,’ where ‘g’ has order ‘n’ in ‘G’ and ‘h’ has order ‘m’ in ‘H,’ then the order of (g, h) in ‘G x H’ is the least common multiple (LCM) of ‘n’ and ‘m.’

In other words, the least common multiple of the orders of the individual elements ‘g’ and ‘h’ determines the order of the combined element (g, h) in the Cartesian product group ‘G x H.’

Lcm and gcd

Proposition:

gcd(n, m) · lcm(n, m) = n · m

Corollary 1: Zn x Zm is cyclic if and only if gcd(n, m) = 1. Then Zn x Zm is an isomorphism Zn x Zm=~ Znm

Corollary 2: the Chinese Remainder Theorem (CRT): suppose you have a system of simulatenous congruences of the form:

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₖ (mod mₖ)

where ‘x’ is the unknown value, ‘a₁, a₂, …, aₖ’ are the remainders, and ‘m₁, m₂, …, mₖ’ are pairwise coprime (mutually prime) positive integers.

Then, there exists a unique solution ‘x’ (up to modulo the least common multiple of ‘m₁, m₂, …, mₖ’) that satisfies all of these congruences.

In other words, the Chinese Remainder Theorem provides a method for finding ‘x’ such that it leaves the given remainders when divided by ‘m₁, m₂, …, mₖ’ respectively.

Classification of Finite Abelian Groups

For a G a (finite) abelian group and “p” a prime:

G(p) = { a in G, where the order of a is a power of p } = { a in G, where (p^n) · a = 0 for some n }

G(p) is called the Primary p-subgroup of G. Break down:

G(p) is a Subgroup of G: a subgroup is a subset of a group that is itself a group under the same group operation. In this case, we’re considering G(p), a subset of G. To prove that G(p) is a subgroup of G, we need to show that it satisfies the requirements of being a subgroup:
- Closure: For any two elements ‘a’ and ‘b’ in G(p), ‘a * b’ must also be in G(p) for some power of ‘p.’ Since G is abelian (commutative), this property is automatically satisfied, as the order of ‘a * b’ is the least common multiple of the orders of ‘a’ and ‘b,’ and if both ‘a’ and ‘b’ have orders that are powers of ‘p,’ then ‘a * b’ will also have an order that is a power of ‘p.’
- Identity Element: The identity element ‘e’ of G is in G(p) because it has an order of 1, which is a power of any prime ‘p.’
- Inverse Element: For any element ‘a’ in G(p), ‘a^(-1)’ is also in G(p) because the order of ‘a^(-1)’ is the same as the order of ‘a.’ Since ‘a’ has an order that is a power of ‘p,’ so does ‘a^(-1).’
G(p) is the Primary p-Subgroup of G: the primary p-subgroup of a group G is the subgroup that contains all the elements in G whose orders are powers of a prime ‘p.’ In other words, it’s the largest subgroup of G that consists of such elements.
To demonstrate that G(p) is the primary p-subgroup of G, we need to show that it contains all elements in G that have orders that are powers of ‘p.’ This is achieved by definition:
- G(p) is explicitly defined as the set of elements in G whose orders are powers of ‘p.’
- Any element in G with an order that is a power of ‘p’ is, by definition, in G(p).
- G(p) is a subgroup of G, so it contains the identity element ‘e,’ which has an order of 1 (a power of ‘p’).
- G(p) is also a subgroup, so it contains the inverses of its elements, and any element with an order that is a power of ‘p’ has an inverse with the same order.

Finding gcd’s

Euclidean Algorithm

The Euclidean algorithm is a straightforward method for finding the GCD of two integers. Given two integers a and b, where a ≥ b, we can find their gcd as follows:

Divide a by b to get the quotient q and the remainder r: a = bq + r
Replace a with b and b with r.
Repeat steps 1 and 2 until r becomes 0.
When r becomes 0, the gcd is the last non-zero remainder, which is b.

For example, let’s find the gcd of 48 and 18:

48 = 18⋅2 + 1248 = 18⋅2 + 12

18 = 12⋅1 + 618 = 12⋅1 + 6

12 = 6⋅2 + 012 = 6⋅2 + 0

Extended Euclidean Algorithm

The Extended Euclidean Algorithm not only finds the gcd of two numbers but also computes Bézout coefficients x and y such that:

ax+by = gcd(a,b)

Here’s how we can use the Extended Euclidean Algorithm to find the GCD and Bézout coefficients:

Start with the initial values a0=a, b0=b, x0=1, y0=0,x1=0, and y1=1.
Use the Euclidean algorithm to find the gcd g.
For each iteration, calculate ai=bi−1, bi=ai−1modbi−1, and compute xi and yi as follows:
- xi=xi−2 − qi⋅xi−1
- yi=yi−2 − qi⋅yi−1
Continue these iterations until bi becomes 0.
The gcd is g=ai, and the Bézout coefficients are xi and yi.

Here’s an example using a=48 and b=18:

a0=48, b0=18, x0=1, y0=0, x1=0, y1=1
Using the Euclidean algorithm, we find �=6g=6.
Continue the iterations:
- a1 = 18, b1 = 12, q1 = 2
- x2 = 1 - 2·0 = 1, y2 = 0 - 2·1 = -2
- a2 = 12, b2 = 6, q2 = 2
- x3 = 0 - 2·1 = -2, y3 = 1 -2·(-2) = 5

So, for a=48 and b=18, the gcd is 6, and we have 48⋅(−2)+18⋅5=648⋅(−2)+18⋅5=6. This illustrates Bézout’s identity.

Fundamental Theorem of Finitely Generated Abelian Groups

It states that a finite abelian group can be decomposed into a direct sum of its primary cyclic subgroups. Let’s break down this theorem step by step:

Group Decomposition: Let G be a finite abelian group. This means that G is a group with a finite number of elements.
Prime Decomposition: The theorem begins by considering the prime factorization of the order (#G) of the group G. This factorization is given as: #G = p_1^{r_1} ·... p_k^{r_k} where p1,p2,…,pk are distinct prime numbers, andr1,r2,…,rk are positive integers.
Primary Cyclic Subgroups: The theorem states that for each prime factor pi_^ri, there exists a unique subgroup G(pi) of G such that:
- The order of G(pi) is p_i^ri.
- G(pi) is a cyclic subgroup generated by an element g_i of order p_i^ri.
Direct Sum: The theorem then asserts that the group G is isomorphic to the direct sum of these primary cyclic subgroups: G≅G(p1)⊕G(p2)⊕…⊕G(pk) Here, ⊕⊕ represents the direct sum of groups.

The theorem essentially provides a way to understand the structure of finite abelian groups by breaking them down into simpler, cyclic subgroups based on their prime factorization.

Matter

Given 2 numbers, get the greatest common divisor using Euclid’s algorithm and he Bézout coefficients, using the extended Euclid’s algorithm.