Mathematical Cryptography II

Group Theory

A group is a set G combined with a binary operation * that satisfies the following four properties:

  1. Identity Law

There is an e ∈ G such that e \ a = a * e = a for every a ∈ G*.

  1. Inverse Law

For every a ∈ G there is a (unique) a^−1 ∈ G satisfying;

a \ a^−1 = a^−1 * a = e.*

  1. Associative Law

a \ (b * c) = (a * b) * c for all a, b, c ∈ G.*

  1. Commutative Law

a \ b = b * a for all a, b ∈ G*

Addition

  • Set: All integers {... -2, -1, 0, 1, 2, ...}

  • Operation: +

  • Identity Element: 0

  • Inverse Element: for every a ∈ G, its inverse is -a

Modular Arithmetic Addition

  • Set: Integers modulo n: {0, 1, 2, 3..., n-1}

  • Operation: + (mod n)

  • Identity Element: 0

  • Inverse Element: For each a, an integer b such that; a + b = 0 (mod n)

Matrix Group Multiplication

  • Set: All invertible 2 X 2 matrices over R or C

  • Operation: Matrix multiplication

  • Identity Element: Identity matrix = I

  • Inverse Element: For a matrix A, its matrix inverse such that; A x A^-1 = I

If the operation is commutative, the group is called an Abelian or Commutative group.

Groups can be finite or infinite. The order of a group is the number of its elements.

What is Subgroup ?

Let H ⊂ G a subset. We'll say that "H is a subgroup of G" if;

  1. e ∈ H

  2. H is closed under * operation;

h1, h2 ∈ H h1 \ h2 ∈ H*

  1. H is closed under taking inverses;

h ∈ H h^-1 ∈ H

As an example, let's take:

g ∈ G, g != e

|G| < (G is a finite group)

H = {g^k : k ∈ N} = {g, g^2, g^3, g^4, ...}

If H is a subgroup of G, it should validate 3 rules above.

Proof of 1st condition

G is a finite, so H is also a finite set, since H is a subset of G.

H = {g, g^2, g^3, g^4, ...}

The powers of the g's can not be all different because of g^{n+1} = g^n \ g^1 = e * g^1 = g^1. There *must be elements like:

R = { m ∈ N: g^m = g^j for some 1 ≤ j < m }

So we can define H like:

H = {g, g^2, g^3, g^4, g^j, ... g^(m-1)}

( Next element of this set is g^m = g^j )

g^m \ (g^j)^-1 = e g^(m- j) = e*

since j < m, (m - j) ∈ N

e ∈ H

Proof of 2nd condition

g^l \ g^m = g^(l + m)*

Proof of 3rd condition

For g^(m- j) = e, we multiply both sides by g;

g^(m- j) \ g = g*

g^(m- j + 1) = g

m - j + 1 ∈ R

According to this equation, m must be the smallest element of R. So;

m ≤ (m - j + 1) ⇾ j ≤ 1 && 1 ≤ j < m

j = 1

H = {g, g^2, g^3, ... g^(m-1)}

Last element's power and also element number of H is (m-1)

g^(m- j) = e ∈ H

References

An Introduction to Mathematical Cryptography

Cyclic Subgroups