Math 4/5/7380: Answers to exam 2

25 October 2013

Definitions, theorems, history

Provide short, precise answers to the following. Use complete sentences!
1. State the Prime Number Theorem. How is it related to the Riemann
Hypothesis? Has the latter been proved?
The Prime Number Theorem says that if π(n) denotes the number of
primes less than n then
Z n
n dx
π(n) ∼ ∼ Li(n) = .
log n 2 log x

This was first proved by de la Vallée Poussin and Hadamard in the

late nineteenth century, based on Riemann’s ideas. Riemann showed
that the Prime Number Theorem would be a corollary of a certain
statement about the zeroes of a particular complex function ζ(s). This
statement is now known as the Riemann Hypothesis. Although the
Riemann Hypothesis has still not been proved nor disproved enough of
what Riemann sketched about the properties of ζ(s) was proved that
de la Vallée Poussin and Hadamard could complete the proof of the
Prime Number Theorem.
2. Who are Alice and Bob? What are Alice’s goals? What do coding
theorists think of her? Which types of coding does Alice use to achieve
each of her goals?
Alice and Bob are fictional characters used to illustrate problems, pro-
tocols, and other issues in coding theory. Alice is often supposed to be
engaged in rather dramatic pursuits — in the famous words of John
Gordon:

1
 Over a noisy telephone line, tapped by the tax authorities and the
secret police, Alice happily attempts, with someone she doesn’t
trust, whom she cannot hear clearly, and who is probably someone
else, to fiddle her tax returns and to organize a coup d’état, while
at the same time minimizing the cost of the phone call.

Gordon goes on to define a coding theorist as someone who doesn’t

think that Alice is crazy. This is because Alice can use source coding
to improve clarity on the telephone line; cryptography to evade the
police; and source coding to compress the data and thereby save on her
telephone bills.

3. When was frequency analysis invented? In what context did it arise?

How is it used by cryptanalysts?
Frequency analysis was invented by Arab scholars in the early Islamic
Empire (7th and 8th centuries) in order to establish the chronology
of the suras in the Quran and the accuracy of putative Hadith. They
later applied the technique to encrypted messages, thereby inventing
cryptanalysis. It is particularly effective in attacking monoalphabetic
substitution ciphers. These are vulnerable because the most frequent
letters or symbols in the ciphertext most likely correspond to the most
frequent letters in the language of the plaintext. It can also be used to
attack some polyalphabetic substitution ciphers, including the Viginère
cipher.

4. Who was Kerckhoffs? What is Kerckhoffs’ Principle? What does it

imply about the choice of key?
Auguste Kerckhoffs was a nineteenth Dutch linguist who lived and
worked in France. He is known primarily for his work in cryptology.
His principle states that the security of a cryptosystem depends on
keeping secret the key but not on the secrecy of the algorithm. Hence
ideally the key should be chosen randomly from a large “keyspace” —
the set of all possible keys, all with equal likelihood.

2
 5. What is the Key Exchange Problem? Who solved it? What “revolu-
tionary idea” followed from this solution?
The Key Exchange Problem is the problem of securely exchanging the
keys used in a cryptosystem. After World War II the rising use of
cryptography (especially computerized cryptography) made the cost of
secure transportation of keys one of the most expensive costs of interna-
tional business and diplomacy. Diffie, Hellman, and Merkle found a way
to carry out secure key exchange over insecure telecommunication lines.
In effect they found a way to agree on a piece of secret information using
a completely public conversation. (It should be noted that this same
thing was discovered by members of Britain’s GCHQ, but since their
discovery was never shared, nor even employed by British intelligence,
it can hardly be said that they “solved” the problem.) Diffie realized
that a similar idea could lead to an asymmetric cipher — that is, one
where the encryption scheme, including its key, is completely public,
but the ability to decrypt is available only to the intended recipient.

Python
6. What does the following compute?

def spam(n):
"""if n is a positive integer then spam(n)
is the list of primes less than n"""
L = range(n)
# recall that range(n) yields the list
# of positive integers less than n.
P = []
k = 2
while k < n:
if L[k] is not ’X’:
P.append(k)
j = k*k
while j < n:
L[j] = ’X’
j = j + k
k = k + 1

3
 return P

Work through an example by hand, showing how each variable changes

as the code executes.
This is simply an implementation of the Sieve of Eratosthenes, which
produces the list of primes less than n. Let’s compute spam(10):

k j P L
----------------------------------------------------------
[0,1,2,3,4,5,6,7,8,9]
[]
2
[2]
4 [0,1,2,3,X,5,6,7,8,9]
6 [0,1,2,3,X,5,X,7,8,9]
8 [0,1,2,3,X,5,X,7,X,9]
10
3 [2,3]
9 [0,1,2,3,X,5,X,7,X,X]
12
4
5 [2,3,5]
25
6
7 [2,3,5,7]
49
8
9

7. Write a python function to compute Euler’s totient φ(n). You may

employ a function for the gcd, but include that code in your answer.
What would you expect for the asymptotics of the running time of your
function, assuming that elementary bit operations execute in constant
time?
φ(n) is the number of k in the range [1, n] that are relatively prime to
n. Hence we can compute gcd(k, n) for all k in this range and count
those which yield 1.

4
 def gcd(a,b):
"computation of the gcd using anthyphairesis"
while b > 0:
a, b = b, a%b
return a

def phi(n):
"""naive computation of euler’s totient
by counting {k in [1,n] | gcd(k,n) = 1}"""
k = 1
c = 1
while k < n:
if gcd(k,n) == 1:
c = c + 1
return c

This is a horribly inefficient algorithm. In fact there is no efficient algo-

rithm known for φ(n). The computation of each gcd takes O((log k)2 )
bit operations, but there are n = exp(log n) steps! Thus the running
time is exponential in the number of bits.

8. Write python code that returns the smallest p that is “probably prime”
and greater than a given n. More precisely, given n and k search for
values of p > n that satisfy the conclusion of Fermat’s Theorem (see
problem 9) for k randomly chosen values of a. About how many p do
you expect to have to test before you find one that is probably prime,
in this sense?
Near n approximately 1/ log n of the numbers are prime. Therefore we
might expect to find one that close to n. That is not guaranteed, of
course, but the probability of not finding something which passes our
test in the first x (odd) integers past n decreases exponentially in x.

from random import randint

def fermat_test(n,k):
"""smallest p > n which satisfies the fermat test
for k randomly chosen bases"""

5
 # we need only consider odd p
if n%2 == 1:
p = n + 2
else:
p = n + 1
while True:
j = 0
while j < k:
a = randint(1,p-1)
if pow(a,p-1,p) != 1:
break
j = j + 1
if j == k:
return p
else:
p = p + 2

Proofs
9. Prove Fermat’s Theorem: If p is a prime and a is an integer such that
p6 | a then ap−1 ≡ 1 mod p.
The statement ap−1 ≡ 1 mod p means simply that p | ap−1 − 1. If p is
prime and p6 | a then p | ap−1 − 1 if an only if p | a(ap−1 − 1) = ap − a.
The latter divisibility statement is true even when p | a. Hence an
equivalent statement of Fermat’s Theorem is that p | ap − a for all
integers a. The advantage of this statement is that we can prove it by
induction on a.
First of all (−a)p − (−a) = a(ap − a), so we may assume that a ≥ 0.
Now the base case is when a = 0. Since 0p − 0 = 0 = p · 0 we have
established the base case in our induction. Now suppose that p | ap − a.
Consider (a + 1)p − (a + 1). The Binomial Theorem tells us that
p−1  
p p
X p
(a + 1) = a + 1 + aj .
j=1
j

6
 When 1 < j < p the formula
 
p p · (p − 1) · · · (p − j + 1)
=
j j · (j − 1) · · · 2 · 1

tells us that since the numerator is divisible by p by none of the fac-

tors in the denominator are divisible by p the integer obtained after
canceling all common factors has a factor of p. Thus,

(a + 1)p ≡ ap + 1 ≡ a + 1 mod p,

by the inductive hypothesis. This concludes the proof.

10. Suppose that n is a positive integer. What is

X
k=?
1≤k≤n
gcd(k,n)=1

Prove your claim.

The sum equals n · φ(n)/2. Note that φ(n) can be odd (when?) so we
must take care with our proof. Now gcd(k, n) = gcd(n − k, n), hence
we can employ Gauss’ trick:
X X
2 k= (k + n − k) = n · φ(n).
1≤k≤n 1≤k≤n
gcd(k,n)=1 gcd(k,n)=1

In fact the only time φ(n) is odd is when n = 2 (why?) and so we could
avoid Gauss’ trick by handling this case separately. But it is more fun
(and easier!) simply to stand on Gauss’ shoulders.

11. Show that the usual “grade school” algorithm for place-value addition
requires O(max(log m, log n)) bit operations to add m and n. Give a
big-O estimate for the number of bit operations to compute m · n and
m ÷ n. Justify your answers.
The “grade school” algorithm for adding two numbers expressed in
binary consists of a first writing the numerals one above the other in
such a way that the k-th bits line up in a column; then, starting on
the right, adding down the column, carrying a bit when necessary,

7
and adding the carried bit from the previous column if present. This
is a maximum number of 3 bit operations per column, and there are
1 + max(log2 m, log2 n) columns. Hence the estimate above.
Now consider the “grade school” algorithm for multiplication. We be-
ginning by lining up the numerals, as before; then, again beginning
on the right, we copy the top numeral and shift it to the let k places
each time the k-th bit of the second numeral equals 1. (This cor-
responds to expressing the second number as a sum of certain pow-
ers 2k and observing that multiplying the first number by 2k simply
shifts the bits k places.) We then start at the top make a running
total of these shifted numerals. There are at most log2 n additions of
1+log2 (mn) = 1+log2 m+log2 n bits, and hence O(max(log m, log n)2 )
bit operations altogether.
Finally, consider how we might divide. Division with remainder is
simply repeated subtraction. The subtraction algorithm is similar to
the addition algorithm, and requires O(max(log m, log n)) bit opera-
tions. In more detail, each step in the division algorithm involves
shifting the divisor a certain number of bits (that is, multiplying by
a power of 2) then subtracting from the dividend so that the result
decreases the number of bits. The quotient is the sum of those factors
of 2k and the remainder is the last difference. Thus there are at most
1 + log2 n subtractions each requiring O(log m) bit operations, for a
total of O(max(log m, log n)) bit operations altogether.