Groups

Groups

• Group: Set $\mathbb G$ and a binary operation $\circ$ defined on $\mathbb G$ such that:

  • (Closure): For all $g_1, g_2 \in \mathbb{G}$, it holds that $g_1 \circ g_2 \in \mathbb{G}$.
  • (Identity): There exists an identity element $e \in \mathbb{G}$ s.t. $e \circ g = g = g \circ e$ for all $g \in \mathbb{G}$.
  • (Inverse): For every element $g \in \mathbb{G}$ there exists an inverse element $h \in \mathbb{G}$ s.t. $g \circ h = e = h \circ g$.
  • (Associativity): For all $g_{1}, g_{2}, g_{3} \in \mathbb{G}$, $g_{1} \circ\left(g_{2} \circ g_{3}\right)=\left(g_{1} \circ g_{2}\right) \circ g_{3}$.

  Order of a finite group $\mathbb G$, denoted $| \mathbb G |$, is the number of elements in $\mathbb G$.

Abelian Groups

• Abelian Group: corresponds to a set $\mathbb G$ and a binary operation $\circ$ defined on $\mathbb G$ such that:
  • (Closure): For all $g_1, g_2 \in \mathbb{G}$, it holds that $g_1 \circ g_2 \in \mathbb{G}$.
  • (Identity): There exists an identity element $e \in \mathbb{G}$ s.t. $e \circ g = g = g \circ e$ for all $g \in \mathbb{G}$.
  • (Inverse): For every element $g \in \mathbb{G}$ there exists an inverse element $h \in \mathbb{G}$ s.t. $g \circ h = e = h \circ g$.
  • (Associativity): For all $g_{1}, g_{2}, g_{3} \in \mathbb{G}$, $g_{1} \circ\left(g_{2} \circ g_{3}\right)=\left(g_{1} \circ g_{2}\right) \circ g_{3}$.
  • (Commutativity): For all $g_1, g_2 \in \mathbb{G}$, $g_1 \circ g_2 = g_2 \circ g_1$.

Cancelation Law

• Theorem (Cancelation Law). Let $\mathbb G$ be a group and $a, b, c \in \mathbb{G}$. If $ac = bc$, then $a = b$. In particular, if $ac = c$, then $a$ is the identity in $\mathbb{G}$.

Group Exponentiation

• The rules of integer exponentiation hold also for Group Exponentiation:

  $$g^{m} \cdot g^{m^{\prime}}=g^{m+m^{\prime}},\left(g^{m}\right)^{m^{\prime}}=g^{m m^{\prime}}, g^{1}=g$$

• If $\mathbb G$ is an abelian group, and $g, h \in \mathbb G$, then $g^m \cdot h^m = (gh)^m$.

Group under addition modulo $N$: $\mathbb{Z}_N$

• $\mathbb{Z}_N = \{0, \ldots, N - 1\}$ under addition modulo $N$, i.e., $a + b := [a + b \bmod N]$ is an Abelian group.
  • Identity is $0$.
  • Inverse of $g$ is $[(N- g) \bmod N]$, since $g + (N- g) = 0 \bmod N$.
  • Associativity, Commutativity hold by usual properties of addition.
  • Order of this group is $N$.
• $m \cdot g=\underbrace{g+\ldots+g}_{m \text { times}} \bmod N$: Group Exponentiation can be computed efficiently by standard arithmetic.

Subgroups

• Definition. If $\mathbb G$ is a group, a set $\mathbb{H} \subseteq \mathbb{G}$ is a subgroup of $\mathbb G$ if $\mathbb{H}$ itself forms a group under the same operation. Every group $\mathbb G$ always has the trivial subgroups $\mathbb G$ and $\{1\}$. $\mathbb{H}$ is a strict subgroup of $\mathbb G$ if $\mathbb H \ne \mathbb G$.

Fermat’s Little Theorem

• Theorem (Fermat’s Little Theorem):

  Let $\mathbb G$ be a finite group of order $m = | \mathbb G |$. Then for any $g \in \mathbb G$, it holds that $g^m = 1$.

• Corollary 1 (Fermat’s Little Theorem):

  Let $\mathbb G$ be a finite group of order $m$. Then for any $g \in \mathbb G$, and any integer $x$, we have $g^x = g^{[x \bmod m]}$.

• Corollary 2 (Fermat’s Little Theorem):

  Let $\mathbb G$ be a finite group of order $m$. Let $e > 0$ be an integer, and define the function, $f_e : \mathbb{G} \rightarrow \mathbb{G}$ by $f_e(g) = g^e$.

  • If $\gcd(e, m) = 1$, then $f_e$ is a permutation, i.e., a bijection.
  • Moreover, if $d = e^{-1} \bmod m$, then $f_d$ is the inverse of $f_e$.

Group under multiplication modulo $N$: $\mathbb{Z}^*_N$

• $\mathbb{Z}^*_N :=$ invertible elements in $\{1,\ldots, N - 1\}$ under multiplication modulo $N$

  $:= \{b \in \{1,\ldots, N- 1\}|\gcd(b, N) = 1\}$

• Proposition: $\mathbb{Z}^*_N$ is an abelian group under multiplication mod $N$.

• $g^m=\underbrace{g \cdot g \cdot \ldots \cdot g}_{m \text { times}} \bmod N$: Group Exponentiation can be computed efficiently in this group.

Euler’s totient function $\phi(N)$

• Euler’s totient function is defined as $\phi(N) :=$ the number of invertible elements modulo $N$.

  In other words, $\phi(N) = |\{g \in \{1,\ldots, N - 1\} : \gcd(g, N) = 1 \} | = |\mathbb{Z}^*_N|$ is Euler’s phi or totient function.

  1. If $N$ is prime, then $\phi(N) = N- 1$.

  2. If $N = p \cdot q$, for distinct primes $p, q$, then

     $$\begin{array}{l}\phi(N)=(N-1)-\mid\{\text {multiples of } p\}|-|\{\text {multiples of } q\} \mid \\\phi(N)=(N-1)-|\{p, 2 p, \ldots,(q-1) p\}|-|\{q, 2 q, \ldots,(p-1) q\}| \\\phi(N)=(N-1)-(q-1)-(p-1)=N-q-p+1=(p-1)(q-1)\end{array}$$

— Mar 14, 2023

Groups by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.