Chapter 4: Number Theory and Cryptography

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{)}$

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

a) \({(763)_8},{(147)_8}\)

b) \({(6001)_8},{(272)_8}\)

c) \({(1111)_8},{(777)_8}\)

d) \({(54321)_8},{(3456)_8}\)

Prove that if f(x) is a non constant polynomial with integer co-efficients, then there is an integer such that is composite. [Hint: Assume that $\mathbf{f}\left(x_0\right)$is prime. Show that p$\mathbf{f}\mathbf{(}{\mathbf{x}}_{\mathbf{0}}\mathbf{+}{\mathbf{k}}_{\mathbf{p}}\mathbf{)}$divides for all integers . Obtain a contradiction of the fact that a polynomial of degree n , where n > 1 , takes on each value at most times.]

What are the greatest common divisors of these pairs of integers?

a)${\mathbf{2}}^{\mathbf{2}}\mathbf{·}{\mathbf{3}}^{\mathbf{3}}\mathbf{·}{\mathbf{5}}^{\mathbf{5}}\mathbf{,}\mathbf{}{\mathbf{2}}^{\mathbf{5}}\mathbf{·}{\mathbf{3}}^{\mathbf{3}}\mathbf{·}{\mathbf{5}}^{\mathbf{2}}$

b)$\mathbf{2}\mathbf{·}\mathbf{3}\mathbf{·}\mathbf{5}\mathbf{·}\mathbf{7}\mathbf{·}\mathbf{11}\mathbf{·}\mathbf{13}\mathbf{,}\mathbf{}{\mathbf{2}}^{\mathbf{11}}\mathbf{·}{\mathbf{3}}^{\mathbf{9}}\mathbf{·}\mathbf{11}\mathbf{·}{\mathbf{17}}^{\mathbf{14}}$

c) 17,${\mathbf{17}}^{\mathbf{17}}$

d)${\mathbf{2}}^{\mathbf{2}}\mathbf{·}\mathbf{7}\mathbf{,}\mathbf{}{\mathbf{5}}^{\mathbf{3}}\mathbf{·}\mathbf{13}$

e) 0, 5

f)$\mathbf{2}\mathbf{·}\mathbf{3}\mathbf{·}\mathbf{5}\mathbf{·}\mathbf{7}\mathbf{,}\mathbf{}\mathbf{2}\mathbf{·}\mathbf{3}\mathbf{·}\mathbf{5}\mathbf{·}\mathbf{7}$

In exercise 24-27 first express your answers without computing modular exponentiations. Then use a computational aid to complete these computations.

24. Encrypt the message$\mathbf{ATTACK}\mathbf{}$ using the system RSAwith $\mathbf{n}\mathbf{=}\mathbf{43}\mathbf{.59}\mathbf{}\mathbf{and}\mathbf{}\mathbf{e}\mathbf{=}\mathbf{13}$, translating each letter into integers and grouping together pairs of integers , as done in Example 8.

Find the sum and product of each of these pairs of num your answers as a hexadecimal expansion

1. \[{(1{\rm{AE}})_{16}},{({\rm{BBC}})_{16}}\]
2. \[{(20{\rm{CBA}})_{16}},{(\;{\rm{A}}01)_{16}}\]
3. \[{({\rm{ABCDE}})_{16}},{(1111)_{16}}\]
4. \[{({\rm{E}}0000{\rm{E}})_{16}},{({\rm{BAAA}})_{16}}\]

Find the integer a such that

a) \({\bf{a}} = {\bf{43}}\left( {{\bf{mod}}{\rm{ }}{\bf{23}}} \right)\) and \( - 22 \le a \le 0\).

b) \({\bf{a}} = {\bf{17}}\left( {{\bf{mod}}{\rm{ }}{\bf{29}}} \right)\) and \( - 14 \le a \le 14\).

c) \({\bf{a}} = - {\bf{11}}\;\left( {{\bf{mod}}{\rm{ }}{\bf{21}}} \right)\) and \(90 \le a \le 110\).

Solve the system of congruenceExercise 21 using the method of back substitution.

How many zeros are at the end of the binary expansion of ${\mathbf{100}}_{\mathbf{10}}$

Find the integer a such that

a) \({\bf{a}} = - {\bf{15}}\left( {{\bf{mod}}{\rm{ }}{\bf{27}}} \right)\) and\( - 26 \le a \le 0\).

b) \({\bf{a}} = {\bf{24}}\;\left( {{\bf{mod}}{\rm{ }}{\bf{31}}} \right)\) and \( - 15 \le a \le 15\).

c) \({\bf{a}} = {\bf{99}}\;\left( {{\bf{mod}}{\rm{ }}{\bf{41}}} \right)\) and \(100 \le a \le 140\).