MATH3301/6114 ADD-ON MODULE (ASE/HPO/6114)
POST-QUANTUM CRYPTOGRAPHY ASSIGNMENT 1
DUE FRIDAY 22 SEPTEMBER AT 6PM
ANTHONY HENDERSON
There are 25 marks in total. Explain your reasoning in sufficient detail to
demonstrate your understanding, unless the question specifies otherwise.
(1) Let n > 1 be an integer. The motivation for this question is the
Random GCD factorization method described in Add-on Lecture 1
(Week 4), in which the probability of failure for each random choice
is φ(n)/(n− 1) where φ(n) is Euler’s totient function. But you can
answer it just using results about φ(n) from the main lectures, which
you can quote without proof.
(a) (2 marks) Compute φ(n)/(n − 1) for n = 1001, showing your
working. (You can use a calculator or computer to do the cal-
culations, if you need it.)
(b) (2 marks) Suppose n has prime factorization n = pe11 p
e2
2 · · · pekk ,
where p1 < p2 < · · · < pk. Show that
φ(n)
n− 1 >
(
1− 1
p1
)k
.
(c) (2 marks) Suppose that n = pq where p and q are different
primes. Show that
φ(n)
n− 1 < 1−
2√
n+ 1
.
(2) The motivation for this question is Shor’s algorithm as described at
the end of Add-on Lecture 2 (Week 5), but you can answer it just
using concepts and results from the main lectures, which you can
quote without proof. Specifically, you may want to use the Chinese
Remainder Theorem and (in (b)) the fact that primitive roots exist
modulo a prime.
(a) (2 marks) Find the multiplicative order of 37 mod 77, showing
your working. (You can use a calculator or computer to do the
calculations, if you need it. As a check: the answer is odd.)
(b) (3 marks) Suppose n = pq where p and q are distinct odd prime
numbers. Show that, out of the φ(n) different integers c satis-
fying 1 < c < n and gcd(c, n) = 1, at most φ(n)/4 of them have
the property that the multiplicative order of c mod n is odd.
MORE QUESTIONS OVER THE PAGE.
2 ANTHONY HENDERSON
(3) Suppose that we have an odd number n > 1 which we know is
composite and not a perfect square. One way to find a nontrivial
divisor of n is Fermat’s factorization method:
• Calculate b√nc, the largest integer less than or equal to √n.
• Letting a run over b√nc+ 1, b√nc+ 2, b√nc+ 3, · · · in turn:
• Calculate √a2 − n and see whether it is an integer;
• Once we have √a2 − n = b for some integer b, we know that
n = a2 − b2 = (a− b)(a+ b), so we finish.
The following questions refer to this version of Fermat’s method.
(a) (2 marks) Find a nontrivial divisor of 310351 using Fermat’s
method, showing your working. (You can use a calculator or
computer to do the calculations.)
(b) (2 marks) Let g(n) denote the largest divisor of n which is less
than
√
n, and let h(n) = n/g(n). Show that when applying
Fermat’s method to n, we will try exactly
1
2(g(n) + h(n))− b
√
nc
values of a before finishing.
(c) (3 marks) In assessing the time taken by Fermat’s method, it
is natural to compare it against “reverse trial division”, where
instead of testing divisibility of n by 2, 3, 4, · · · , we test divisi-
bility of n by b√nc, b√nc − 1, b√nc − 2, · · · . Using the result
of (b), explain why there are some values of n for which Fer-
mat’s method would find a nontrivial divisor more quickly than
reverse trial division. (You do not have to be very precise about
the time taken to compute square roots or divisions, but you
will lose marks for assumptions which are obviously absurd.)
(4) Again let n > 1 be a number which we wish to factorize. Suppose we
try to change the implementation of Pollard’s Rho method in Add-on
Lecture 2 (Week 5) to use the polynomial f(x) = x2 instead. That is,
we define our sequence a1, a2, · · · by choosing a1 ∈ {0, 1, · · · , n− 1}
at random and then defining ai to be the remainder of a
2
i−1 mod n,
for all i ≥ 2. Assume that our chosen a1 is coprime to n.
(a) (2 marks) Let p denote a prime factor of n, and let k be the
multiplicative order of a1 mod p. Show that for j < i,
ai ≡ aj (mod p) ⇐⇒ 2i−1 ≡ 2j−1 (mod k).
(b) (2 marks) Write k = 2sm where m is odd, and let ` be the
multiplicative order of 2 mod m. Show that for j < i,
2i−1 ≡ 2j−1 (mod k) ⇐⇒ j > s and i ≡ j (mod `).
(c) (3 marks) Without knowing any special information about n
other than that it is odd and composite, would you expect this
new version of Pollard’s Rho method to find a nontrivial divisor
of n more quickly than trial division? Explain your answer.