Crypto Pills #16: Basics of Abstract Algebra—Isomorphism

In cryptographic applications, isomorphism is ideal for transformations where structural equivalence is necessary, allowing secure, structure-preserving mappings. Homomorphism allows for structure-preserving mappings that need not be bijective. Homomorphic encryption, for instance, utilizes the concept of homomorphism to perform computations on encrypted data.

Understanding the role of isomorphisms and homomorphisms enables cryptographers and software engineers to build robust, efficient cryptographic systems by transforming data within secure, mathematically sound frameworks.

In this post we'll dive into the isomorphism concept first, then we'll cover homomorphism, as a generalization, later.

Isomorphism

In abstract algebra, an isomorphism is a bijective mapping between two algebraic structures that preserves their operations. Isomorphisms demonstrate that two structures are essentially the same in terms of their algebraic properties, even if their representations differ.

For cryptography, this notion of equivalence is crucial — it allows transformations between different data representations without altering the underlying structure necessary for security.

Definition

Consider two groups (G, ∗) and (H, ⋅); so if there is a bijective map ϕ : G → H such that the group operation ϕ(a ⋅ b) = ϕ(a) ∗ ϕ(b) is preserved, then the map ϕ is an isomorphism.

If G is isomorphic to H, we write G ≅ H.

Example 1: Integers under Addition and Even Integers

Let’s define the groups

• G = (ℤ, +): the group of all integers under addition.
• H = (2ℤ, +): the group of all even integers under addition.

If we define the mapping ϕ : G → H as ϕ(n) = 2n, then

1. ∀ a, b ∈ G : ϕ(a + b) = 2(a + b) = 2a + 2b = ϕ(a) + ϕ(b).
2. Suppose ϕ(a) = ϕ(b), then 2a = 2b, which implies a = b, so it's an injective map.
3. ∀ y ∈ H, ∃x ∈ G : ϕ(x) = y, specifically x = y/2​, so it's surjective also.

Therefore, (ℤ, +) ≅ (2ℤ, +).

Example 2: Complex Numbers in the Cartesian Plane

Consider:

• G = (ℂ, +): the group of complex numbers under addition.
• H = (ℝ², +): the group of ordered pairs of real numbers under addition.

If we define the mapping ϕ : G → H as ϕ(a + bi) = (a, b), then

1. For any z₁ = a₁ + b₁i and z₂ = a₂ + b₂i in G,

2. Suppose ϕ(z₁) = ϕ(z₂); then (a₁, b₁) = (a₂, b₂), which implies z₁ = z₂.

3. ∀ (x, y) ∈ ℝ², we have z = x + yi ∈ ℂ : ϕ(z) = (x, y).

Therefore, (ℂ,+) ≅ (ℝ², +).

Example 3: Exponentiation

Consider:

• G = (ℝ, +): the group of real numbers under addition.
• H = (ℝ⁺, ⋅): the group of positive real numbers under multiplication with exponential map.

If we define the mapping ϕ : G → H as ϕ(n) = eⁿ, then

1. ∀ x, y ∈ G, ϕ(x + y) = eˣ⁺ʸ = eˣ ⋅ eʸ = ϕ(x) ⋅ ϕ(y).
2. Suppose ϕ(a) = ϕ(b); then eᵃ = eᵇ, which implies a = b.
3. ∀ y ∈ H, ∃x ∈ G : ϕ(x) = y, which is x = e⁻ʸ.

Therefore, (ℝ, +) ≅ (ℝ⁺, ⋅).

Exercises

• Be G = (ℂ, ⋅), H = (𝕋, ⋅), ϕ(z): G → H | ϕ(z) = z / |z*|. Check if the function of normalizing complex numbers is isomorphic.
• Be ϕ : ℤ → ℂ | ϕ(n) = iⁿ. Is it isomorphic?

Theorem 1. Let ϕ : G → H be an isomorphism of two groups. Then all the following statements are true.

1. ϕ⁻¹ : H → G is an isomorphism.
2. |G| = |H|.
3. G is abelian ⇒ H is abelian.
4. G is cyclic ⇒ H is cyclic.
5. G has a subgroup of order n ⇒ H has a subgroup of order n.

Theorem 2. All cyclic groups of infinite order are isomorphic to ℤ.

Theorem 3. If G is a cyclic group of order n, then G is isomorphic to ℤₙ.

• Corollary. If G is a group of order p, where p is a prime number, then G is isomorphic to ℤₚ.

Direct Products

Given two groups G and H, we can form a new group by taking their Cartesian product G × H. Sometimes, large groups can be decomposed as the direct product of smaller groups, making it easier to analyze their component groups individually rather than as a whole.

External Direct Products

If (G, ⋅) and (H, ∗) are groups, their Cartesian product G × H can be structured as a new group, such that each element is an ordered pair (g, h) ∈ G × H.

We can define a binary operation in this new group combining elements from each coordinate, such as in (g₁, h₁) ⋅ (g₂, h₂) = (g₁ ⋅ g₂, h₁ ∗ h₂). We usually denote this relationship as simply (g₁, h₁) ⋅ (g₂, h₂) = (g₁g₂, h₁h₂) omitting operators.

This group G × H is known as the external direct product of G and H.

The concept can be extended to any finite number of groups, denoted as G₁ × G₂ × … × Gₙ, with each operation applying within the corresponding component.

Theorem 4. Let G and H be finite groups with orders r =|G| and s = |H|. The order of (g, h) in G × H is the least common multiple (lcm) of r and s.

• Corollary. For any group (g₁, …, gₙ) ∈ ∏ Gᵢ, if gᵢ has finite order rᵢ in Gᵢ, then the order of (g₁, …, gₙ) in ∏Gᵢ is lcm(r₁, …, rₙ).

Theorem 5. The group ℤₘ × ℤₙ​ is cyclic and isomorphic to ℤₘₙ if and only if gcd(m, n) = 1, which is the same as saying that m and n should be coprimes.

Internal Direct Products

The external direct product builds a larger group from smaller groups. Conversely, an internal direct product expresses a group as the product of its subgroups, where a group G is isomorphic to the direct product of two subgroups H and K if:

1. Every element of G can be uniquely written as hk for h ∈ H and k ∈ K, expressed just as G = HK = {hk : h ∈ H, k ∈ K},
2. H ∩ K = {e},
3. h and k commute (hk = kh) for all h ∈ H and k ∈ K.

Theorem 6. If G is the internal direct product of subgroups H and K, then G is isomorphic to H × K.

This definition extends to more than two subgroups, allowing a group to be decomposed as the direct product of multiple components under similar conditions.

Credits

Above is a resume I created by reading about the same theme in Abstract Algebra: Theory and Applications, by Thomas W. Judson.

I’m grateful for this quality of material to be freely available on Internet. Thank you.

Conclusion

Isomorphisms allow for transformations that maintain structural equivalence. By studying isomorphisms through examples and analyzing the properties of direct products, cryptographers can gain powerful tools for constructing systems that are both secure and mathematically robust.