COMPUTATIONAL NUMBER THEORY 
Trinity Term 2018

1) An algorithm reads in the binary digits of a positive integer N and
determines whether N is a multiple of 3.  Show that the algorithm
takes time at least of order n, where n is the number of binary digits of N.

2) An algorithm reads in the positive integer N, (in binary) 
and prints out the binary
expansion of 3^N (3 to the power N).  Show that this takes time at
least of order N. 

3) Find the points on the elliptic curve y^2=x^3-x (mod 7), and
determine the "group table", listing all compositions P+Q=R.

4) Suppose that the elliptic curve y^2=x^3+ax+b (mod p) has p+1-t
points.  Find a second elliptic curve modulo p which has p+1+t points.

5) Perform the LLL algorithm on the basis (4,5) (13,17).

6) In the LLL reduction algorithm, suppose that the initial basis
vectors b_i all have integer coordinates of modulus at most B.  Give
an upper bound on the size of the determinants Delta(L_i), and derive
an upper bound for the total number of steps B which can involve a
swap.

7) If Step B in the LLL algorithm performs a swap exactly N times, show
that Step B is performed at most k-1+2N times; and hence estimate the
overall number of loops performed by the algorithm (under the
assumptions of Q4).

8) In smooth square factoring (pages 45 & 46), what is the probability
that a random positive integer k < n is b-smooth ?  Roughly how many such
random integers k would you expect to have to pick in order to find N
b-smooth values ?  How long does it take to test an integer k < n to
see if it is b-smooth, and if it is, to factor it (using trial
division).  Suppose that the set B contains N-1 primes q.  How long
does Gaussian elimination take to find integers e_1,...,e_N  (not all
even), such that

sum_{i=1}^N e_i r_{q,i} = 0 (mod 2) 

for each of the N-1 primes q ?  Show that the overall running time of
the method is at most of order (Nb u^u + N^3) times a power of log n,
where u = (log n)/(log b).  How would you choose b to optimize this ?
(First
optimize Nb u^u.  You should discover that the optimal (i.e. minimal)
value for this exceeds the corresponding value for N^3.)

9)  In Pollard's p-1 method (page 46 & 47), suppose that n=pp', with p and
p' prime.  Estimate the probability that p-1 is b smooth for
b=p^{1/2}.  Assume that p-1 is b-smooth for this b, but that p'-1 is
not b-smooth.  How long will it take to compute hcf(2^k-1,n), in the
notation of the notes?

10)  Demonstrate the p-1 method on n=77, taking b=4 and a=2.

11)  Which of the algorithms in the notes can be run easily using
several computers in parallel?