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.
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 ⊆ 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 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 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 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 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
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 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.
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
DOI 10.1016/j.endm.2019.02.003See 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.