20161014

Please Login to access more options.

Today

Definition (Affine Encryption Key)

Suppose we have an alphabet with $n$ letters. Set up a 1-1 correspondence between the letters in your alphabet and the integers 0 to $n-1$. As an example, we could let $n=27$ for the standard alphabet with 26 letters and a space (the 27th letter which we'll number 0), and then use the correspondence in the table below.

Pick an integer $m\geq n$. Then an affine encryption key is an invertible function \( f:\mathbb{Z}_m \to \mathbb{Z}_m\) defined by $$f(x)=ax+b\pmod {m}$$ for some $a,b\in\mathbb{Z}_m$.

Problem 43 (Affine Encryption Key Introduction)

If we let $m=31$, then we can use the function $f(x)=5x+12\pmod m$ to encrypt the message "save them" by (1) swapping the letters to the numbers (19,1,22,5,0,20,8,5,13) and then (2) applying $f(x)$ to each letter to obtain the encrypted numbers (14, 17, 29, 6, 12, 19, 21, 6, 15).

1. Find $c,d\in \mathbb{Z}_{31}$ so that the inverse of $f$ is $f^{-1}(x)=cx+d$ where $c,d\in \mathbb{Z}_{31}$.
2. If instead we let $m=27$, then find the inverses of $f(x)=2x+17\pmod{27}$ or explain why it cannot be done.
3. Give an example of nonzero $a,b\in \mathbb{Z}_{27}$ so that $f(x)=ax+b\pmod{27}$ is not invertible.

Because of how we defined groups, anytime we span a collection of permutations of a set $X$ we should get a group. The next problem has you show this. Each question can be answered by referring to things we have already shown. Feel free to look at the pages September 2016 and October 2016 for a list of all the problems we have solved each day. If you have not yet printed the work we are doing, I would suggest that you print a copy for reference as you work on new problems.

Problem 45 (Spans Of Permutations Are Subgroups)

Let $X=\{1,2,3,\ldots,n\}$. Let $S_n$ be the set of all permutations of $X$ (so we know there are $n!$ such permutations).

1. Show that $S_n$ is a group under function composition $\circ$.
2. If $H$ is a subset of $S_n$ that is closed (under composition combinations of permutations), prove that $H$ is a group under function composition.
3. Let $S$ be a nonempty subset of $S_n$. Show that $\text{span}(S)$ is a group under function composition.

In the previous problem, we saw if $S\subseteq S_n$ then $\text{span}(S)$ is a not only just a subset of the group $S_n$, but is itself a group. The operation we use in the smaller group $(\text{span}(S),\circ)$ comes from the operation we used in the larger group $(S_n,\circ)$. Because of this close connection, we call $\text{span}(S)$ a subgroup of $S_n$ and write $\text{span}(S)\leq S_n$. Let's now make a formal definition.

Definition (Subgroup)

Let $(G,\cdot)$ be a group, and let $H$ be a nonempty subset of $G$. Then $H$ is called a $\textdef{subgroup}$ of $G$ if the following hold:

1. $\textbf{[Closure]}$ for all $h,k\in H$ we have $h\cdot k\in H$, and
2. $(H,\cdot)$ is a group.

When $H$ is a subgroup of $G$, we write $H\le G$. Any subgroup of $G$ that is not equal to $G$ itself we call a $\textdef{proper subgroup}$. The subset of $G$ consisting of just the identity we call the $\textdef{trivial subgroup}$.

In the proof of problem Characterizing Closed Sets Of Permutations, we did not need to use the first and fourth properties listed to show that the set of permutations $H$ was closed. The next problem replicates this, but now in terms of subgroups instead of in terms of closed sets of permutations.

Problem 46 (The Subgroup Test - Subgroups Are Subsets That Are Closed Under Products And Taking Inverses)

A graph of the first 1000 values of $\varphi(n)$. See Wikipedia.

Problem 48 (Orders Of $\mathbb{Z}_n$ And $U(n)$ And Their Elements)

We've already shown that $\mathbb{Z}_n$ under addition mod $n$ and $U(n)$ under multiplication mod $n$ are groups.

1. For each $n$ between 2 and 10, compute the order of $Z_n$ and the order of each element of $\mathbb{Z}_n$. Organize your work into a table where you first make a list of the elements, and then underneath each element state the order. For example, if $n=6$ then our table would look like the one below. $$\begin{array}{|c|c|c|c|c|c|c|} \hline \text{Element}&0&1&2&3&4&5\\\hline \text{Order}&1&6&3&2&3&6\\\hline \end{array}$$
2. For each $n$ between 2 and 10, compute the order of $U(n)$ (state $\varphi(n)$) and then compute the order of each element of $U(n)$. You can check your work with the sage code below. I kept the numbers under 10 because you can do these by hand (or in your head) fairly quickly. Make sure you do enough by hand that you feel comfortable with this process.
3. You should have noticed that $U(8)$ and $U(10)$ both have order 4. Is there a 1-1 correspondence between these two groups that matches elements with the same order?

Here's some Sage code you can use to check your computations with $U(n)$.

for n in (2..20):
 Zn = Integers(n)
 Un = [x for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
 show(table(["U("+str(n)+r") has order $\varphi($"+str(n)+"$)=$"+str(len(Un))+
             ".The elements, with orders below them, are listed below."]))
 orders=[x.multiplicative_order() for x in Un] #This computes the multiplicative order of each element.
 show(table([Un,orders])) #This creates a table of elements (top row) and their orders (bottom row).