20161003

Please Login to access more options.

Today

Definition (A Closed Set Of Permutations)

We say that a set of permutations is closed if the set $S$ is equal to its span, so notionally we write $$S=\text{span}{(S)}.$$ In other words, we say that $S$ is closed if the set $S$ already contains every composition combination of permutations of elements in $S$.

Problem 24 (The Span Of A Set Of Permutations Is Closed)

Let $S$ be a set of permutations of $X$. Show that $\text{span}(S)$ is closed. In other words, show that once you form the span of a set $S$ of permutations of $X$, you cannot obtain any new permutations by spanning the span. For this reason, we'll often refer to $\text{span}(S)$ as the closure of $S$.

Problem 27 (Matrix Encryption Mod 5)

In the Problem (Simple Matrix Encryption), we took a plain text message written in columns of a matrix $M$ and a matrix $A$ and used the product $AM$ to encode a message. Let's now combine matrix encryption with modular arithmetic to obtain a new encryption scheme. Once we have done this, we'll be one step closer to understanding modern encryption techniques. To simplify our work, let's use a small alphabet consisting of 5 letters. Instead of using the set $S=\{a,b,c,d,e\}$, let's just use numbers for our letters and we'll consider the alphabet $S=\{0,1,2,3,4\}=\mathbb{Z}_5$. Given the plain text "bad bed" or "10 31 43", we can encode it in the columns of the matrix $$M=\begin{bmatrix}1&3&4\\0&1&3\end{bmatrix}.$$ An 2 by 2 encryption key using coefficients mod 5 is a 2 by 2 matrix $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$ where $a,b,c,d\in \mathbb{Z}_5$. Here are the steps to our encryption scheme.

• First convert the plain text to a matrix $M$ where the letters are place in the matrix top to bottom, column by column.
• Take the encryption key $A$ and compute the product $AM$.
• Reduce all the entries in $AM$ mod 5. So the cipher text only consists of the numbers in $\mathbb{Z}_5$.

Answer the following questions.

1. Suppose we let $A=\begin{bmatrix}4&2\\1&3\end{bmatrix}$. Why is this matrix not suitable as an encryption key? (Hint: what is the determinant, and why is that a problem?)
2. Suppose we let $A=\begin{bmatrix}2&1\\4&3\end{bmatrix}$. The inverse of $A$ if we ignore modular arithmetic is $\frac{1}{2}\begin{bmatrix}3&-1\\-4&2\end{bmatrix}$. We know that we can replace $-4$ with $1$ when working modular 5. Similarly we can replace $-1$ with a positive number. We need to find the multiplicative inverse of 2 when working modular 5. Find a value $b\in \mathbb{Z}_5$ so that $2b\mod 5=1$. This number $b$ is the inverse of $2$ modular 5.
3. State a matrix $B$ with coefficients in $\mathbb{Z}_5$ so that $AB$ is the identity matrix after reducing each entry mod 5. Actually perform the product by hand, and show how this matrix product reduces to the identity.

Definition (Modular Multiplicative Inverse and $U(n)$)

Let $n$ be a positive integer, and let $a\in \mathbb{Z}_n$. Then the modular multiplicative inverse of $a \mod n$ is an integer $b\in \mathbb{Z}_n$ such that $(ab)\mod n=1$. If such an integer exists, then we'll write $a^{-1}\mod n$ to represent the modular multiplicative inverse. If the context is clear, we may just refer to this as the inverse instead of the modular multiplicative inverse. We'll use the notation $U(n)$ to represent the set of elements in $\mathbb{Z}$ that have a modular multiplicative inverse. Notationaly, we write $$U(n)=\{a\in\mathbb{Z}_n\mid \text{ there exists } b\in \mathbb{Z}_n \text{ such that } (ab)\mod n=1\}.$$

The Sage code "inverse_mod(a,n)" will compute the modular multiplicative inverse of $a\mod n$ or return an error.

inverse_mod(7, 11)

Problem 28 (Computing Multiplicative Inverses For Small N)

To use modular arithmetic in matrix encryption, we must be able to find the modular multiplicative inverse of $a \mod n$. For each $n\leq 13$ and $a\in \mathbb{Z}_n$, we now compute the inverse of $a\mod n$ or explain why it does not have one.

1. Why does $0\mod n$ never have an inverse?
2. What is the multiplicative inverse of $1\mod n$?
3. For $n=3$, what is the multiplicative inverse of $a=2$.
4. For $n=4$, show that 2 does not have an inverse by computing $2\cdot 0$, $2\cdot 1$, $2\cdot 2$, and $2\cdot 3$ all modulo $4$. What is $3^{-1}\mod 4$?
5. For each $n$ between 5 and 13, create a table that shows the inverse of each $a\in \mathbb{Z}_n$. List the elements of $\mathbb{Z}_n$ along the top row, and beneath each element list the multiplicative inverse, or cross off the number if there is no multiplicative inverse.

When you are done you should have a list of the elements of $U(n)$ for each $n$ up to 13, as well as the inverse of each element in $U(n)$. Do you see any patterns?

For $n=9$, you should obtain a table somewhat similar to the following table.

Definition (Cayley Graph Of A Span Of Permutations)

Let $X$ be a set. Let $S$ be a set of permutations of $X$. Then a Cayley graph of $H=\text{span} (S)$ generated by $S$, which we'll write as $(H,S)$, is a colored directed graph that satisfies the the following three properties:

1. The vertex set is $\text{span} (S)$. Each vertex corresponds to a permutation.
2. Each element $s \in S$ is assigned a unique color which we'll denote by $c_s$.
3. For each color $c_s$, and each vertex $\sigma$, we draw the colored arrow $(\sigma ,s \circ \sigma)$.

Most of the time we assume that $S$ does not contain the identity. However, if it does contain the identity, then we just draw a colored loop $(\sigma,\sigma)$ at each vertex.

Problem 29 (Cayley Graph Patterns)

In each scenario below, you should draw a Cayley graph.

1. Let $X=\mathbb{Z}$, an infinite set. Consider the permutation $\phi_1:\mathbb{Z}\to \mathbb{Z}$ defined by $\phi_1(x)=x+1$. This permutation shifts elements in $\mathbb{Z}$ right one, with no wrap around. If we let $S=\{\phi_1\}$, give a rough sketch of the Cayley graph of $\text{span}(S)$. It's a rough sketch of the graph because there are infinitely many vertices.
2. How would you change your graph in part 1 if instead you used $S=\{\phi_2,\phi_3\}$, where these are shifts right 2 and 3 respectively?
3. Suppose that $X$ is a set, and that $S$ contains a single automorphism $s$ of $X$. Suppose also that we know $s^6$ is the identity (so following the arrow colored $c_s$ 6 times will return us to where we started). Construct a Cayley graph of $\text{span}(S)$. Is there more than one right answer to this?
4. Suppose that we know $S$ contains two elements $a$ and $b$. We also know that $a^2$ and $b^4$ are both the identity. In addition, we know that $a\circ b=b\circ a$, so if we start somewhere and follow the arrows colored $c_a$ and then $c_b$, then we should end up at the same place if we followed the arrows colored $c_b$ and then $c_a$. Construct a graph that satisfies these relationships. We'll often write this as $$\left<a,b\mid a^2=id, b^4=id, a\circ b=b\circ a\right>.$$

For more problems, see AllProblems