Chapter 4: Number Theory and Cryptography

One digit in each of these identification numbers of a postal money order is smudged. Can you recover the smudged digit, indicated by a Q, in each of these numbers?

a) Q 1223139784

b) 6702120 Q 988

c) 27 Q 41007734

d) 213279032 Q 1

Describe how two parties can share a secret key using the Diffie-Hellman key exchange protocol.

Find the five smallest consecutive composite integers.

One digit in each of these identification numbers of a postal money order is smudged. Can you recover the smudged digit, indicated by a Q, in each of these numbers?

a) 493212 Q 0688

b) 850 Q 9103858

c) 2 Q 941007734

d) 66687 Q 03201

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

a)\[{(1000111)_2},{(1110111)_2}\]

b)\[{(11101111)_2},{(10111101)_2}\]

c)\[{(1010101010)_2},{(111110000)_2}\]

d) \[{(1000000001)_2},{(1111111111)_2}\]

The value of the Euler $\mathit{\varphi }$-function at the positive integer is defined to be the number of positive integers less than or equal to that are relatively prime to. [Note:$\mathit{\varphi }$ is the Greek letter phi.]

Find these values of the Euler $\mathit{\varphi }$-function.

a)role="math" localid="1668504243797" $\mathit{\varphi }\left(4\right)$ b)role="math" localid="1668504251452" $\mathit{\varphi }\left(10\right)$ c)role="math" localid="1668504258881" $\mathit{\varphi }\left(13\right)$

Use the construction in the proof of the Chinese Remainder Theorem to find the solution of the system of congruences$\mathit{x}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{mod}\mathbf{2}\mathbf{)}\mathbf{,}\mathit{x}\mathbf{\equiv }\mathbf{2}\mathbf{(}\mathbf{mod}\mathbf{3}\mathbf{)}\mathbf{,}\mathit{x}\mathbf{\equiv }\mathbf{3}\mathbf{(}\mathbf{mod}\mathbf{5}\mathbf{)}\mathbf{,}\mathbf{}\mathbf{and}\mathbf{}\mathit{x}\mathbf{\equiv }\mathbf{4}\mathbf{(}\mathbf{mod}\mathbf{11}\mathbf{)}$

Evaluate these quantities.

a) 13 mod 3

b)−97 mod 11

c) 155 mod 19

d)−221 mod 23

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.

21. Suppose that when a long string of text is encrypted using a Vigenere cipher, the same string is found in the cipher text starting at several different positions. Explain how this information ca be used to help determine the length of the key.

Show that Goldbach’s conjecture, which states that every even integer greater than 2 is the sum of two primes, is equivalent to the statement that every integer greater than 5 is the sum of three primes.