In this 4th lecture of the Elliptic Curve Cryptography hosted by Privacy Scaling Ethereum, we continued our journey of Groups. We saw how to move from one group to another (homomorphisms), like we did in sets, but here it must respect the structure of groups. We also saw the trivial homomorphism, the one that maps everything to the unit.
Homomorphisms. How to Move Between Groups
To move between sets we only need a function, but to move between groups we need something that respects the additional structure of groups.
Let G and H be groups, a function f: G –> H is a homomorphism if
f(x · x') = f(x) · f(x')and if f: G –> H is a homomorphism, then automatically f of the unit element of G has to go to the unit element of H:
f(eG) = eHand the inverse done in G is equal to the inverse done in H:
f(x^-1) = f(x)^-1From Wikipedia, a group homomorphism is a map between groups that preserves the group operation. This implies that the group homomorphism maps the identity element of the first group to the identity element of the second group, and maps the inverse of an element of the first group to the inverse of the image of this element. Thus a semigroup homomorphism between groups is necessarily a group homomorphism.
The Trivial Homomorphism
The trivial homomorphism is the one that maps everything to the unit.
There is no non-trivial homomorphism from the integers modn to the integers.
The Quotient Group
From Wikipedia, a quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure (the rest of the structure is “factored” out). For example, the cyclic group of addition modulo n can be obtained from the group of integers under addition by identifying elements that differ by a multiple of n and defining a group structure that operates on each such class (known as a congruence class) as a single entity.
From Wolfram, for a group G and a normal subgroup N of G, the quotient group of N in G, written G / N and read “G modulo N”, is the set of cosets of N in G. Quotient groups are also called factor groups. The elements of G/N are written Na and form a group under the normal operation on the group N on the coefficient a. Thus:
(N a) (N b) = N a bSince all elements of G will appear in exactly one coset of the normal subgroup N, it follows that:
| G | = | G / N | N |where G denotes the order of a group. This is also a consequence of Lagrange’s group theorem with H = G and K = N.
Isomorphism
A homomorphism of groups f: G –> H is called an isomorphism if it is bijective. As an intuition, the 2 multiplication tables are the same, just change symbols (x to f(x)).
The identity function is an isomorphism, because it is bijective (you can always go back).
Isomorphism are special types of homomorphisms.
Proposition: if f: G –> H is an isomorphism, then so is f^-1: H –> G.
The notation is symmetric, meaning:
- it exists an isomorphism between G and H
- it exists an isomorphism between H and G
Kernel and Image
- The kernel ker(f) is all the elements x in G, such that f(x) = eH. The kernel of f is a subset of G.
- the kernel of f is a subgroup of G. So this should hold:
- the unit element is in the candidate for a subgroup
- the binary operation of 2 elements in the subgroup are an element in the subgroup
- the inverse of an element in the subgroup is also an element in the subgroup
- the kernel of f is a subgroup of G. So this should hold:
- The image of f Im(f) is the set of all f(x) such that x in G. The image of f is a subset of H
- the image of f is a subgroup of H
Note: the kernel of f is kind of a measurement of how close f is to be an injective map.
The First Isomorphism Theorem
Let f: G –> H be a homomorphiusm of abelian groups and denote k = ker(f), then there is a isomorphism between the quotien G/k and the image of f:
G / k =~ Im(f)Note, many groups that come from quotient constructions are isomorphic to groups that are constructed in a more direct and simple way.