Privacy Scaling Ethereum – Lecture 7

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

Finite Abelian p-Groups

Lemma: Let G be a finite abelian p-group (the order of G is a power of p). Let “a” in G be an element of maximal order. Then there exists a subgroup K such that G is isomorphic to <a> + K.

It essentially states that in a finite abelian p-group, there exists an element of maximal order, and you can find a subgroup such that the group is isomorphic to the direct sum of this element and that subgroup. Let’s break down the lemma step by step:

1. Finite Abelian p-Group: A group G is called a finite abelian p-group if its order is a power of a prime number p. In other words, the order of G can be expressed as p^n for some non-negative integer n.
2. Element of Maximal Order: In G, there is an element “a” of maximal order. This means that among all the elements in G, “a” has the largest possible order. In an abelian group, the order of an element is the smallest positive integer k such that a^k = e (where e is the identity element).
3. <a>: The notation <a> represents the subgroup generated by the element “a.” It consists of all the elements that can be obtained by taking powers of “a” and their inverses.
4. Direct Sum: The direct sum (+) of two subgroups is a way to combine them into a larger group. If H and K are two subgroups of a group G, then H + K is the set of all elements of the form h + k, where h is in H and k is in K. This operation is well-defined because G is abelian.

The First Version of the Classification Theorem

The Chinese Remainder Theorem (CRT) states that if you have two relatively prime modulo (in this case 4 and 25), then you can combine them to find an isomorphism to a larger modulus (in this case 100). Here’s how this works:

1. Integers modulo 4 (Z4) has elements {0, 1, 2, 3}.
2. Integers modulo 25 (Z25) has elements {0, 1, 2, 3, …, 24}.
3. Integers modulo 100 (Z100) has elements {0, 1, 2, 3, …, 99}.

First, note that 4 and 25 are relatively prime, meaning their greatest common divisor (gcd) is 1. This is a key requirement for the CRT to work. You can define an isomorphism by considering two mappings:

1. From Z4 to Z100:
   • 0 in Z4 maps to 0 in Z100.
   • 1 in Z4 maps to 25 in Z100 (25 is equivalent to 1 modulo 100).
   • 2 in Z4 maps to 50 in Z100 (50 is equivalent to 2 modulo 100).
   • 3 in Z4 maps to 75 in Z100 (75 is equivalent to 3 modulo 100).
2. From Z25 to Z100:
   • n in Z25 maps to 4n in Z100. (For any n in Z25, you can find an equivalent n in Z100 by multiplying it by 4.)

These two mappings are consistent with the way modular arithmetic works. When you combine them using the CRT, you get an isomorphism from Z4 and Z25 to Z100.

So, Z4 x Z25 is isomorphic to Z100, where “x” represents the direct product of two groups. In other words, the combination of integers modulo 4 and integers modulo 25 is isomorphic to integers modulo 100.

Corollary

Finite Abelian groups admit the converse of Lagrange Theorem.

Lagrange’s Theorem is a fundamental result in group theory, which states that for any finite group G and any subgroup H of G, the order (number of elements) of H divides the order of G.

If you have a finite group G, and you know that the order of every subgroup of G divides the order of G, then G is necessarily an Abelian group, and more specifically, a finite Abelian group.

In other words, the converse of Lagrange’s Theorem tells us that if the order of subgroups dividing the order of the group is satisfied for all subgroups of a finite group, then that group is Abelian.

The Second Version of the Classification Theorem

Let G be a finite abelian group, then G is isomorphic to Zni direct sum … Znk, where ni divides ni+1 for any i between 1 and k-1.

Main example: elliptic curve E: y^2 = x^3 +ax +b, with a, b in Fp (prime field), the set of solutions E(Fp) = { (x, y) in FpxFp, such that y^2= x^3 +ax +b} —> this is an abelian group.