Privacy Scaling Ethereum – Lecture 3

In this 3rd lecture of the Elliptic Curve Cryptography hosted by Privacy Scaling Ethereum, we continued exploring groups. We reviewed what a group was – a set with a binary operation – and its properties (associativity, existence of the neutral element and the inverse element). We also saw the concept of subgroups and coset.

Review from last week

A group is a set G with a binary operation · such that for any x, y, z in G we have:

• associativity (x y) z = x (y z)
• existist a neutral element such that for any x in G, e · x = x · e = x
• exists an element x^-1 such that x · x^-1 = e = x^-1 · x

From the axioms:

1. The neutral element e is unique
2. The inverse element x^-1 is unique
3. It is enough to ask for left/right inverse instead of a two-sided inverse

Subgroups

Let G be a group. A subset H belonging to G is called a subgroup if:

1. The neutral elemenet belongs to H
2. The subgroup is closed under the binary operation of G. For any x and y, x · y belongs to H
3. For any x in H, the inverse also belongs to H

Normal Subgroup

From Wolfram, let H be a subgroup of a group G. The similarity transformation of H by a fixed element x in G not in H always gives a subgroup. If:

x H x^-1 = H

for every element x in G, then H is said to be a normal subgroup of G. Normal subgroups are also known as invariant subgroups or self-conjugate subgroup.

Coset

The Coset is subset of mathematical group consisting of all the products obtained by multiplying fixed element of group by each of elements of given subgroup, either on right or on left.

Suppose if A is group, and B is subgroup of A, and is an element of A, then:

aB = {ab : b an element of B } is left coset of B in A

The left coset of B in A is subset of A of form aB for some a(element of A). In aB(left coset), a is representative of coset.

Proposition: for a group G and a subgroup H <= G, the set of cosets (xH where x belongs to G) form a partition of G:

1. The union of all cosets is the group H: xH = G
2. if we take 2 cosets that are not equal (xH and yH) then their intersection is the empty set

Lagrange Theorem: if G is finite and H is a subgroup of G (also finite), then the number of elements in H must divide the number of elements in G.

Overview of Next Steps

• See more groups (Cauchy theory, isomorphism theory,..)
• Fields (prime field, prime to the n field, polynomials over fields, classification of finite fields)
• Algebraic closure of a field
• Elliptic curves