NT01_L02.5 - HackMD

###### tags: `Number Theory` `NT01` # L02.5 Intro to Group and Permutation Cipher --- Last Week - Euclidean Algorithm - Affine cipher --- ## This week - Groups of Modular Arithmetic - Permutation Group - Permutation Cipher --- 1.1 Example $(\Bbb{Z}_6, \times)$ **$(\Bbb{Z}_6, \times)$ or $(\{0,1,2,3,4,5\}, \times)$** Check: 1. For all $a, b, c \in G$, $(a*b)*c = a*(b*c)$ >yes, e.g. $(1\times2)\times3 = 0 = 1\times(2\times3)$ 2. Exit $e \in G$, that for any $g \in G$, $g*e = e*g = g$ >yes, 1 is that e, identity element 3. for any $g \in G$, exit $h \in G$, that $g * h = e$ > **Oop!** 0, 2, 3, and 4 have no Inverse!! But we can Denote $\Bbb{Z}^{*}_6$, the subset of $\Bbb{Z}_6$ that coprime with 6 Now your turn to check if $\Bbb{Z}^{*}_6$ satisfy Group Definition ---- 1.2 Cayley Table It is a bit tedious to calculate every binary output for a group, especially when Group is large. So we will Use Cayley Table to present Group Operations. (We will use Python Later ..) **Caylay Table for $(\Bbb{Z}^{*}_6, +)$** | $+_5$ | 0 | 1 | 2 | 3 | 4 | 5 | | ----- | --- | --- | --- | --- | --- | --- | | 0 | 0 | 1 | 2 | 3 | 4 | 5 | | 1 | 1 | 2 | 3 | 4 | 5 | 0 | | 2 | 2 | 3 | 4 | 5 | 0 | 1 | | 3 | 3 | 4 | 5 | 0 | 1 | 2 | | 4 | 4 | 5 | 0 | 1 | 2 | 3 | | 5 | 5 | 0 | 1 | 2 | 3 | 4 | Quiz: Can you draw Caylay Table $\Bbb{Z}^{*}_6$ by your self? ---- 1.4 Cayley Table **Caylay Table for $(\Bbb{U}_6, \times)$** | $\times_6$ | 1 | 5 | | ---------- | --- | --- | | 1 | 1 | 5 | | 5 | 5 | 1 | *Think about it at home:* Can we confirm that, for prime p, $\Bbb{Z}^{*}_p = \{1,2,\dots,p-1\}$? How can you explain it from the perspective of Group Definition? --- 2.1 Another View of Cayley Table Let's draw a smaller table **Caylay Table for $(\Bbb{Z}_3, +)$** | $+_3$ | 0 | 1 | 2 | | ----- | --- | --- | --- | | 0 | 0 | 1 | 2 | | 1 | 1 | 2 | 0 | | 2 | 2 | 0 | 1 | Let's denote following permutations: $id = (\begin{smallmatrix} 0 & 1 & 2\\ 0 & 1 & 2 \end{smallmatrix})$, $a_1 = (\begin{smallmatrix} 0 & 1 & 2\\ 1 & 2 & 0 \end{smallmatrix})$, $a_2 = (\begin{smallmatrix} 0 & 1 & 2\\ 2 & 0 & 1 \end{smallmatrix})$ ---- 2.2 Permutation Group $id = (\begin{smallmatrix} 0 & 1 & 2\\ 0 & 1 & 2 \end{smallmatrix})$, $a_1 = (\begin{smallmatrix} 0 & 1 & 2\\ 1 & 2 & 0 \end{smallmatrix})$, $a_2 = (\begin{smallmatrix} 0 & 1 & 2\\ 2 & 0 & 1 \end{smallmatrix})$ We define a binary operation, "composition" of two permutation as example below: $a_1 \circ a_2 := (\begin{smallmatrix} 0 & 1 & 2\\ 1 & 2 & 0 \end{smallmatrix})(\begin{smallmatrix} 0 & 1 & 2\\ 2 & 0 & 1 \end{smallmatrix}) = (\begin{smallmatrix} 0 & 1 & 2\\ 0 & 1 & 2 \end{smallmatrix}) = id$ We can also check that: $a_1 \circ a_1 := (\begin{smallmatrix} 0 & 1 & 2\\ 1 & 2 & 0 \end{smallmatrix})(\begin{smallmatrix} 0 & 1 & 2\\ 1 & 2 & 0 \end{smallmatrix}) = (\begin{smallmatrix} 0 & 1 & 2\\ 2 & 0 & 1 \end{smallmatrix}) = a_2$ $a_2 \circ a_2 := (\begin{smallmatrix} 0 & 1 & 2\\ 2 & 0 & 1 \end{smallmatrix})(\begin{smallmatrix} 0 & 1 & 2\\ 2 & 0 & 1 \end{smallmatrix}) = (\begin{smallmatrix} 0 & 1 & 2\\ 1 & 2 & 0 \end{smallmatrix}) = a_1$ So $(\{id,a_1, a_2\}, \circ)$ also form a Group, We call this Permutation Group. There are more interesting connection between Permutations and Modular of Integers, we will introduce them in the next Module NT02. ---- 2.3 Permutation Cipher Permutation Cipher plays an important role in contemporary Cryptograph An example: Our Message: "hello", Our Chosen permutation as $key := (\begin{smallmatrix} 0 & 1 & 2 & 3 & 4\\ 2 & 0 & 1 & 4 & 3 \end{smallmatrix}$) So our encrypted message would be "elhol" We can choose larger n for more serious cases, as n goes larger, the number of posible permutations, $n!$, goes extremely large! For example, 64 bit strings, have $\approx 1.3*10^{89}$ possible ways of permutation ---