## Exercises5.8Exercises Set 11

###### 1.

Finish all investigations from in-class activities.

###### 2.

We can use Fermat's Little Theorem to simplify exponents in the following way. Since $x^{16} \equiv 1 \pmod {17}$ we can simplify $x^{20} = x^{16}x^{4} \equiv 1*x^4 = x^ 4 \pmod{17} \text{.}$ Use Fermat's Little Theorem to reduce the following congruences. Explicitly show how you are using the theorem the simplify the exponent. All of the mods are prime numbers.

1. $\displaystyle 2^{23} \bmod 23$

2. $\displaystyle 2^{92} \bmod 23$

3. $\displaystyle 19^{500} \bmod 101$

4. $\displaystyle 3^{204} \bmod 101$

5. $\displaystyle 99^{323} \bmod 107$

###### 3.

Use Fermat's Little Theorem to find a multiplicative inverse of $a \bmod p\text{.}$

###### 4.

Recall Euler's theorem says that $x^{\phi(n)} \equiv 1 \pmod{n}\text{.}$ We can use Euler's Theorem to simplify exponents in the same way as you used Fermat's Little Theorem. Since $x^{10} \equiv 1 \pmod {22}$ we can simplify $x^{22} = x^{10}*x^{10}x^{2} \equiv 1*1*x^2 = x^ 2 \pmod{22} \text{.}$ Use Euler's Theorem to reduce the following congruences. Explicitly show how you are using the theorem the simplify the exponent. All of the mods are $p*q$ for two distinct primes $p$ and $q\text{.}$

1. $\displaystyle 2^{27} \bmod 21$

2. $\displaystyle 2^{81} \bmod 55$

3. $\displaystyle 10^{148} \bmod 39$

4. $\displaystyle 3^{200} \bmod 85$

5. $\displaystyle 9^{106} \bmod 106$

###### 5.

Alice has published the modulus 22897 and exponent 7, so her encryption formula is $CT=x^7 \pmod{22897}\text{.}$ Use a three letter base twenty-six encoding and RSA to encipher the following messages to her. Convert them to three or four letters using base 26 for your final answer.

1. LIE

3. SUN

###### 6.

For an RSA encryption scheme you have chosen an encryption formula of $E(x) = x^{113} \bmod 17741\text{.}$ Find your decryption formula. Then use it to decrypt the following messages. Last, use a base 26 conversion for the plaintext.

1. 13667

2. 4202

###### 7.

For an RSA encryption scheme you have chosen an encryption formula of $E(x) = x^{5093} \bmod 17617\text{.}$ Find your decryption formula. Then use it to decrypt the following messages. Assume that each block of five decimal digits represents a block of three letters. Decrypt each block separately. $14438 \qquad 4108 \qquad 511 \qquad 3560 \qquad 16470 \qquad 1247$

###### 8.

For an RSA encryption scheme you have chosen an encryption formula of $E(x) = x^{293221} \bmod 2885500349\text{.}$ Find your decryption formula. Then use it to decrypt the following messages using blocks of five letters. Decrypt each block separately.

\begin{equation*} 692482488 \; \; 411080826 \end{equation*}
###### 9.

Use Induction to prove that $1^2+2^2+3^2 + \cdots +n^2 = \frac{n(2n+1)(n+1)}{6}$ for all $n \geq 1\text{.}$

###### 10.

Use induction to prove the finite geometric series formula (given below) from Calculus is true for any integer $n \ge 0\text{.}$

\begin{equation*} a+ ar + ar^2 + \cdots + ar^{n}=\frac{ar^{n+1}-a}{r-1} \end{equation*}

(You've probably proved this before (in Calculus) without induction, but you must use induction here.) Remember $a$ and $r$ are any real numbers, so they are not necessarily integers. Your induction should be with respect to $n\text{.}$

###### 11.

Suppose $n=p^2t$ for a prime $p$ and an integer $t \ge 1\text{.}$

1. Prove that if $x=pt$ then $x^a \equiv 0 \pmod{n}$ for any integer $a \ge 2\text{.}$
2. Prove that if $x=pt$ then $x \not\equiv 0 \pmod{n}\text{.}$
3. Explain what this tells you about which $n$ will not have an $a \ge 2$ such that $x^a \equiv x \pmod{n}$ for all $x\text{.}$
###### 12.

Let $p,q$ be distinct primes. Use Theorem 5.5.8 to prove that if $p$ is a prime and $a=1+\phi(pq)k$ for an integer $k$ then $x^a \equiv x \pmod{p}$ for all $x\text{.}$ There should be two cases for $x\text{.}$ Case 1: $\gcd(x,p)=1\text{.}$ Case 2: $\gcd(x,p) \neq 1\text{.}$

Hint

Use the formula for $\phi(pq)\text{.}$

###### 13.

Use a definition of modular arithmetic to prove that if $p$ and $q$ are distinct primes, $x \equiv a \pmod{p}$ and $x \equiv a \pmod{q}$ then $x \equiv a \pmod{pq}$

###### 14.

Let $p,q$ be distinct primes. Use the two previous problems to show that if $p$ is a prime and $a=1+\phi(pq)k$ for an integer $k$ then $x^a \equiv x \pmod{pq}$ for all $x\text{.}$ Note, you already proved this mod $p\text{,}$ you need to extend it to mod $pq\text{.}$

###### 15.

Explain why RSA works in general. That is, explain why $D(E(x)) \equiv x \bmod n\text{.}$ Does the order matter? Is it also true that $E(D(x)) \equiv x \bmod n\text{?}$ Explain why or why not.

###### 16.

Consider the following recursive algorithm for any integer $M\text{.}$

\begin{align*} C_0\amp=1 \\ C_1\amp=(C_0)^2 M \\ C_2\amp=(C_1)^2 M \\ \amp \;\; \vdots \\ C_k\amp=(C_{k-1})^2 M \end{align*}
1. Compute $C_3, C_4, C_5, C_6$ as powers of $M\text{.}$ For example, $C_2=M^3\text{.}$
2. Find a formula for $j$ in terms of $k$ where $C_k=M^j\text{.}$ (Use your above examples to identify the pattern.) Hint
Examining powers of 2 maybe be helpful.
3. Prove your formula $C_k=M^j$ by induction.
4. What's the connection to binary?