# Review Exercises (Set C)

1. Suppose a message is RSA-encrypted with modulus $N=323$ and encrypting key $e=49$. Find the decrypting key $d$.

2. Find an integer $x$ that satisfies the congruence below.
$$x^{169} \equiv 119 \pmod{1452}$$

3. Consider the function $f: \mathbb{Z} \rightarrow 2\mathbb{Z}$ defined by $f(x) = 2x^2 - 4$. Is $f(x)$ injective? Is it surjective? Justify your claims.

4. Find or describe a bijection between the points in the open interval $(0,1)$ and the points in $(-\infty,\infty)$.

5. Prove that the cardinality of the power set of a given set is never equal to the cardinality of the set itself.

6. Find $\text{ord}_{19} 8$.

7. Suppose $\text{ord}_n b = 3$. How many positive integer solutions does $b^x \equiv 1 \pmod{n}$ have for $x$ that are less than $26$?

8. Suppose that $r$ is a primitive root for $n$, prove the following:

• $\text{ind}_r (xy) \equiv \text{ind}_r x + \text{ind}_r y \pmod{\varphi(n)}$
• $\text{ind}_r b^k \equiv k \cdot \text{ind}_r b \pmod{\varphi(n)}$     (presuming $k \in \mathbb{Z}^+$)
• $\textrm{ind}_r 1 \equiv 0 \pmod{\varphi(n)}$

[see the notes on index arithmetic]

9. Alice and Bob agree to create a secret encryption key for future correspondence according to the Diffie-Hellman Key Exchange Protocol. Over a public communications channel, they agree upon a prime base of $5$ and a modulus of $23$. Alice then sends Bob the value $8$, and Bob sends Alice the value $19$. What is their agreed upon secret encryption key? What could they have done to better protect the secret key they generated? (Hint: You may wish to refer to the table of powers and indexes $\pmod{23}$ provided in the next question.)

10. Use the table of powers and indexes provided below and index arithmetic to solve the following congruences:

1. $3x^{14} \equiv 2 \pmod{23}$
2. $13^x \equiv 6 \pmod{23}$

Some powers and related indexes $\pmod{23}$

$$\begin{array}{rclcrcl|rclrcl} 5^1 &\equiv& 5 && 5^{12} &\equiv& 18 & \text{ind}_5 1 &=& 22 & \text{ind}_5 12 &=&20\\ 5^2 &\equiv& 2 && 5^{13} &\equiv& 21 & \text{ind}_5 2 &=& 2 & \text{ind}_5 13 &=&14\\ 5^3 &\equiv& 10 && 5^{14} &\equiv& 13 & \text{ind}_5 3 &=& 16 & \text{ind}_5 14 &=&21\\ 5^4 &\equiv& 4 && 5^{15} &\equiv& 19 & \text{ind}_5 4 &=& 4 & \text{ind}_5 15 &=&17\\ 5^5 &\equiv& 20 && 5^{16} &\equiv& 3 & \text{ind}_5 5 &=& 1 & \text{ind}_5 16 &=&8\\ 5^6 &\equiv& 8 && 5^{17} &\equiv& 15 & \text{ind}_5 6 &=& 18 & \text{ind}_5 17 &=&7\\ 5^7 &\equiv& 17 && 5^{18} &\equiv& 6 & \text{ind}_5 7 &=& 19 & \text{ind}_5 18 &=&12\\ 5^8 &\equiv& 16 && 5^{19} &\equiv& 7 & \text{ind}_5 8 &=& 6 & \text{ind}_5 19 &=&15\\ 5^9 &\equiv& 11 && 5^{20} &\equiv& 12 & \text{ind}_5 9 &=& 10 & \text{ind}_5 20 &=&5\\ 5^{10} &\equiv& 9 && 5^{21} &\equiv& 14 & \text{ind}_5 10 &=& 3 & \text{ind}_5 21 &=&13\\ 5^{11} &\equiv& 22 && 5^{22} &\equiv& 1 & \text{ind}_5 11 &=& 9 & \text{ind}_5 22 &=&11\\ \end{array}$$
11. In a plane, given two points $F_1$ and $F_2$, a hyperbola is defined as the set of all points $P$ where the positive difference between the distance from $P$ to $F_1$ and the distance from $P$ to $F_2$ is constant. Suppose $F_1 = (-2,0)$, $F_2 = (2,0)$, the aforementioned constant positive difference is 3, and distances are found with the taxicab metric. Draw the corresponding "hyperbola".

12. The inhabitants of planet Quatro wish to beam a message to Earth. The alphabet used on Quatro has four letters: A, B, C, and D, which the people of Quatro have encoded as $00000$, $10110$, $01011$, and $11101$, respectively. What is the maximum number of single digit errors that this encoding scheme can correct in the transmission of any one letter?

13. Show that the powers of $\alpha = x$ generates the finite field with elements constructed using the irreducible polynomial $f(x) = x^3 + x^2 + 1$ from $\mathbb{Z}_2[x]$.

14. Construct a Zech's Log Table for the finite field generated by $\alpha = x$ and the irreducible polynomial $f(x) = x^4 + x + 1$ with coefficients taken from $\mathbb{Z}_2$. Now let $y$ be given by the following: $$y = x^{10} + \frac{x^7 + x^{23}}{x^4 + x^9} + 1$$ Use the table constructed to write $y$ as a power of $x$.

◆ ◆ ◆