Introduction to Cryptography with Coding Theory, 3rd Edition

3.13 Exercises

1. 1. Find integers $x$ and $y$ such that $17x+101y=1\text{.}$

   2. Find ${17}^{-1}(\text{mod}101)\text{.}$

2. 1. Using the identity $x^3+y^3=(x+y)(x^2-xy+y^3)\text{,}$ factor $2^{333}+1$ into a product of two integers greater than 1.

   2. Using the congruence $2^2\equiv 1(\text{mod}3)\text{,}$ deduce that $2^{232}\equiv 1(\text{mod}3)$ and show that $2^{333}+1$ is a multiple of 3.

3. 1. Solve $7d\equiv 1(\text{mod}30)\text{.}$

   2. Suppose you write a message as a number $m(\text{mod}31)\text{.}$ Encrypt $m$ as $m^7(\text{mod}31)\text{.}$ How would you decrypt? (Hint: Decryption is done by raising the ciphertext to a power mod 31. Fermat’s theorem will be useful.)

4. Solve $5x+2\equiv 3x-7(\text{mod}31)\text{.}$

5. 1. Find all solutions of $12x\equiv 28(\text{mod}236)\text{.}$

   2. Find all solutions of $12x\equiv 30(\text{mod}236)\text{.}$

6. 1. Find all solutions of $4x\equiv 20(\text{mod}50)\text{.}$

   2. Find all solutions of $4x\equiv 21(\text{mod}50)\text{.}$

7. 1. Let $n\ge 2\text{.}$ Show that if $n$ is composite ...