16 Isomorphism, Powers, Order, Generators, Lagrange's Theorem, Multiplicative Groups, Euler's Totient Function, RSA

Lecture from: 11.11.2024 | Video: Videos ETHZ

Isomorphism

Last time, we explored the isomorphism between ${\mathbb{Z}}_{20}^{\ast }$ and ${\mathbb{Z}}_2\times {\mathbb{Z}}_4$. A key strategy for demonstrating such isomorphisms is to examine the orders of elements and, in particular, to find generators for each group.

Recall that ${\mathbb{Z}}_{20}^{\ast }=\{1,3,7,9,11,13,17,19\}$. We found that:

In ${\mathbb{Z}}_{20}^{\ast }$:

• 3 has order 4.
• -1 (or 19) has order 2. In ${\mathbb{Z}}_2\times {\mathbb{Z}}_4$:
• (0,1) has order 4.
• (1,0) has order 2.
• (1,2) has order 2.

By matching elements of the same order, we can construct a mapping between the two groups. As shown in the image, we mapped 3 to (0,1) and -1 to (1,0). This partial mapping helps to determine the full isomorphism. Once generators are mapped, the rest of the mapping follows from the homomorphism property.

This establishes an isomorphism because it defines a bijective homomorphism.

• Homomorphism: The mapping preserves the group operation. That is, if we map two elements from ${\mathbb{Z}}_{20}^{\ast }$ to ${\mathbb{Z}}_2\times {\mathbb{Z}}_4$ and then perform the operation in ${\mathbb{Z}}_2\times {\mathbb{Z}}_4$, we get the same result as if we performed the operation in ${\mathbb{Z}}_{20}^{\ast }$ and then mapped the result. This needs to be verified for the chosen generators.
• Bijective: The mapping is one-to-one and onto. Every element in ${\mathbb{Z}}_{20}^{\ast }$ maps to a unique element in ${\mathbb{Z}}_2\times {\mathbb{Z}}_4$, and every element in ${\mathbb{Z}}_2\times {\mathbb{Z}}_4$ has a pre-image in ${\mathbb{Z}}_{20}^{\ast }$.

Because the mapping is a bijective homomorphism, it’s an isomorphism, demonstrating that the two groups have the same underlying structure despite their different representations. The existence of an isomorphism is typically not trivial to prove; there’s no general algorithmic approach. However, by examining element orders, and especially generators and their relations, we can often simplify the process of finding an isomorphism.

Powers

Let $⟨G;\ast {,}^{-1},e⟩$ be a group. We define integer powers of an element $a\in G$ as follows:

• $a^0=e$: The zeroth power of any element is the identity element.
• $a^n=a\ast a\ast \cdots \ast a$ ($n$ times) for $n>0$: The $n$-th power is the element $a$ combined with itself $n$ times using the group operation.
• $a^{-1}=\hat{a}$: The negative first power is the inverse of $a$.
• $a^{-n}=(a^{-1}{)}^n$ for $n>0$: The negative $n$-th power is the $n$-th power of the inverse of $a$. With these definitions, the following properties hold for all integers $m$ and $n$:
• $a^m\ast a^n=a^{m+n}$
• $(a^m{)}^n=a^{mn}$

These properties establish a homomorphism from the additive group of integers $⟨\mathbb{Z};+,-,0⟩$ to the group $G$. Consider the map $\varphi :\mathbb{Z}\to G$ defined by $\varphi (n)=a^n$ for a fixed element $a\in G$. Then:

$\varphi (m+n)=a^{m+n}=a^m\ast a^n=\varphi (m)\ast \varphi (n)$

This shows that $\varphi$ is a homomorphism. This homomorphism maps the additive structure of integers to the multiplicative structure (repeated application of the group operation) within $G$. Note that this may not always be an isomorphism, as $a^n$ may not cover all of $G$, nor is $n$ necessarily unique. However, if the homomorphism $\varphi :\mathbb{Z}\to G$ is surjective (meaning $a$ covers all of $G$), then $G$ is a cyclic group with $a$ as the generator.

Order of an Element

The order of an element $a$ in a group $⟨G;\ast {,}^{-1},e⟩$ is the smallest positive integer $n$ such that $a^n=e$. If no such positive integer exists, the order of $a$ is said to be infinite.

Intuitively, the order of an element represents how many times the element needs to be combined with itself using the group operation to reach the identity element.

Examples:

• In ${\mathbb{Z}}_4$ (additive group): The order of 1 is 4, because $1+1+1+1=4\equiv 0(\mathrm{mod}4)$, and 4 is the smallest positive integer with this property. The order of 2 is 2, because $2+2=4\equiv 0(\mathrm{mod}4)$.

• In $\mathbb{Z}$ (additive group): The order of any non-zero integer is infinite, because no matter how many times we add a non-zero integer to itself, we will never reach 0.

• In ${\mathbb{Z}}_5^{\ast }$ (multiplicative group): The order of 2 is 4, because $2^1\equiv 2(\mathrm{mod}5)$, $2^2\equiv 4(\mathrm{mod}5)$, $2^3\equiv 8\equiv 3(\mathrm{mod}5)$, and $2^4\equiv 16\equiv 1(\mathrm{mod}5)$.

Note on Terminology:

The term “order” is unfortunately used in two different contexts in group theory:

1. Order of a group: This refers to the cardinality (number of elements) of the group, often denoted as $|G|$.
2. Order of an element: This refers to the smallest positive integer power that results in the identity element.

The context usually makes it clear which meaning is intended.

Finite Groups imply finite order for any element

Theorem: In a finite group $G$, every element $a\in G$ has finite order.

Proof:

Consider the powers of $a$: $a^1,a^2,a^3,\dots$. Since $G$ is finite, there must be a repetition among these powers. That is, there exist integers $m$ and $n$ with $m>n$ such that $a^m=a^n$.

Multiplying both sides of this equation by $a^{-n}$ (which exists since $G$ is a group), we get:

$a^{m-n}=a^m\ast a^{-n}=a^n\ast a^{-n}=e$

Since $m>n$, $m-n$ is a positive integer. Therefore, we have found a positive integer $k=m-n$ such that $a^k=e$. This means that the order of $a$ is finite and at most $k$.

Generators of a Group

A generator of a group $G$ is an element $g\in G$ such that every element of $G$ can be expressed as a power of $g$ (using the group operation). In other words, for every $a\in G$, there exists an integer $n$ such that $a=g^n$.

A group that has a generator is called a cyclic group. Cyclic groups are denoted by $⟨g⟩$, where $g$ is the generator.

Examples:

• ${\mathbb{Z}}_4$: The group of integers modulo 4 under addition is cyclic. The element 1 is a generator, since every element can be expressed as a multiple of 1: $0=1^0$ (using additive notation, this means $0\cdot 1$), $1=1^1$, $2=1^2$ ($1+1$), $3=1^3$ ($1+1+1$). 3 is also a generator.

• ${\mathbb{Z}}_n$: More generally, the group of integers modulo $n$ under addition is always cyclic. The element 1 is a generator. Other elements can be generators too, specifically those coprime to $n$.

• ${\mathbb{Z}}_2\times {\mathbb{Z}}_2$: The Klein four-group is not cyclic. No single element can generate all other elements. Every element other than the identity has order 2.

• $S_3$: The symmetric group on 3 elements is not cyclic. There is no single permutation that can generate all other permutations.

Properties of Cyclic Groups:

• Abelian: All cyclic groups are abelian (commutative). This follows directly from the definition and the properties of powers: $g^m\ast g^n=g^{m+n}=g^{n+m}=g^n\ast g^m$.

• Order of a Cyclic Group: The order of a cyclic group is the smallest positive integer $n$ such that $g^n=e$, where $g$ is the generator.

• Subgroups: All subgroups of a cyclic group are also cyclic.

• Isomorphic to ${\mathbb{Z}}_n$ or $\mathbb{Z}$: Every cyclic group is isomorphic to either ${\mathbb{Z}}_n$ (if the group is finite of order $n$) or to $\mathbb{Z}$ (if the group is infinite).

Lagrange’s Theorem

Let $G$ be a finite group and $H$ be a subgroup of $G$. Then the order of $H$ divides the order of $G$. That is, $|H|$ is a divisor of $|G|$.

Proof:

The proof relies on the concept of cosets. A left coset of $H$ in $G$ is a set of the form $gH=\{gh\mid h\in H\}$ for some $g\in G$. Similarly, a right coset is $Hg=\{hg\mid h\in H\}$. We will focus on left cosets, but the argument is analogous for right cosets.

1. Cosets partition G: The left cosets of $H$ partition $G$. This means that every element of $G$ belongs to exactly one left coset of $H$. To see this:

   • Every element $g\in G$ belongs to the coset $gH$ (since $g=ge$ and $e\in H$).
   • If two cosets $g_{1}H$ and $g_{2}H$ intersect (i.e., have a common element), then they are equal. Suppose $g_1{h}_1=g_2{h}_2$ for some $h_1,h_2\in H$. Then $g_1=g_2{h}_2{h}_1^{-1}$. Since $H$ is a subgroup, $h_2{h}_1^{-1}\in H$. Let $h_3=h_2{h}_1^{-1}$. Then $g_1=g_2{h}_3$, and therefore $g_{1}H=g_2{h}_{3}H=g_{2}H$. Thus if two left cosets intersect they are equal.

2. All cosets have the same size: Every left coset $gH$ has the same cardinality as $H$. This can be shown by defining a bijection $f:H\to gH$ by $f(h)=gh$. This function is clearly surjective, and it’s injective because if $g{h}_1=g{h}_2$, then $h_1=h_2$ by the cancellation law in $G$.

3. Order of G is the sum of coset sizes: Since the cosets partition $G$ and all have size $|H|$, the order of $G$ is the number of cosets multiplied by the size of each coset. Let $n$ be the number of distinct left cosets of $H$ in $G$. Then $|G|=n|H|$.

Therefore, $|H|$ divides $|G|$.

Consequences of Lagrange’s Theorem

Lagrange’s Theorem, which states that the order of any subgroup of a finite group divides the order of the group, has several important implications:

• Order of Elements: The order of any element $a$ in a finite group $G$ divides the order of the group ($|G|$). This is because the set of powers of $a$ forms a cyclic subgroup of $G$, and the order of this subgroup is equal to the order of $a$.

• Groups of Prime Order: A group of prime order $p$ has no nontrivial proper subgroups. This follows directly from Lagrange’s Theorem. Any subgroup must have an order that divides $p$, so the only possible subgroup orders are 1 and $p$. The subgroup of order 1 is the trivial subgroup, and the subgroup of order $p$ is the group itself. Consequently, a group of prime order must be cyclic and therefore has a generator. Any element other than the identity will generate the entire group.

Further Consequences:

• $a^{\text{ord}(a)}=e$: This follows directly from the definition of the order of an element. The order of $a$ is the smallest positive integer $n$ such that $a^n=e$.

• $a^{|G|}=e$: Since $\text{ord}(a)$ divides $|G|$, we can write $|G|=k\cdot \text{ord}(a)$ for some integer $k$. Then, $a^{|G|}=a^{k\cdot \text{ord}(a)}=(a^{\text{ord}(a)}{)}^k=e^k=e$. This result is sometimes referred to as Euler’s theorem when applied to modular arithmetic.

Multiplicative Groups Modulo m

The set ${\mathbb{Z}}_m^{\ast }$, consisting of the integers modulo $m$ that are coprime to $m$, forms a group under multiplication modulo $m$. This group is denoted as $⟨{\mathbb{Z}}_m^{\ast };{\odot }_m⟩$.

Proof that ${\mathbb{Z}}_m^{\ast }$ is closed under ${\odot }_m$:

We need to show that if $a$ and $b$ are in ${\mathbb{Z}}_m^{\ast }$, then their product $a{\odot }_{m}b$ (which is equivalent to $ab(\mathrm{mod}m)$) is also in ${\mathbb{Z}}_m^{\ast }$. In other words, if $\text{gcd}(a,m)=1$ and $\text{gcd}(b,m)=1$, then $\text{gcd}(ab,m)=1$.

This follows from the fundamental theorem of arithmetic. If $\text{gcd}(a,m)=1$, then $a$ and $m$ share no common prime factors. Similarly, if $\text{gcd}(b,m)=1$, then $b$ and $m$ share no common prime factors. The prime factorization of $ab$ is simply the combination of the prime factors of $a$ and $b$. Since neither $a$ nor $b$ shares any prime factors with $m$, their product $ab$ also shares no prime factors with $m$. Therefore, $\text{gcd}(ab,m)=1$, and $ab(\mathrm{mod}m)$ belongs to ${\mathbb{Z}}_m^{\ast }$. This demonstrates closure.

The other group axioms (associativity, identity, and inverses) also hold for $⟨{\mathbb{Z}}_m^{\ast };{\odot }_m⟩$.

Euler’s Totient Function $\varphi (m)$

Euler’s totient function, denoted by $\varphi (m)$, counts the number of positive integers less than or equal to $m$ that are coprime to $m$. In other words, $\varphi (m)$ is the size of the set ${\mathbb{Z}}_m^{\ast }$.

Formal Definition

$\varphi (m)=|\{k\in \mathbb{Z}\mid 1\le k\le m\text{ and }\text{gcd}(k,m)=1\}|$

Properties of $\varphi (m)$

• For a prime $p$: $\varphi (p)=p-1$. Since $p$ is prime, all integers less than $p$ are coprime to it.
• For a prime power $p^k$: $\varphi (p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p})$. The integers not coprime to $p^k$ are multiples of $p$: $p,2p,3p,\dots ,p^{k-1}p$. There are $p^{k-1}$ such multiples.
• Multiplicativity: If $\text{gcd}(m,n)=1$, then $\varphi (mn)=\varphi (m)\varphi (n)$. This means that $\varphi$ is a multiplicative function.
• Formula using prime factorization: If $m=p_1^{k_1}{p}_2^{k_2}\dots p_r^{k_r}$ is the prime factorization of $m$, then: $\varphi (m)=m{\prod }_{p|m}(1-\frac{1}{p})=m(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_r})$ where the product is taken over the distinct prime factors of $m$.

Example

• $\varphi (10)=\varphi (2\cdot 5)=\varphi (2)\varphi (5)=(2-1)(5-1)=1\cdot 4=4$. The numbers coprime to 10 are 1, 3, 7, and 9.
• $\varphi (12)=\varphi (2^2\cdot 3)=\varphi (2^2)\varphi (3)=(2^2-2^1)(3-1)=(4-2)(2)=2\cdot 2=4=12(1-\frac{1}{2})(1-\frac{1}{3})=12(\frac{1}{2})(\frac{2}{3})=4$. The numbers coprime to 12 are 1, 5, 7, and 11.

Consequence

As a consequence of Lagrange’s theorem and the fact that $|{\mathbb{Z}}_m^{\ast }|=\varphi (m)$, for any element $a\in {\mathbb{Z}}_m^{\ast }$, we have:

$a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$

This is known as Euler’s theorem.

Explanation:

1. ${\mathbb{Z}}_m^{\ast }$ is a group of order $\varphi (m)$: Euler’s totient function $\varphi (m)$ counts the number of elements in ${\mathbb{Z}}_m^{\ast }$, which are the integers less than or equal to $m$ that are coprime to $m$.

2. Lagrange’s theorem: The order of any element in a finite group divides the order of the group. In our case, the order of any element $a\in {\mathbb{Z}}_m^{\ast }$ must divide $\varphi (m)$.

3. Raising to the power of the group’s order: As we saw earlier as a consequence of Lagrange’s theorem, raising any element to the power of the group’s order results in the identity element. In ${\mathbb{Z}}_m^{\ast }$, the group operation is multiplication modulo $m$, and the identity element is 1. Therefore, for any $a\in {\mathbb{Z}}_m^{\ast }$:

$a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$

This is Euler’s theorem. It’s a generalization of Fermat’s Little Theorem, which applies specifically to the case where $m$ is a prime number. If $m=p$, where $p$ is prime then ${\mathbb{Z}}_p^{\ast }=\{1,2,\dots ,p-1\}$, $\varphi (p)=p-1$, and thus Euler’s theorem says $a^{p-1}\equiv 1(\mathrm{mod}p)$ for $1\le a<p$, which is Fermat’s Little Theorem.

Bijections in Groups and Exponentiation

A crucial concept in understanding group structure and its applications, especially in cryptography, is the idea of bijections induced by exponentiation. Under certain conditions, raising elements of a group to a specific power can create a one-to-one and onto mapping from the group to itself.

Theorem: Let $G$ be a finite group of order $|G|$, and let $e$ be an integer such that $\text{gcd}(e,|G|)=1$. Then the map $f:G\to G$ defined by $f(x)=x^e$ is a bijection.

Proof:

The core of the proof lies in demonstrating the existence of an inverse map. Since $\text{gcd}(e,|G|)=1$, there exists an integer $d$ such that $ed{\equiv }_{|G|}1$. This means there is an integer $k$ where:

$ed=1+k|G|$

We will show that the map $g:G\to G$ defined by $g(x)=x^d$ is the inverse of $f$. Consider the composition of $f$ and $g$:

$g(f(x))=g(x^e)=(x^e{)}^d=x^{ed}$

Using the equation $ed=1+k|G|$, we can rewrite the exponent:

$x^{ed}=x^{1+k|G|}=x^1\cdot x^{k|G|}=x\cdot (x^{|G|}{)}^k$

By a consequence of Lagrange’s theorem, we know that for any element $x$ in a finite group $G$, $x^{|G|}=1$ (the identity element). Therefore:

$x\cdot (x^{|G|}{)}^k=x\cdot 1^k=x\cdot 1=x$

Thus, $g(f(x))=x$, meaning $g$ is the inverse of $f$. The existence of an inverse map proves that $f$ is a bijection.

Significance in Cryptography (RSA):

This theorem has direct applications in the RSA cryptosystem. In RSA, we work with the multiplicative group ${\mathbb{Z}}_N^{\ast }$, where $N=pq$ is the product of two large primes. The order of this group is $\varphi (N)=(p-1)(q-1)$.

• $e$ is chosen such that $\text{gcd}(e,\varphi (N))=1$, and $e$ becomes the public key.
• $d$ is the inverse of $e$ modulo $\varphi (N)$, satisfying $ed\equiv 1(\mathrm{mod}\varphi (N))$. The value $d$ is kept as the private key.

Encryption involves raising the message (represented as a number $m$) to the power of $e$ modulo $N$: $c\equiv m^e(\mathrm{mod}N)$. Decryption involves raising the ciphertext $c$ to the power of $d$ modulo $N$: $m\equiv c^d(\mathrm{mod}N)$. The bijection property ensures that these operations are inverses of each other, allowing the original message to be recovered. This is based on the fact, proven above, that $m^{ed}\equiv m(\mathrm{mod}N)$ since $ed=1+k\varphi (N)$. Thus $(m^e{)}^d=m^{ed}=m^{1+k\varphi (N)}\equiv m(m^{\varphi (N)}{)}^k\equiv m\cdot 1^k\equiv m(\mathrm{mod}N)$.

Therefore, the concept of bijections induced by exponentiation is fundamental to the security and functionality of the RSA cryptosystem.

RSA (Public Key Encryption)

RSA is a widely used public-key cryptosystem that relies on the mathematical properties of modular arithmetic and prime numbers. It enables secure communication over insecure channels, allowing for both encryption and digital signatures.

Public-Key Cryptosystems:

In a public-key cryptosystem, each participant has a pair of keys: a public key ($P_B$ for Bob) and a private key ($S_B$ for Bob). The public key can be freely distributed, while the private key must be kept secret. Anyone can encrypt a message using the recipient’s public key, but only the recipient, possessing the corresponding private key, can decrypt the message. Crucially, while the channel itself may be insecure, an authentic channel for distributing public keys is essential for the security of the system. If an adversary can tamper with the public key distribution, they can substitute their own public key, allowing them to intercept and decrypt messages intended for the original recipient.

Mechanical Analogy:

A mechanical analog for a public-key system is a lockbox with a slot. Anyone can place a message in the slot and close the lock (encrypt), but only the person with the key can open the lock and retrieve the message (decrypt).

RSA Algorithm:

The RSA algorithm involves the following steps:

1. Key Generation:

• Alice generates two large prime numbers, $p$ and $q$.
• She computes $n=pq$ and $\varphi (n)=(p-1)(q-1)$.
• Alice selects a public exponent $e$ such that $1<e<\varphi (n)$ and $\text{gcd}(e,\varphi (n))=1$.
• She computes the private exponent $d$ such that $ed\equiv 1(\mathrm{mod}\varphi (n))$. This $d$ acts as the multiplicative inverse of $e$ within ${\mathbb{Z}}_{\varphi (n)}^{\ast }$. This implies that there is a $k$ for which $ed=1+k\varphi (n)$.
• She publishes the pair $(n,e)$ as his public key and keeps $d$ as his private key.

2. Encryption (by Bob): Bob converts his message into an integer $m$ such that $0\le m<n$. He then computes the ciphertext $c$ as $c\equiv m^e(\mathrm{mod}n)$.

3. Decryption (by Alice): Alice decrypts the ciphertext $c$ by computing $m\equiv c^d(\mathrm{mod}n)$. The bijection property discussed earlier guarantees correct decryption: since $ed\equiv 1(\mathrm{mod}\varphi (n))$, $ed=1+k\varphi (n)$ and we know $c^d\equiv (m^e{)}^d\equiv m^{ed}\equiv m^{1+k\varphi (n)}\equiv m(\mathrm{mod}n)$, so Alice recovers the original message $m$.

In practice, $m$ is typically limited to 2048 bits or more to avoid certain types of attacks, since there is no longer a bijection to arbitrarily large m.

Deterministic Encryption and its Implications:

RSA encryption is deterministic. This means that encrypting the same message always produces the same ciphertext. This can be a vulnerability if the message space is small (e.g., “yes” or “no”). An attacker could potentially encrypt all possible messages with the public key and compare the results to the intercepted ciphertext, effectively decrypting the message. Therefore, in practice, padding schemes are used to introduce randomness and prevent such attacks.

Digital Signatures:

Digital signatures provide a way to verify the authenticity and integrity of a message. Unlike encryption, which protects the confidentiality of a message, digital signatures ensure that a message has not been tampered with and originated from the claimed sender.

RSA can also be used for digital signatures. The process is similar to encryption, but the roles of the keys are reversed. The sender signs the message using their private key, and anyone can verify the signature using the sender’s public key and a known hash function $h()$. This verifies both authenticity of message and its origin.

Continue here: 17 Rings, Polynomial Rings, Integral Domains, Units