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$.  

◆ ◆ ◆