Chapter 4: Number Theory and Cryptography

Use Algorithm 5 to find$7^{644}mod645$

Encrypt the message UPLOAD using the RSA system with $n=53\cdot 61\mathrm{and}\mathrm{e}=17$, translating each letter into integers and grouping together pairs of integers, as done in Example 8.

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\).

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

1. ${\mathbf{3}}^{\mathbf{7}}\mathbf{\cdot }{\mathbf{5}}^{\mathbf{3}}\mathbf{\cdot }{\mathbf{7}}^{\mathbf{3}}\mathbf{,}{\mathbf{2}}^{\mathbf{11}}\mathbf{\cdot }{\mathbf{3}}^{\mathbf{5}}\mathbf{\cdot }{\mathbf{5}}^{\mathbf{9}}$
2. $\mathbf{11}\mathbf{\cdot }\mathbf{13}\mathbf{\cdot }\mathbf{17}\mathbf{,}{\mathbf{2}}^{\mathbf{9}}\mathbf{\cdot }{\mathbf{3}}^{\mathbf{7}}\mathbf{\cdot }{\mathbf{5}}^{\mathbf{5}}\mathbf{\cdot }{\mathbf{7}}^{\mathbf{3}}$
3. ${\mathbf{23}}^{\mathbf{31}}\mathbf{,}{\mathbf{23}}^{\mathbf{17}}$
4. $\mathbf{41}\mathbf{\cdot }\mathbf{43}\mathbf{\cdot }\mathbf{53}\mathbf{,}\mathbf{41}\mathbf{\cdot }\mathbf{43}\mathbf{\cdot }\mathbf{53}$
5. ${\mathbf{3}}^{\mathbf{13}}\mathbf{\cdot }{\mathbf{5}}^{\mathbf{17}}\mathbf{,}{\mathbf{2}}^{\mathbf{12}}\mathbf{\cdot }{\mathbf{7}}^{\mathbf{21}}$
6. $\mathbf{1111}\mathbf{,}\mathbf{0}$
   

Use the Euclidean algorithm to find the greatest common divisor of 10,223 and 33,341 .

Does the check digit of a UPC code detect all single errors? Prove your answer or find a counterexample.

Use Algorithm 5 to find ${11}^{644}mod645$

Find all solutions, if any, to the system of congruences $\mathbf{x}\mathbf{\equiv }\mathbf{5}\mathbf{(}\mathbf{mod}\mathbf{6}{\mathbf{)}}_{\mathbf{2}}\mathbf{x}\mathbf{\equiv }\mathbf{3}\mathbf{(}\mathbf{mod}\mathbf{10}\mathbf{)}$, and$\mathbf{x}\mathbf{\equiv }\mathbf{8}\mathbf{(}\mathbf{mod}\mathbf{15}\mathbf{)}$

List five integers that are congruent to 4 modulo 12.

What is the original message encrypted using the RSA system with $\mathrm{n}=53\cdot 61\mathrm{and}\mathrm{e}=17$if the encrypted message is $3185203824602550$? (To decrypt, first find the decryption exponent d, which is the inverse of $\mathrm{e}=17\mathrm{modulo}52\cdot 60$).