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.

    Back to Richard Pinch's personal home page


    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    A sequence well-distributed in the square

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

    Math Review 87c:11058
    Zbl 581.10024.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    Squares in quadratic progression

    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

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Associated data files are available.

    See the full paper in DVI or PS format.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Associated data files are available.

    See the full paper in PS format.

    Math Review 93m:11137
    Zbl 780.11069

    Back to the table of contents

    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 table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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

    Back to the table of contents

    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.

    Associated data files are available.

    See the full paper in PS format. (Copyright © Springer-Verlag 2000)

    Math Review 2002g:11177
    Zbl 1032.11060.

    Back to the table of contents

    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

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Associated data files are available.

    See the full paper in PS format.

    Arxiv version math.NT/9803082

    Back to the table of contents

    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.

    Back to the table of contents

    Some properties of the pseudo-Smarandache function

    Scientia Magna 1.2 (2005)

    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

    Back to the table of contents

    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.

    Associated data files are available.

    See the full paper in PS format.

    Arxiv version math.NT/0504119

    The computations have been extended to 10^18.

    Back to the table of contents

    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.

    Associated data files are available.

    See a poster for the ANTS VII meeting in PS format.

    Back to the table of contents

    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

    Back to the table of contents

    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.

    Associated data files are available.

    See the full paper in PS format.

    Arxiv version math.NT/0604376

    The computations have been extended to 10^19.

    Back to the table of contents

    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.

    Associated data files are available.

    See a poster for the ANTS VII meeting in PS format.

    Back to the table of contents

    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.

    Associated data files are available.

    See a poster for the ANTS VII meeting in PS format.

    The computations have been extended to 10^21.

    Back to the table of contents

    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.

    Back to the table of contents

    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.

    Associated data files are available.

    See the full paper in PDF format.

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

    Back to the table of contents

    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.

    International Journal of Number Theory (IJNT) 6 (2010) 257-269 DOI: 10.1142/S1793042110002922

    Back to the table of contents


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


    Back to the table of contents

    Back to Richard Pinch's personal home page or mathematics page.


    Updated 13/iv/'10 by Richard Pinch