Chapter 4: Number Theory and Cryptography

Adapt the proof in the text that there are infinitely many primes to prove that there are infinitely many primes of the form \(4k + 3\), where k is a non negative integer. (Hint: Suppose that there are only finitely many such primes \({q_1),{q_2),...,{q_n)\), and consider the number \(4{q_1){q_2)...,{q_n) - 1\)).

Devise an algorithm that, given the binary expansions of the integers a and b, determines whether a>b, a=b, or a<b.

Find the discrete logarithms of 5 and 6 to the base 2 modulo 19.

Let p be an odd prime and r a primitive root of p. Show that if a and b are positive integers in Zp,the${\log }_r\left(ab\right)\equiv {\log }_r\left(a\right)+{\log }_{r}b(modp-1)$

Prove that the set of positive rational numbers is countable by setting up a function that assigns to a ration number\({\raise0.7ex\hbox{\(p\)} \!\mathord{\left/

{\vphantom {p q}}\right.\kern-\nulldelimiterspace}

\!\lower0.7ex\hbox{\(q\)}}\)with\(\gcd (p,q) = 1\) the base\(11\) number formed by the decimal representation of p followed by the base\(11\)digit A, which corresponds to the decimal number\(10\) followed by the decimal representation of q.

How many bit operations does the comparison algorithm from Exercise 55 use when the larger of a and b has n bits its binary expansion.

Estimate the complexity of algorithm 1 for finding the base b expansion of an integer n in terms of the number of divisions used.

Prove that the set of positive rational numbers is countable by showing that the function K is a one-to-one correspondence between the set of positive rational numbers and the set of positive integers if\(K({\raise0.7ex\hbox{\(m\)} \!\mathord{\left/

{\vphantom {m n}}\right.\kern-\nulldelimiterspace}

\!\lower0.7ex\hbox{\(n\)}}) = p_1^{2{a_1}}p_2^{2{a_2}}.....p_s^{2{a_s}}q_1^{2{b_1} - 1}q_2^{2{b_2} - 1}.....q_t^{2{b_t} - 1}\)where\(\gcd (m,n) = 1\)and the prime-power factorizations of m and n are\(m = p_1^{{a_1}}p_2^{{a_2}}.....p_s^{{a_s}}{\rm{ and n = }}q_1^{{b_1}}q_2^{{b_2}}.....q_t^{{b_t}}\).

Write out a table of discrete logarithms modulo 17 with respect to the primitive root 3.

Which integers are quadratic residues of 11?s