# Publications

## Contents

Click on the title to see an abstract, publication details and links to the full text.

Note: the text of some older papers has been rather crudely translated into TeX or PostScript format. In a few cases the full text is not available at all.

• Communication Theory, with C.M. Goldie, LMS Student Texts 20, CUP, 1991
The introduction in DVI or PS format.

Math Review 93a:94001

• Fermat's Last Theorem, a video of the LMS popular lectures in 1994.

#### Elliptic curves with good reduction away from 2

Math. Proc. Cambridge Philos. Soc. 96 (1984) 25-38

We list the elliptic curves defined over Q(√-1), Q(√-2) and Q(√-3) with good reduction away from 2.

Math Review 85j:14080
Zbl 602.14030.

#### a-convexity

Math. Proc. Cambridge Philos. Soc. 97 (1985) 63-68

For a in R, define V ⊆ Rn to be $a$-convex if x ,y in V implies ax + (1-a)y in V. Let D = {0,1} and $D(a)$ the $a$-convex hull of $D$ in R1. We show that $D(a)$ is either dense in $[0,1]$ or in $R$ or a set of isolated points: in the latter case we call $a$ sparse. We show that a necessary condition for $a$ to be sparse is that it be an algebraic integer, that a sufficient condition is that $a$ be a totally real algebraic integer with all but one conjugate in [0,1], and that this condition is also necessary if $a$ is quadratic.

See the full paper in DVI or PS format.

Math Review 86e:11114
Zbl 571.10041.

#### A sequence well-distributed in the square

Math. Proc. Cambridge Philos. Soc. 99 (1986) 19-22

Math Review 87c:11058
Zbl 581.10024.

#### Elliptic curves with everywhere good reduction

Let $N$ be a prime congruent to 1 modulo 4 and $E$ an elliptic curve over $K = Q(√ N)$ which has good reduction at all primes of $K$ and is isogenous to the Galois conjugate curve by an isogeny of degree $c$. Then the L-function of $E$ over $K$ has coefficients which are congruent modulo primes dividing $c$ to the Fourier coefficients of a modular form for the subgroup of Γ0(N) corresponding to the quadratic character of conductor $N$.

See the full paper in PS format, with tables.

#### Elliptic curves with good reduction away from 2: II

Math. Proc. Cambridge Philos. Soc. 100 (1986) 435-457

We continue the study of elliptic curves defined over a quadratic field Q(√d) with good reduction at primes not dividing 2 begun in part I. We extend the results of I to show that such a curve must have a point of order 2 also defined over Q(√d) when d = -7, -3, -2, -1, 2, 3 or 5 and list all such curves over Q(√-7).

Math Review 87j:11052
Zbl 617.14022.

#### Elliptic curves with good reduction away from 3

Math. Proc. Cambridge Philos. Soc. 101 (1987) 451-9

In this paper we list the elliptic curves defined over Q(√-3) with good reduction away from the prime dividing 3.

See the full paper in DVI or PS format.

Math Review 88d:11056
Zbl 632.14030.

#### Simultaneous Pellian equations

Math. Proc. Cambridge Philos. Soc. 101 (1987) 451-459

We describe a method for finding integer solutions of simultaneous Pellian equations, that is, integer triples $(x,y,z)$ satisfying equations of the form $$(x+f)^2 - a y^2 = b$$ and $$(x-f)^2 - c z^2 = d$$ where the coefficients $a,b,c,d,f$ are integers and we assume that $a$, $c$ and $ac$ are not square. The method for dealing with the computational aspect of solving these equations which avoids calculation to high accuracy, and which has a running time expected to be approximately linear in $h$; it is well adapted to practical computation. It verifies that a set of previously obtained solutions is indeed complete. If there is a further solution, the method will usually give enough information to find it.

See the full paper in DVI or PS format.

Math Review 89a:11029
Zbl 641.10014.

#### Elliptic curves with good reduction away from 2: III

In this paper we list the elliptic curves defined over Q(√5) with good reduction away from 2. We use the results of the previous papers Part I and Part II. By Theorem 1.14 of I, such a curve must have a point of order 2 defined over Q(√5) and by Theorem 2.3 of II, if t ∈ Q(√5) is the corresponding value of the Hauptmodul on $X_0 (2)$ then either $t$ or $t' = 4096 / t$ satisfies one of the equations $$t = 64 u / v, u + v = x^2$$ or $$t = 64v / 2^a u, 2^a u + v = x^2$$ where $u$, $v$ are units, $x ∈ Q ( √ 5 )$ and $a ≥ 0$. We solve these equations and determine the corresponding $j$-invariants and obtain a global minimal equation in each isomorphism class by Tate's algorithm. There are 368 isomorphism classes of these curves.

See the full paper in DVI or PS format, with tables of j-invariants and minimal equations.

Arxiv version math.NT/9803012 or here

#### Computations on elliptic Gauss sums

Proceedings IMA Conference on Computers in Mathematical Research (edd. N.M. Stephens and Thorne) OUP 1988

We describe some calculations made jointly with M.J. Taylor on elliptic analogues of the Gauss sum in order to obtain information on the Galois module structure of rings of integers in Abelian extensions of imaginary quadratic fields.

See the full paper in DVI or PS format.

Math Review 89i:11122
Zbl 636.12008.

#### Binomial equivalence of algebraic integers

J. Indian Math. Soc. 58:1 (1992) 33-38

We give a short proof that binomial equivalence is an equivalence relation and show how to construct algebraic numbers, either integral or non-integral, with an arbitrarily large finite equivalence class.

See the full paper in DVI or PS format.

Math Review 94a:11160
Zbl 903.11024.

#### Recognising elements of finite fields

Proceedings 2nd IMA Conference on Coding and Cryptography 1989 (ed. C.J. Mitchell) IMA Conference Series (n.s.) 33, OUP, 1991, pp. 193-197

It is well known that there is precisely one finite field up to isomorphism of every prime power order $q = p^n$. Every such field may be realised as the field generated over ${\rm GF}(p)$ by a root of an irreducible separable polynomial, $f(X)$, say, of degree $n$. Hence, given two such polynomials $f(X)$ and $g(Y)$ of the same degree, each of the roots of $f$ must be expressible as a polynomial, of degree at most $n$, in any root of $g$, and conversely. We describe two algorithms for calculating the expressions which find the roots of one irreducible separable polynomial over a finite field in terms of the roots of another such polynomial.

See the full paper in DVI or PS or PDF format.

Math Review 93h:11138
Zbl 746.11055.

Math. Comp. 60:202, (Apr 1993) 841-845

The sequence of consecutive integer squares has constant second difference 2. We list every such sequence of squares containing a term less than $1000^2$, using the methods and results of Simultaneous Pellian equations.

See the full paper in DVI or PS format.

Math Review 93h:11029
Zbl 779.11013

#### Arithmetic of diagonal quartic surfaces I (with P. Swinnerton-Dyer)

L-functions and arithmetic, Proc. Durham Symp 1989 (edd. J.H. Coates and M.J. Taylor, LMS lecture notes 153, CUP, 1991,

This is the first of what we hope will be a number of papers on the arithmetic of diagonal quartic surfaces $$V : a_0 X^4_0 + a_1 X^4_1 + a_2 X^4_2 + a_3 X^4_3 = 0$$ defined over Q, where $a_0 a_1 a_2 a_3 \not= 0$. In what follows we shall always assume that the $a_\nu$ are integers with no common factor, which clearly involves no loss of generality. We are interested in K3 surfaces more generally, as being the simplest kind of variety whose arithmetic theory is still rudimentary, but there are three advantages in confining ourselves to the narrower class (1): it is possible to write down the zeta-function explicitly, the Neron-Severi group over Q is frequently non-trivial, and $V$ has a convenient form and a convenient number of parameters for numerical experimentation.

See the full paper in DVI or PS format.

Math Review 92d:11068
Zbl 736.14006.

#### Recurrent sequences modulo prime powers

Proceedings 3rd IMA Conference on Coding and Cryptography 1991 (ed. M. Ganley) OUP 1993, 297-310

We study the possible periods of linear recurrent sequences modulo $p^n$ for prime $p$. The maximum possible period depends on the degree and ramification index of the $p$-adic field generated by the roots of the auxiliary polynomial of the recurrence: in most cases, this is sufficient to determine the maximum period completely. In any case, the maximum period modulo $p^n$ is determined by the period modulo $p^2$ if $p$ is odd, or modulo $2^3$.

See the full paper in DVI or PS format.

Math Review 95b:11019
Zbl 822.11012.

#### An A4~extension of Q attached to a non-selfdual automorphic form on GL(3)

(with A. Ash and R.L. Taylor)

Math. Annalen 291:4 (1991) 753-766

Conjectures concerning the relations between motives and automorphic representations of GL(n) over number fields have been made by Clozel [C1]. They make precise part of the programme indicated by Langlands in [La]. Once a motive is attached to an automorphic representation, one can derive a compatible series of λ-adic representations of GQ attached to it in the usual way.

The purpose of this paper is to investigate the conjecture for this cuspidal cohomology in the following way. We do not know how to guess at a motive, or even a λ-adic representation. We seek merely the reduction mod λ of the conjectured λ-adic representation. For a few small primes λ in the Hecke algebra, congruences mod λ between the computed automorphic forms and Eisenstein series coming from classical holomorphic cusp forms of weight 2 for GL(2) were already noted in [AGG]. Hence for such λ, one knows how to attach a representation ρ of GQ into GL(3,F) for some finite field F = Oλ/λ. In our examples there happens always to be such a congruence modulo some prime above 2. For primes above 3, we have a congruence for the cuspform of level 53. For the cuspform of level 89, 3 is inert in the Hecke algebra, so that F would have 9 elements and this was too big for us to compute with.

We find, a posteriori, that there should be a congruence mod λ between our form of level 61 and an Eisenstein series built from a Maass form on GL(2). We see no way of predicting its existence a priori, nor indeed to prove the congruence; i.e. to show that all the Hecke eigenvalues (not just those computed in [AGG]) match properly with the traces of Frobenius elements. It might be worthwhile to redo the computations, find the Hecke eigenvalues for the first few hundred primes, and check that they continue to match the traces of Frobenius elements.

See the full paper in DVI or PS format.

Math Review 93c:11031
Zbl 713.11036.

#### Some primality testing algorithms

AMS Notices, 40, no. 9 (Nov 1993) 1203-1210

and in revised form in Proc 4th Rhine workshop on Computer Algebra, Karlsruhe, March 1994 (ed. J. Calmet) 2-13

We describe the primality testing algorithms in use in some popular computer algebra systems, and give some examples where they break down in practice.

See the full paper in DVI or PS format.

#### On a digital signature scheme with message recovery

Electronics Letters, 30, no. 11 (15 May 1994) 852

Piveteau has proposed a digital signature scheme with message recovery. We show that the method proposed for recovering the message is impractical, and give a practical alternative.

See the full paper in DVI or PS format.

#### Extending the Wiener attack to RSA-type cryptosystems

Electronics Letters, 31, no. 20 (28 Sep 1995) 1736-1738

We show that the attack of Wiener on RSA cryptosystems with a short deciphering exponent extends to systems using other groups such as elliptic curves, and {\smc Luc}.

See the full paper in DVI or PS format.

#### Extending the Hastad attack to LUC

Electronics Letters, 31, no. 21 (12 Oct 1995) 1827-1828

We show that the attack of H\aa stad on broadcast messages using the RSA cryptosystem extends to the case where the public keys are different, and that the attack is also applicable to the {\smc Luc} system, with the same security parameters.

See the full paper in DVI or PS format.

#### Carmichael numbers up to 10^15

Math. Comp. 61:203 (Jul 1993) 381-391

There are 105212 Carmichael numbers up to $10^{15}$: we describe the calculations. The numbers were generated by a back-tracking search for possible prime factorisations, and the computations checked by searching selected ranges of integers directly using a sieving technique, together with a large prime variation''.

The computations have been extended to 10^16 , 10^17 and 10^18.

See the full paper in PS format.

Math Review 93m:11137
Zbl 780.11069

#### Distribution of recurrent sequences modulo prime powers

Extended abstract in Proceedings 5th IMA Conference on Coding and Cryptography 1995 (ed. C. Boyd) Springer Lecture Notes in Computer Science 1025 (1995) 188-189

We study the distribution of linear recurrent sequences modulo $p^n$ for prime $p$ when the auxiliary polynomial is irreducible and the period is maximal. We show that such a sequence takes each possible value equally often up to an error of order $p^{n/2}$.

See the extended abstract in DVI or PS format.

Math Review 95b:11019

#### Back to the Dark Ages

(with James McKee)

Extended abstract presented at ANTS II, Bordeaux, May 1996. Algorithmic Number Theory ed. Henri Cohen, Springer Lecture Notes in Computer Science 1122 (1996) 217-224

Slides from the SECANTS-1 meeting, Oxford, December 1995 and the RSA Data Security Conference, San Francisco, January 1997.

In recent years, there has been spectacular progress in the practical art of factoring. By contrast, the theoretical problem of finding deterministic algorithms which provably factor composite numbers has made little, if any, progress. In this talk, I report on joint work with James McKee examining some old exponential-time ("Dark Ages") deterministic algorithms: we give deterministic running times for them, and provide several new examples of algorithms of this type.

See the extended abstract in DVI or PS format.

Math Review 98a:11183
Zbl 957.11054.

#### An asymptotic upper bound for multiplier design

Electronics Letters, 32, no. 5 (29 Feb 1996) 420

The cost, in terms of adders/subtractors, of multiplication by n-bit integers when shifts are free is shown to be of the order of n /(log n)α for any α < 1.

See the paper in DVI or PS format.

#### On-line multiple secret sharing

Electronics Letters, 32, no. 12 (6 Jun 1996) 1087-1088.

A protocol for computationally secure on-line'' secret-sharing is presented, based on the intractability of the Diffie-Hellman problem, in which the participants' shares can be reused. Each share is the same size as one of the secrets.

See the paper in DVI or PS format.

#### On using Carmichael numbers for public key encryption systems

Proceedings 6th IMA Conference on Coding and Cryptography, Cirencester 1997, (ed. M. Darnell) Springer Lecture Notes in Computer Science 1355 (1997) 265-269

Slides from the meeting.

We show that the inadvertent use of a Carmichael number instead of a prime factor in the modulus of an RSA cryptosystem is likely to make the system fatally vulnerable, but that such numbers may be detected.

See the paper in DVI, PS or PDF format.

Zbl 1083.94519

#### Pseudoprimes up to 10^13

Proceedings ANTS-IV, 4th Algorithmic Number Theory Symposium, Leiden, July 2000. Springer Lecture Notes in Computer Science 1838 (2000) 459-474.

There are 38975 Fermat pseudoprimes (base 2) up to $10^{11}$ and 101629 up to $10^{12}$ and 264239 up to $10^{13}$: we describe the calculations and give some statistics. The numbers were generated by a variety of strategies, the most important being a back-tracking search for possible prime factorisations, and the computations checked by searching selected ranges of integers directly using a sieving technique.

Math Review 2002g:11177
Zbl 1032.11060.

#### Economical numbers

A number n is said to be economical if the prime power factorisation of n $n$ can be written with no more digits than n itself. We show that under a plausible hypothesis, related to the twin prime conjecture, there are arbitrarily long sequences of consecutive economial numbers, and exhibit such a sequence of length 9, starting at 1034429177995381247.

See the paper in DVI or PS format.

Arxiv version math.NT/9802046 or here

#### Comments on Key agreement scheme based on generalised inverses of matrices

Electronics Letters, 34, no. 7 (2 April 1998) 653-654

We show that the security parameters of a proposed key agreement scheme, based on generalised matrix inverses, are significantly lower than suggested by the authors.

See the paper in DVI or PS format.

#### Further attacks on server-aided RSA cryptosystems

(with James McKee)

Lim and Lee describe protocols for server-aided RSA digital signatures involving moduli $N$ with special structure: $N = pq$ where $p$ and $q$ are both of order $N^{1/2}$, and $p-1$ and $q-1$ have a large common factor $\beta$. We describe a method to factor such numbers in time $O(N^{1/4}/\beta)$ and show that this renders the proposed system insecure.

See the paper in DVI or PS format.

#### On a cryptosystem of Vanstone and Zuccherato

(with James McKee)

Vanstone and Zuccherato proposed a public-key elliptic curve cryptosystem in which the public key consists of an integer $N$ and an elliptic curve $E$ defined over the ring ${\mathbf Z}/N{\mathbf Z}$. Here $N$ is a product of two secret primes $p$ and $q$, each of special Form, and the order of $E$ modulo $N$ is smooth. We present three attacks, each of which factors the modulus $N$ and hence breaks the cryptosystem. The first attack exploits the special form of $p$ and $q$; the second exploits the smoothness of the elliptic curve; and the third attack breaks a proposed application of the system to user authentication. For parameters as in \cite{VZ}, the modulus can be factored within a fraction of a second.

See the paper in DVI or PS format.

#### Square values of quadratic polynomials

Allinson asked whether a quadratic polynomial symmetric about an integer point which is not a perfect square can take more than five integer square values about the centre of symmetry. We show that it can not by reducing the problem to finding the rational points on certain elliptic curve. We show that the problem is equivalent to an old result of Pocklington.

See the paper in DVI or PS format.

#### Carmichael numbers up to 10^16

We extend our previous computations to show that there are 246683 Carmichael numbers up to $10^{16}$. As before, the numbers were generated by a back-tracking search for possible prime factorisations together with a large prime variation''. We present further statistics on the distribution of Carmichael numbers.

The computations have been extended to 10^17 and 10^18.

See the full paper in PS format.

Arxiv version math.NT/9803082

#### Cheating in split knowledge RSA parameter generation (with Marc Joye)

Given at WCC99, Paris, 11th-14th January 1999.

D. Augot and C. Carlet, editors, Workshop on Coding and Cryptography, 157-163, Paris, January 1999.

Cocks (1997) has recently described a protocol for two parties to generate an RSA modulus $N = PQ$ where neither party has knowledge of the factorisation, but which enables the parties to collaborate to decipher a encrypted message. We describe a number of ways in which it is possible for one of the parties to the protocol to cheat and obtain knowledge of the factorisation, and suggest modifications to the protocol to guard against cheating.

See the paper in DVI or PS format.

Ashbacher has posed a number of questions relating to the pseudo-Smarandache function $Z(n)$. In this note we show that the ratio of consecutive values $Z(n+1)/Z(n)$ and $Z(n-1)/Z(n)$ are unbounded; that $Z(2n)/Z(n)$ is unbounded; that $n/Z(n)$ takes every integer value infinitely often; and that the series \sum_n 1/Z(n)^α is convergent for any α > 1$. See the full paper in DVI format or PS format. Arxiv version math.NT/0504118 Math Review 2007g:11005 Zbl pre05008792 #### Carmichael numbers up to 10^17 We extend our previous computations to show that there are 585355 Carmichael numbers up to$10^{17}$. As before, the numbers were generated by a back-tracking search for possible prime factorisations together with a large prime variation''. We present further statistics on the distribution of Carmichael numbers. See the full paper in PS format. Arxiv version math.NT/0504119 The computations have been extended to 10^18. #### Carmichael numbers with small index We define the index of a Carmichael number N as the quotient i(N) = (N-1)/λ(N). We show that i(N) tends to infinity over Carmichael numbers N and give an algorithm for listing all the numbers with given value of i which we illustrate by listing the numbers with index up to 100. See a poster for the ANTS VII meeting in PS format. #### The distance of a permutation from a subgroup of Sn In Combinatorics and Probability edited by Graham Brightwell, Imre Leader, Alex Scott and Andrew Thomason, (CUP, 2007) 473-480 We show that the problem of computing the distance of a given permutation from a subgroup H of Sn is in general NP-complete, even under the restriction that H is elementary Abelian of exponent 2. The problem is shown to be polynomial-time equivalent to a problem related to finding a maximal partition of the edges of an Eulerian directed graph into cycles and this problem is in turn equivalent to a standard NP-complete problem of Boolean satisfiability. See the full paper in PDF format. Arxiv version math.CO/0511501 #### Carmichael numbers up to 10^18 We extend our previous computations to show that there are 1401644 Carmichael numbers up to$10^{18}$. As before, the numbers were generated by a back-tracking search for possible prime factorisations together with a large prime variation''. We present further statistics on the distribution of Carmichael numbers. See the full paper in PS format. Arxiv version math.NT/0604376 The computations have been extended to 10^19. #### A note on Lehmer's Totient Problem Lehmer's Totient Problem asks whether there is an integer n such that φ(n) divides n-1. We give a computational proof that there is no such n less than 1030 and that the number of prime factors of such a number must be at least 15. See a poster for the ANTS VII meeting in PS format. #### Carmichael numbers up to 10^19 We extend our previous computations to show that there are 3381806 Carmichael numbers up to$10^{19}$. As before, the numbers were generated by a back-tracking search for possible prime factorisations together with a large prime variation''. We present further statistics on the distribution of Carmichael numbers. See a poster for the ANTS VII meeting in PS format. The computations have been extended to 10^21. #### Absolute quadratic pseudoprimes Proceedings Conference on Algorithmic Number Theory, Turku, May 2007. Turku Centre for Computer Science General Publications 46, edited by Anne-Maria Ernvall-Hytönen, Matti Jutila, Juhani Karhumäki and Arto Lepistö. We describe some primality tests based on quadratic rings and discuss the absolute pseudoprimes for these tests. See the full paper in PDF format. #### Carmichael numbers up to 10^21 Proceedings Conference on Algorithmic Number Theory, Turku, May 2007. Turku Centre for Computer Science General Publications 46, edited by Anne-Maria Ernvall-Hytönen, Matti Jutila, Juhani Karhumäki and Arto Lepistö. We extend our previous computations to show that there are 20138200 Carmichael numbers up to$10^{21}\$. As before, the numbers were generated by a back-tracking search for possible prime factorisations together with a large prime variation''. We present further statistics on the distribution of Carmichael numbers.

See the full paper in PDF format.

See a poster for the ANTS VIII meeting in PDF format.

#### Korselt numbers and sets

(with Kais Bouallegue, Othman Echi)

Let a be a non-zero integer. A positive integer N is said to be an a-Korselt number (Ka-number, for short) if p - a divides N - a for each prime divisor p of N. We are concerned, here, with both a numerical and theoretical study of composite squarefree Korselt numbers.

Some preprints are also available in the Number Theory section of the eprint Arxiv: try here.