Chapter 4: Number Theory and Cryptography

Find the sum and product of each of these pairs of numbers. Express your answers as a base 3 expansion.

a) $(112{)}_3,(210{)}_3$

b) $(2112{)}_3,(12021{)}_3$

c) $(20001{)}_3,(1111{)}_3$

d) $(120021{)}_3,(2002{)}_3$

Solve the system of congruence$\mathbf{x}\mathbf{\equiv }\mathbf{3}\left(\mathrm{mod}6\right)$and $\mathbf{x}\mathbf{\equiv }\mathbf{4}\mathbf{(}\mathbf{mod}\mathbf{}\mathbf{7}\mathbf{)}$using the method of back substitution.

Show that n is prime if and only if$\mathit{\varphi }\left(n\right)\mathbf{=}\mathit{n}\mathbf{‐}\mathbf{1}$ .

Determine which single digit errors are detected by the USPS money order code.

To break a Vigenere cipher by recovering a plain text message from the cipher text message without having the key, the step is to figure out the length of the key string. The second step is to figure out each character of the key string by determining the corresponding shift. Exercise 21 and 22 deal with these two aspects.

22.Once the length of the key string of a vigenere cipher is known, explain how to determine each of its characters. Assume that the plain text is long enough so that the frequency of its letters is reasonably close to the frequency of letters in typical English text.

Find a div m and a mod m when

a) \({\bf{a}} = - {\bf{111}},{\rm{ }}{\bf{m}} = {\bf{99}}\)

b) \({\bf{a}} = - 9999,{\rm{ }}{\bf{m}} = 101\)

c) \({\bf{a}} = 10299,{\rm{ }}{\bf{m}} = 999\)

d)\({\bf{a}} = {\bf{1}}23456,{\rm{ }}{\bf{m}} = 1001\)

Find an arithmetic progression of length six beginning

with 7 that contains only primes.

show that we can easily factor when we know that n is the product of two primes, p and q, and we know the value of $\mathbf{(}\mathbf{p}\mathbf{‐}\mathbf{1}\mathbf{)}\mathbf{(}\mathbf{q}\mathbf{‐}\mathbf{1}\mathbf{)}$

Determine which transposition errors are detected by the USPS money order code.

Find \(a{\rm{ div}}\;m\) and \(a{\rm{ mod}}\;\;m\)when

\(\begin{array}{*{20}{l}}{{\bf{a}}){\rm{ }}{\bf{a}} = {\bf{228}},{\rm{ }}{\bf{m}} = {\bf{119}}.}\\{{\bf{b}}){\rm{ }}{\bf{a}} = {\bf{9009}},{\rm{ }}{\bf{m}} = {\bf{223}}.}\\{{\bf{c}}){\rm{ }}{\bf{a}} = - {\bf{10101}},{\rm{ }}{\bf{m}} = {\bf{333}}.}\\{{\bf{d}}){\rm{ }}{\bf{a}} = - {\bf{765432}},{\rm{ }}{\bf{m}} = {\bf{38271}}.}\end{array}\)