# Review Exercises (Set B)

1. Find all solutions to $26x \equiv 14\pmod{82}$

2. Consider the set $S$ of numbers of the form $a + b\sqrt{7}$ where $a$ and $b$ are integers. Find a number is this form that serves as a unit for the set $S$.

3. Prove the converse of Wilson's theorem is true.

4. Encode the message "HILLCODE" with a Hill Cipher and encoding matrix given by

$$E=\left[ \begin{array}{cc} 1 & 13 \\ 2 & 7 \end{array} \right]$$

5. Encode the message "RUN AWAY NOW" with a Vigenere cipher using the keyword "YELLOW"

6. Vector $W$ gives the distribution of A's, B's, C's, D's, and E's in a particular Kryptonian plaintext message, respectively. The other three vectors give the probability distributions of these letters (in the same order) for messages encoded with simple shift of 1, 2, or 3 letters, respectively. Which of the three probability vectors most closely matches $W$? (To be more precise, in terms of vectors, the one that most closely matches $W$ will form the smallest angle with $W$.)

$$\begin{array}{c} W=(0.35, 0.3, 0.1, 0.05, 0.2)\\\\ P_1 = (0.35, 0.05, 0.1, 0.2, 0.3)\\ P_2 = (0.3, 0.35, 0.05, 0.1, 0.2)\\ P_3 = (0.2, 0.3, 0.35, 0.05, 0.1) \end{array}$$

7. Suppose $M$ is a linear transformation that both operates on, and produces 2-dimensional vectors. If the following are true
$$M\begin{pmatrix}2\\0\end{pmatrix} = \begin{pmatrix}1\\3\end{pmatrix} \quad \quad \textrm{and} \quad \quad M\begin{pmatrix}4\\6\end{pmatrix} = \begin{pmatrix}1\\-3\end{pmatrix}$$
Find $\displaystyle{M\begin{pmatrix}2\\5\end{pmatrix}}$

8. Express $\sqrt{17}$ in continued fraction form.

9. $[4;\overline{1,3,1,8}]$ is the square root of what value?

10. Find $23^{534} \pmod{29}$ using fast exponentiation (i.e., successive squaring).

11. Find $23^{534} \pmod{29}$ using Fermat's Little Theorem.

12. Find the value of $\varphi(75600)$.

13. Suppose you know the following:
$$2^{340} \equiv 1 \pmod{341} \quad \quad \textrm{and} \quad \quad 3^{340} \equiv 56 \pmod{341}$$
Can you immediately tell (without further calculation) if 341 is prime or composite? Explain how.

14. Find one solution for $x$ if
$$x \equiv 8 \pmod{23} \quad \quad \textrm{and} \quad \quad x \equiv 15 \pmod{17}$$

◆ ◆ ◆