Subgroup

DEFINITION: Let $(G, \star)$ be an Abelian group. A subset $H \subseteq G$ is a subgroup of $G$ if $(H, \star)$ is also a group. ($H \le G$) // trivial subgroups: $\{1\},G;\{0\},G$

• Multiplicative: $G = \mathbb{Z}_6^* = \{1,5\}$ has two subgroups $\{1\},G$
• Additive: $G = \mathbb{Z}_6 = \{0,1,2,3,4,5\}$ has a non trivial subgroup $H = \{0,2,4\}$

THEOREM: Let $(G, \cdot)$ be an Abelian group. Let $\langle g \rangle = \{g^k : k \in \mathbb{Z}\}$ be a subset of $G$, where $g \in G$. Then $\langle g \rangle \le G$.

• Closure: $g^a \cdot g^b = g^{a+b} \in \langle g \rangle$
• Associative: $g^a \cdot (g^b \cdot g^c) = g^{a+b+c} = (g^a \cdot g^b) \cdot g^c$
• Identity element: $g^0 \cdot g^a = g^a \cdot g^0 = g^a$
• Inverse: $g^a \cdot g^{-a} = g^{-a} \cdot g^a = g^0$
• Communicative: $g^a \cdot g^b = g^{a+b} = g^{b+a} = g^b \cdot g^a$

Cyclic Group

DEFINITION: An Abelian group $(G, \cdot)$ is cyclic if there exists $g \in G$ s.t. $G = \langle g \rangle$.

• $g$ is called a generator of $G$.

EXAMPLE:$\mathbb{Z}_{10}^* = {[1]_{10}, [3]_{10}, [7]_{10}, [9]_{10}} = \langle [3]_{10} \rangle$

• $g = [3]_{10}$
• $g^0 = [1]_{10}, g^1 = [3]_{10}, g^2 = [9]_{10}, g^3 = [27]_{10} = [7]_{10}$

REMARK: Let $G$ be a finite group and let $g \in G$. Then $\langle g \rangle = \{g^1, g^2, \dots\}$

• If $G = \langle g \rangle$ is a cyclic group of order $m$, then $G = \{g^0, g^1, \dots, g^{m-1}\} = \{g^1, \dots, g^{m-1}, g^m\}$.

THEOREM: For any prime $p$, the group $\mathbb{Z}_p^*$ is a cyclic group.

• proof omitted (beyond the scope of the course)

EXAMPLE:$p = 23$; $\mathbb{Z}_p^*$ is a cyclic group of order 22 and has a subgroup of order 11

• $\alpha = 5; \langle\alpha\rangle = \{5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14, 1, 5, 2\}$
• $|\mathbb{Z}_p^*| = p – 1 = 22; o(5) | 22; o(5) \in \{1, 2, 11, 22\}; 5^1 = 5, 5^2 = 2, 5^{11} = 22$
• $g = 2; \langle g \rangle = \{g^1, \dots\} = \{2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1\}$ is a subgroup of order $q = 11 = (p – 1)/2$

EXAMPLE:$\mathbb{Z}_p^*$ is a cyclic group and $G = \langle g \rangle$ is a cyclic subgroup.

• $p=$ 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624227998859
  • $p$ is a prime; $\alpha = 2$; $o(\alpha) = (p – 1)/2 := q$ // $o(\alpha) | (p – 1), o(\alpha) \in \{1, 2, q, p\}$
  • $\mathbb{Z}_p^* = \langle \alpha \rangle = \{\alpha^0, \alpha^1, \dots, \alpha^{p-2}\} = \{\alpha^1, \dots, \alpha^{p-2}, \alpha^{p-1}\}$ is a cyclic group of order $p – 1$
• $q =$ 89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208311246423715319737062188883946712432742638151109800623047059726541476042502884419075341171231440736956555270413618581675255342293149119973622969239 858152417678164812113999429
  • $q = (p – 1)/2$ is a prime; $g = \alpha^2 = 4$
  • $G = \langle g \rangle = \{g^0, g^1, \dots, g^{q-1}\}$
    $= \{\alpha^0, \alpha^2, \dots, \alpha^{2q-2}\}$
    $= \{\alpha^2, \dots, \alpha^{2q-2}, \alpha^{2q}\}$ is a subgroup of $\mathbb{Z}_p^*$ of order $q$

DLOG and CDH

DEFINITION: Let $G = \langle g \rangle$ be a cyclic group of order $q$. For every $h \in G$, there exists $x \in \{0,1,\dots,q-1\}$ such that $h = g^x$. The integer $x$ is called the discrete logarithm (DLOG) of $h$with respect to$g$.

• Notation: $x = \log_g h$

DLOG Problem:$G = \langle g \rangle$ is a cyclic group of order $q$

• Input:$q, G, g$ and $h \in G$; Output:$\log_g h$

CDH Problem:Computational Diffie-Hellman

• Input:$q, G, g$ and $A = g^a, B = g^b$ for $a, b \leftarrow \{0,1,\dots,q-1\}$; Output:$g^{ab}$

Hardness of DLOG and CDH: If $p = 2q + 1$ is a safe prime and $G$ is the order $q$ subgroup of $\mathbb{Z}_p^*$, then the best known algorithm for DLOG/CDH runs in time $\exp\left(O(\sqrt{\ln q \ln \ln q})\right)$.

• $q \approx 2^{2048}$

Diffie-Hellman Key Exchange

CONSTRUCTION:$G = \langle g \rangle$ is a cyclic group of prime order $q$

• Alice:$a \gets \mathbb{Z}_q$, $A = g^a$; send $(q, G, g, A)$ to Bob
• Bob:$b \gets \mathbb{Z}_q$, $B = g^b$; send $B$ to Alice; output $k = A^b$
• Alice: output $k = B^a$

Whitfield Diffie, Martin E. Hellman: New directions in Cryptography, IEEE Trans. Info. Theory, 1976
Turing Award 2015

EXAMPLE:$p = 23$; $\mathbb{Z}_{23}^* = \langle 5 \rangle$; $G = \langle 2 \rangle$, $q = |G| = 11$, $g = 2$

Combinatorics

1666, Leibniz (1646-1716), De Arte Combinatoria

Enumerative combinatorics

• permutations, combinations, partitions of integers, generating functions, combinatorial identities, inequalities …

Designs and configurations

• block designs, triple systems, Latin squares, orthogonal arrays, configurations, packing, covering, tiling …

Graphtheory

• graphs, trees, planarity, coloring, paths, cycles, …

Extremal combinatorics

• extremal set theory, probabilistic method …

Algebraic combinatorics

• symmetricfunctions, group, algebra, representation, group actions …

Sets and Functions

DEFINITION: A set is an unordered collection of elements

• $a \in A; a \notin A$; roster method, set builder; empty set $\emptyset$, universal set
• $A = B; A \subseteq B; A \subset B; A \cup B; A \cap B; \bar{A}$

DEFINITION: Let $A, B \neq \emptyset$ be two sets. A function (map)$f: A \to B$ assigns a unique element $b \in B$ for all $a \in A$.

• injective:$f(a) = f(b) \implies a = b$
• surjective:$f(A) = B$
• bijective: injective and surjective

Cardinality of Sets

DEFINITION: Let $A$ be a set. $A$ is a finite set if it has finitely many elements; Otherwise, $A$ is an infinite set.

• The cardinality$|A|$ of a finite set $A$ is the number of elements in $A$.

EXAMPLE:$\emptyset, \{1\}, \{x: x^2 – 2x – 3 = 0\}, \{a, b, c, …, z\}$ are all finite sets; $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$ are all infinite sets.

DEFINITION: Let $A, B$ be any sets. We say that $A, B$have the same cardinality ($|A| = |B|$) if there is a bijection $f: A \to B$.

• We say that $|A| \le |B|$ if there exists an injection $f: A \to B$.
  • If $|A| \le |B|$ and $|A| \neq |B|$, we say that $|A| < |B|$.

THEOREM: Let $A, B, C$ be any sets. Then

• $|A| = |A|$
• $|A| = |B| \implies |B| = |A|$
• $|A| = |B| \land |B| = |C| \implies |A| = |C|$

EXAMPLE:$|\mathbb{Z}^+| = |\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}^+| = |\mathbb{Q}|$

• $f: \mathbb{Z}^+ \to \mathbb{N}, \quad x \mapsto x – 1$
• $f: \mathbb{Z} \to \mathbb{N}, \quad f(x) = \begin{cases} 2x & x \ge 0 \\ -(2x + 1) & x < 0 \end{cases}$

EXAMPLE:$|\mathbb{R}^+| = |\mathbb{R}| = |(0,1)| = |[0,1]|$

• $f: \mathbb{R} \to \mathbb{R}^+, \quad x \mapsto 2^x$
• $f: (0,1) \to \mathbb{R}, \quad x \mapsto \tan(\pi(x – 1/2))$
• $f: [0,1] \to (0,1)$
  • $f(1) = 2^{-1}, f(0) = 2^{-2}, f(2^{-n}) = 2^{-n-2}, n = 1, 2, 3, \dots$
  • $f(x) = x$ for all other $x$