91Ó°ÊÓ

The ISBN-10 of the sixth edition of Elementary Number Theory and Its Applications is \(0-321-500 \mathrm{Q} 1-8,\) where \(Q\) is a digit. Find the value of \(Q .\)

Convert \((7345321)_{8}\) to its binary expansion and \((1010111011)_{2}\) to its octal expansion.

Give a procedure for converting from the hexadecimal expansion of an integer to its octal expansion using binary notation as an intermediate step.

The Vigenère cipher is a block cipher, with a key that is a string of letters with numerical equivalents \(k_{1} k_{2} \ldots k_{m},\) where \(k_{i} \in \mathbf{Z}_{26}\) for \(i=1,2, \ldots, m .\) Suppose that the numerical equivalents of the letters of a plaintext block are \(p_{1} p_{2} \ldots p_{m} .\) The corresponding numerical ciphertext block is \(\left(p_{1}+k_{1}\right)\) mod 26 \(\left(p_{2}+k_{2}\right) \bmod 26 \ldots\left(p_{m}+k_{m}\right)\) mod \(26 .\) Finally, we translate back to letters. For example, suppose that the key string is RED, with numerical equivalents \(1743 .\) Then, the plaintext ORANGE, with numerical equivalents \(141700130604,\) is encrypted by first splitting it into two blocks 141700 and 13 \(0604 .\) Then, in each block we shift the first letter by 17 , the second by \(4,\) and the third by \(3 .\) We obtain 52103 and 0410 \(07 .\) The cipherext is FVDEKH. Use the Vigenère cipher with key BLUE to encrypt the message SNOWFALL.

Determine whether each of these integers is prime, verifying some of Mersenne's claims. $$\begin{array}{ll}{\text { a) } 2^{7}-1} & {\text { b) } 2^{9}-1} \\ {\text { c) } 2^{11}-1} & {\text { d) } 2^{13}-1}\end{array}$$

Use the construction in the proof of the Chinese remainder theorem to find all solutions to the system of congruences \(x \equiv 2(\bmod 3), x \equiv 1(\bmod 4),\) and \(x \equiv 3(\bmod 5)\)

The Vigenère cipher is a block cipher, with a key that is a string of letters with numerical equivalents \(k_{1} k_{2} \ldots k_{m},\) where \(k_{i} \in \mathbf{Z}_{26}\) for \(i=1,2, \ldots, m .\) Suppose that the numerical equivalents of the letters of a plaintext block are \(p_{1} p_{2} \ldots p_{m} .\) The corresponding numerical ciphertext block is \(\left(p_{1}+k_{1}\right)\) mod 26 \(\left(p_{2}+k_{2}\right) \bmod 26 \ldots\left(p_{m}+k_{m}\right)\) mod \(26 .\) Finally, we translate back to letters. For example, suppose that the key string is RED, with numerical equivalents \(1743 .\) Then, the plaintext ORANGE, with numerical equivalents \(141700130604,\) is encrypted by first splitting it into two blocks 141700 and 13 \(0604 .\) Then, in each block we shift the first letter by 17 , the second by \(4,\) and the third by \(3 .\) We obtain 52103 and 0410 \(07 .\) The cipherext is FVDEKH. Express the Vigenère cipher as a cryptosystem.

Use the construction in the proof of the Chinese remainder theorem to find all solutions to the system of congruences \(x \equiv 1(\bmod 2), x \equiv 2(\bmod 3), x \equiv 3(\bmod 5),\) and \(x \equiv 4(\bmod 11)\)

Find these values of the Euler \(\phi\) -function. $$\begin{array}{lll}{\text { a) } \phi(4)} & {\text { b) } \phi(10)} & {\text { c) } \phi(13)}\end{array}$$

Solve the system of congruence \(x \equiv 3(\bmod 6)\) and \(x \equiv 4(\bmod 7)\) using the method of back substitution.