Chapter 4: Number Theory and Cryptography

Show that the integer m with two's complement representation $\left(a_{n-1}{a}_{n-2},\dots \dots ,a_1{a}_0\right)$can be found using the equation

$m=-a_{n-1}{2}^{n-1}+-a_{n-2}^{\mathrm{\prime }}{2}^{n-2}+\dots \dots +a_1^{\mathrm{\prime }}2+a_0$

Describe the extended Euclidean algorithm using pseudocode.

Show that 2047 is a strong pseudoprime to the base 2 by showing that is passes Miller’s test to the base 2, but is composite.

Write out the addition and multiplication tables for \({{\rm{Z}}_5}\) (where by addition and multiplication we mean \({ + _5}{\rm{ and }}{ \cdot _5}\)).

Show that if ${\mathbf{d}}_{\mathbf{1}}{\mathbf{d}}_{\mathbf{2}}\mathbf{\dots }{\mathbf{d}}_{\mathbf{9}}$is a valid RTN, then ${\mathit{d}}_{\mathbf{9}}\mathbf{=}\mathbf{7}\left(d_1+d_4+d_7\right)\mathbf{+}\mathbf{3}\left(d_2+d_5+d_8\right)\mathbf{+}\mathbf{9}\left(d_3+d_6\right)$mod 10Furthermore, use this formula to find the check digit that follows the eight digits 11100002 in a valid RTN.

Find the smallest positive integer with exactly n different positive factors when n is

Show that 1729 is a Carmichael number.

Write out the addition and multiplication tables for \[{{\rm{Z}}_6}\] (where by addition and multiplication we mean \[{ + _6}{\rm{ and }}{ \cdot _6}\]).

Show that the check digit of an RTN can detect all single errors and determine which transposition errors an RTN check digit can catch and which ones it cannot catch.

Determine whether each of the functions

\(f(a) = a{\rm{ div d and g(a) = a mod d}}\), where d is a fixed positive integer, from the set of integers to the set of integers, is one-to-one, and determine whether each of these functions is onto.