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

- Elliptic curves with good reduction away from 2
*a*-convexity- A sequence well-distributed in the square
- Elliptic curves with everywhere good reduction
- Elliptic curves with good reduction away from 2: II
- Elliptic curves with good reduction away from 3
- Simultaneous Pellian equations
- Elliptic curves with good reduction away from 2: III
- Computations on elliptic Gauss sums
- Binomial equivalence of algebraic integers
- Recognising elements of finite fields
- Squares in quadratic progression
- Arithmetic of diagonal quartic surfaces I (with P. Swinnerton-Dyer)
- Recurrent sequences modulo prime powers
- An A4~extension of Q attached to a non-selfdual automorphic form on GL(3) (with A. Ash and R.L. Taylor)
- The Carmichael numbers up to 10 to the 15
- Some primality testing algorithms
- On a digital signature scheme with message recovery
- Extending the Wiener attack to RSA-type cryptosystems
- Extending the Hastad attack to LUC
- The pseudoprimes up to 10 to the 13
- Distribution of recurrent sequences modulo prime powers
- Back to the Dark Ages (with James McKee)
- An asymptotic upper bound for multiplier design
- On-line multiple secret sharing
- On using Carmichael numbers for public key encryption systems
- Economical numbers
- On a key agreement scheme based on generalised inverses of matrices
- Further attacks on server-aided RSA cryptosystems (with James McKee)
- On a cryptosystem of Vanstone and Zuccherato (with James McKee)
- Square values of quadratic polynomials
- The Carmichael numbers up to 10 to the 16
- Cheating in split-knowledge RSA parameter generation (with Marc Joye)
- Some properties of the pseudo-Smarandache function
- The Carmichael numbers up to 10 to the 17
- The distance to a subgroup of the symmetric group
- Carmichael numbers with small index
- The Carmichael numbers up to 10 to the 18
- A note on Lehmer's Totient Problem
- The Carmichael numbers up to 10 to the 19
- Absolute quadratic pseudoprimes
- The Carmichael numbers up to 10 to the 21
- Korselt numbers and sets
- Enumerating forbidden factors

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.

Math Review 93a:94001

Back to Richard Pinch's personal home page

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.

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

For a in **R**, define V ⊆ **R**^{n} to be
$a$-*convex*
if **x** ,**y** in V implies a**x** + (1-a)**y** in V.
Let D = {0,1} and $D(a)$ the $a$-convex hull of $D$ in **R**^{1}.
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 PS format.

Math Review 86e:11114

Zbl 571.10041.

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

Math Review 87c:11058

Zbl 581.10024.

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.

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.

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 PS format.

Math Review 88d:11056

Zbl 632.14030.

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 PS format.

Math Review 89a:11029

Zbl 641.10014.

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

Arxiv version math.NT/9803012 or here

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 PS format.

Math Review 89i:11122

Zbl 636.12008.

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 PS format.

Math Review 94a:11160

Zbl 903.11024.

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 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 PS format.

Math Review 93h:11029

Zbl 779.11013

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 PS format.

Math Review 92d:11068

Zbl 736.14006.

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 PS format.

Math Review 95b:11019

Zbl 822.11012.

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
G_{Q} 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
G_{Q} 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 PS format.

Math Review 93c:11031

Zbl 713.11036.

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

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 PDF format.

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 PS format.

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 PS format.

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 PS format.

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

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 PS format.

Math Review 95b:11019

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 PS format.

Math Review 98a:11183

Zbl 957.11054.

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 PS format.

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 PS format.

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 PS or PDF format.

Zbl 1083.94519

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.

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 PS format.

Arxiv version math.NT/9802046 or here

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 PS format.

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 PS format.

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 PS format.

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 PS format.

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

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 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 in PS format.

Arxiv version math.NT/0504118

Math Review 2007g:11005

Zbl pre05008792

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*.

Associated data files are available.

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

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 *S _{n}* is in general NP-complete, even
under the restriction that

See the full paper in PDF format.

Arxiv version math.CO/0511501

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*.

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
10^{30} 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.

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*.

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.

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.

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

Exposition of an application of the theory
of recurrence relations to enumerating strings over an alphabet with
a forbidden factor (consecutive substring). As an illustration we
examine in detail the case of binary strings with a forbidden factor
of *k* consecutive symbols **1** for given *k*,
using generating function techniques that deserve to be better known.

Electronic Notes in Discrete Mathematics
**71** (March 2019) 15-20

See slides for the 2nd IMA Conference on Theoretical and Computational Discrete Mathematics in PDF format.

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 20/iii/'19 by Richard Pinch