ELLIPTIC PSEUDOPRIMES

Ian Miyamoto and M. Ram Murty^{1}

§1. INTRODUCTION.

The problem of determining whether a given integer is prime or not is very basic to mathematics. Fermat’s ‘little theorem’ provides us with a criterion:

(0.1)  for any odd prime p,  2^{p−1} ≡ 1 (mod p).

One may thus test a given n by computing 2^{n−1} (mod n). If the congruence

(0.2)  2^{n−1} ≡ 1 (mod n)

fails, then n is definitely composite. If, however (0.2) is satisfied, all that can be said is that n is probably prime. Indeed, there are infinitely many composite numbers that satisfy (0.2). These are called false witnesses or pseudoprimes (to the base 2) and denoted psp_{2} for short.(More generally, for any odd prime p, (a, p) = 1 one has a^{p−1} ≡ 1 (mod p) so we may likewise define psp_{a}.) Though there are infinitely many such numbers, their cardinality up to x is substantially smaller than the number of primes up to x. This therefore gives a probabilistic primality test. This test and modifications of it have been studied extensively. (The reader may refer to [5] or [12].)

Indeed, let P_{2}(x) denote the number of psp_{2} up to x. Erdös [3] established that for some positive constants c_{1}, c_{2},

(1.1)  c_{1} log x ≪ P_{2}(x) ≪ xR(x)^{−c_{2}}

where

(1.2)  R(x) = exp(\sqrt{log x log log x}).

Pomerance [12] had subsequently improved these bounds to

(1.3)  exp(log^{5/14} x) ≪ P_{2}(x) ≪ xL(x)^{−1/2},

where

(1.4)  L(x) = exp (log x log log log x/ log log x) ,

1Research supported by NSERC grant A9418

and has conjectured that this is nearly best possible: the correct order guessed to be

xL(x)^{−1+o(1)}.

Recently elliptic curves have been applied to this problem of distinguishing primes from composites, again, using only the basic theory. Gordon in [7], for example, considers such a test which uses curves (with what is known as complex multiplication), that is analogous to the Fermat test described above.

In order to describe the test quickly, we consider a special case. Let E be an elliptic curve with complex multiplication by the ring of Gaussian integers, Z[i]. If E has good reduction at p and p ≡ 3 (mod 4), then E(F_{p}) has size p + 1. If P is a rational point of E of infinite order, then (p + 1)P = 0 in E(F_{p}), provided P has good reduction at p. This is analogous to Fermat’s little theorem, and we can utilise this as a primality test for primes ≡ 3 (mod 4). More precisely, we can utilise the division polynomials to give an equivalent formulation of this criterion. Let ψ_{n} denote the n-th division polynomial (as defined in §2). The equation (p + 1)P = 0 in E(F_{p}) can be rephrased as p|ψ_{p+1}(P). We therefore say that a composite number n is an elliptic pseudoprime if n|ψ_{n+1}(P). Gordon [7] has recently shown that there are infinitely many such pseudoprimes. Assuming a generalised Riemann hypothesis (GRH), he proved [6] that the number of elliptic pseudoprimes up to x is less than

\frac{x log log x}{(log x)^{2}}.

This therefore gave a probabilistic primality test using elliptic curves, but only conditionally.

The purpose of this paper is to establish this probabilistic primality test without the use of the generalised Riemann hypothesis. We do this by showing that the number of elliptic pseudoprimes up to x is

≪ \frac{x(log log x)^{7/2}}{(log x)^{3/2}} .

In section 2 we will provide the needed background of elliptic curves in order to describe Gordon’s test. In section 3 we will describe the test, and a suitable generalization of the test to elliptic curves of rank ≥ 2. The idea is to consider r independent rational points P_{1}, ..., P_{r} on the curve E and let Γ be the group generated by them. Denote by N_{Γ}(x) the number of composite n ≤ x satisfying n|ψ_{n+1}(P_{i}), 1 ≤ i ≤ r. The case of elliptic pseudoprimes can be viewed as the case r = 1. If r ≥ 2, we are able to obtain a substantially better estimate for N_{Γ}(x). In sections 4-6 we will prove our main theorems on the number of elliptic pseudoprimes. In case r ≥ 2, we obtain

N_{Γ}(x) ≪ xR(x)^{−c},

where

R(x) = exp(\sqrt{log x log log x}),

and c is some positive constant. This upper bound is the same as established for psp_{2} by Erdös [3].

The key tool in the derivation is a lemma established by Gupta and Ram Murty [8] and the methods of that paper. This lemma does generalise to elliptic curves over arbitrary number fields and more generally to abelian varieties. However, the error terms grow large as the degree of the base field increases and therefore the results of this paper do not generalise easily to other number fields.

§2 ELLIPTIC CURVES. We briefly review the salient features of elliptic curves. For a quick survey, the reader should consult Tate [14] and for a detailed treatment, Silverman [13] is ideal.

Let k be a field. An elliptic curve E defined over k may be thought of as the zero set of a plane algebraic curve given in affine coordinates by

(2.1)  E : y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6},

where the a_{i} ∈ k. (In projective space E is defined by a nonsingular homogeneous cubic polynomial.) If the characteristic of k is not 2 or 3, E has the simpler model of the form:

(2.2)  E : y^{2} = x^{3} + ax + b.

A simple calculation shows that the nonsingularity of E is equivalent to the fact that

Δ = −16(4a^{3} + 27b^{2}) ≠ 0.

This number is called the discriminant of E and is −16 times the discriminant of the polynomial

x^{3} + ax + b.

It is well-known that multiplication by m is a map of degree m^{2}. One may see this in many ways. A method is by using explicit formulas. Indeed, using the addition law, one can define division polynomials,

(2.3)  {ψ_{n}}_{n=1}^{∞}.

Each ψ_{n}(x, y) is in k[x, y] and has zeroes exactly at the n-division points of E(\overline{k}). (Here \overline{k} is the algebraic closure of k.) These polynomials may be defined by [1]:

(2.4)  \{ \begin{matrix}ψ_{1} & = 1, \\ ψ_{2} & = 2y, \\ ψ_{3} & = 3x^{4} + 6ax^{2} + 12bx − a^{2}, \\ ψ_{4} & = 4y(x^{6} + 5ax^{4} + 20bx^{3} − 5a^{2}x^{2} − 4abx − 8b^{2} − a^{3}), \end{matrix}

and the recursive relation,

(2.5)  ψ_{m−n}ψ_{m+n} = ψ_{m−1}ψ_{m+1}ψ_{n}^{2} − ψ_{n−1}ψ_{n+1}ψ_{m}^{2}.

By setting m = n + 1 in (2.5) we find that

ψ_{2n+1} = ψ_{n}^{3}ψ_{n+2} − ψ_{n+1}^{3}ψ_{n−1},

and by setting m = n + 2,

2yψ_{2n} = ψ_{n}(ψ_{n+2}ψ_{n−1}^{2} − ψ_{n−2}ψ_{n+1}^{2}).

Further we define

(2.6)  \begin{aligned}ϕ_{m} & = xψ_{m}^{2} − ψ_{m−1}ψ_{m+1}, \\ 4yω_{m} & = ψ_{m+2}ψ_{m−1}^{2} − ψ_{m−2}ψ_{m+1}^{3}. \end{aligned}

It follows that for m odd, ϕ_{m}, y^{−1}ω_{m}, ψ_{m}, and for m even, (2y)^{−1}ψ_{m}, ϕ_{m}^{2}, ω_{m} are all polynomials in k[a, b, x]. Moreover, ϕ_{m} is monic, and ϕ_{m} and ψ_{m}^{2} are relatively prime of degree m^{2} and m^{2} − 1 respectively, and

(2.7)  [m]P = (\frac{ϕ_{m}}{ψ_{m}^{2}} , \frac{ω_{m}}{ψ_{m}^{3}} ).

For m odd, ψ_{m}^{2} has zeroes exactly at the m division points of E and, being of degree m^{2} − 1, we see that the degree of [m] is m^{2}. (Do not forget that [m]O = O.)

Let End_{k}E denote the ring of endomorphisms of E defined over k. If k̄ denotes the algebraic closure of k, the above considerations show that Endk̄E ⊇ Z. If k has characteristic zero, it is known that Endk̄E = Z or is an order in an imaginary quadratic field K = Q(\sqrt{−d}). If Endk̄E ≠ Z, then E is said to have complex multiplication (CM) by an order in K (or more briefly, by K).

If E is defined over Q, and has CM by K, then necessarily K has class number 1, so is one of the nine fields, K = Q(\sqrt{−d}) with

d = 1, 2, 3, 7, 11, 19, 43, 67, 163.

Up to isomorphism over Q̄, there are only thirteen elliptic curves with CM by an order in one of these fields. Nine of these isomorphism classes of curves have CM by the full ring of integers and four others have

K = Q(\sqrt{−1}), Q(\sqrt{−3}), Q(\sqrt{−7}), with End E = Z + 2O_{K},
K = Q(\sqrt{−3}) with End E = Z + 3O_{K}.

Each class, of course, contains infinitely many curves. For example j = 1728 gives all the curves E : y^{2} = x^{3} + Dx.

§3 THE TEST.

Let E be an elliptic curve defined over Q given by the Weierstrass normal form

E : y^{2} = x^{3} + ax + b, Δ = −16(4a^{3} + 27b^{2}) ≠ 0,

with a, b ∈ Z. Assume, that E has CM by an order in K = Q(\sqrt{−d}), an imaginary quadratic extension of Q, and a rational point of infinite order. By making a suitable transformation of the curve, we can assume without loss that our point of infinite order has integral co-ordinates. This is not essential but makes the subsequent discussion free from the annoying exclusion of a finite set of primes that do not necessarily come from primes for which E has bad reduction.

For any prime p and (p, 6Δ) = 1), it makes sense to consider E as an elliptic curve over F̄_{p}. If E(F_{p}) is the group of F_{p} rational points, then

#E(F_{p}) = p + 1 − a_{p}, |a_{p}| ≤ 2\sqrt{p}.

Also, as E is a CM curve, a_{p} = 0 roughly half the time, specifically according to

\{ \begin{matrix}if p is inert in K, then a_{p} = 0, \\ if p is split in K, then a_{p} = tr(uπ_{p}). \end{matrix}

Here π_{p}π̄_{p} = p, and u is one of the finitely many units in K.

We would like to view the fact that |E(F_{p})| = p + 1 whenever p is inert, as analogous to the criterion used in the Fermat test that the order of the multiplicative subgroup of F_{p} is p − 1. Since Z/nZ is not a field for composite n, it is more convenient to use the division polynomials. Let p be an inert prime, (p, 6Δ) = 1. Then #E(F_{p}) = p + 1, and

(3.1)  ψ_{p+1}(P) ≡ 0 (mod p),  for any P ∈ E(Z).

This calculation can be carried out for any n, prime or not. Accordingly, Gordon [6] fixes a point P ∈ Z^{2} in E(Q) of infinite order and tests:

Given n with (n, 6Δ) = 1 and (\frac{−d}{n}) = −1, check whether or not

(3.2)  ψ_{n+1}(P) ≡ 0 (mod n).

If so, and n is composite, we call n an elliptic pseudoprime.(epsp)

So one has a primality test that is analogous to the Fermat test in classical number theory. An obvious generalization is to test a given n with more than one point. Let us fix P_{1}, …, P_{r}, independent points of infinite order and test for a given n as in (3.2) with each of these points. As before, we may assume, without loss of generality, that the points are integral by passing to an isomorphic curve via a suitable transformation. False witnesses to this test may be called generalized elliptic pseudoprimes.

One could generalize the test and define analogously strong elliptic pseudoprimes, or Euler elliptic pseudoprimes. The interested reader should look at Gordon [6] and some of the cited articles in his paper, for tests involving non CM curves.

§4 UPPER BOUNDS.

We fix E, an elliptic curve with CM and positive rank. Also suppose we have an independent set {P_{1}, …, P_{r}} with r ≤ rank(E) = r_{E}. Let Γ =< P_{1}, …, P_{r} > and Γ_{p} be the subgroup of E(F_{p}) generated by {P_{1}, …, P_{r}}.

Applying our test with E, we would like to know if it is effective at distinguishing primes from composites. For this to be the case, the number of false witnesses must be small in comparison to the number of primes. Accordingly, denote N(x) to be the number of epsp not exceeding x. Gordon [6] has proved that

N(x) ≪ \frac{x log log x}{(log x)^{2}},

assuming a suitable GRH. This gives a probabilistic primality test using elliptic curves, but only conditionally. We will establish unconditionally, Theorem 1.

N(x) ≪ \frac{x(log log x)^{7/2}}{(log x)^{3/2}} .

For our generalization to higher rank (r_{E} ≥ 2), we establish a stronger upper bound.

Theorem 2. If r ≥ 2 then

N_{Γ}(x) ≪ xR(x)^{−c}

for some c > 0, where

R(x) = exp(\sqrt{log x log log x}).

This is the analogous bound established by Erdös [3] for Fermat pseudoprimes to the base 2, (see (1.1)), and we expect that it can be strengthened to the bound of Pomerance,(see (1.3)) though the generalisation is not immediate.

Remark 4.1. The proofs of both theorems are similar in spirit to Erdös [3] and Gordon [7], but with additional complications due to the fact that for split primes p, |E(F_{p})| ≠ p + 1. The removal of the GRH in theorem 2 is accomplished via a key lemma regarding the order of Γ_{p} for split primes p which simplifies the harder part of the argument. Some difficulty is encountered due to the fact that Γ_{p} may not be cyclic for a given p. However, this difficulty arises in the easier part of the analysis. In the rank 1 case this latter difficulty is not encountered. Nevertheless, the harder part of the argument is simplified to a narrow range by the use of the lemma.

Higher Rank Case : Preliminary Lemmas. Keeping the notation established so far we will need

Lemma 1. The number of primes p for which |Γ_{p}| < y is O(y^{1+ \frac{2}{r}}).

proof. The result is proved using the canonical height pairing of Néron and Tate, and a result counting the number of lattice points contained in a particular r-dimensional ellipsoid. (See Gupta and Ram Murty [8] for a proof of this result.) □

In a similar fashion Gupta and Ram Murty [8] prove what will be our key tool for estimation,

Lemma 2. The number of primes p for which |Γ_{p}| < y and p splits in K is O(y^{1+ \frac{1}{r}}).

As in the Erdös paper [3] establishing the upper bound for Fermat psp in (1.1), we will need the following estimate adapted by Erdös [3] from the work of de Bruijn [2] on the number of n ≤ x composed of primes p > y.

Lemma 3. Let N(p_{1}, …, p_{k}) denote the number of n ≤ x composed of primes from the set {p_{1}, …, p_{k}} of k-distinct primes. Put k^{u} = x. Then, for u < \frac{log x}{log log x}, i.e. k > log x,

N(p_{1}, …, p_{k}) < x exp(−cu log u),

for some c > 0.

proof. See Erdös[3] and de Bruijn [2]

Lemma 4. We may write Γ_{p} = Γ_{p}^{∗} ×U_{p} with Γ_{p}^{∗} cyclic, and, if b | |U_{p}| then b | |Γ_{p}^{∗}|.

proof. The first part is clear since Γ_{p} is a finite abelian group. Being so, S_{q}, the q-Sylow subgroup of Γ_{p}, is unique and Γ_{p} = ∏_{q||Γ_{p}|} S_{q}. Writing

S_{q} = C_{q^{n_{1}}} × ⋯ × C_{q^{n_{k}}} , n_{1} ≥ … ≥ n_{k} ≥ 0,

where C_{q^{n_{i}}} is cyclic of order q^{n_{i}}, (not necessarily unique), we note that n_{1} ≥ … ≥ n_{k} ≥ 0 are uniquely determined. Moreover, k ≤ 2 as the group of q^{n_{1}} division points of E over F̄_{p} is either cyclic or a product of 2 cyclic groups. The lemma follows by setting

Γ_{p}^{∗} = ∏_{q||Γ_{p}|} C_{q^{n_{1}}} , U_{p} = ∏_{q||Γ_{p}|} C_{q^{n_{2}}} . □

We shall say that a group is of type (b, b) (or more briefly, a (b, b) group), if it is isomorphic to

Z/bZ × Z/bZ.

Corollary 1. E(F_{p}) is cyclic if and only if E(F_{p}) does not contain a (b, b) group for every b.

Corollary 2. For x sufficiently large, (1) If |Γ_{p}| ≥ R(x) then |Γ_{p}^{∗}| ≥ \sqrt{R(x)}.

(2) If |Γ_{p}| > x^{1−δ} for some δ > 0, and |U_{p}| < R(x), then |Γ_{p}^{∗}| > x^{1−δ′} for any δ′ > δ.

proof.

(1) By Lemma 4, |Γ_{p}| = |Γ_{p}^{∗}||U_{p}| ≤ |Γ_{p}^{∗}|^{2} from which the result follows.

(2) This follows from the fact that R(x) ≪ x^{ϵ} for any ϵ > 0.

Lemma 4 suggests the need to develop tools to estimate the number of primes p for which E(F_{p}) contains a (b, b) group, b fixed.

Lemma 5. E(F_{p}) contains a (b, b) group b ≠ p if and only if p splits completely in Q(E[b]). (Here, E[b] consists of the b-division points of E(\overline{Q}), and Q(E[b]) is the field obtained by adjoining the x and y coordinates of points P ∈ E[b] to Q.)

proof. See Ram Murty [11].

Let K be any number field. The ray class field belonging to an ideal Q is an abelian extension L of K such that the set of prime ideals of K which split completely in L are precisely those ideals lying in the unit class of the Q ideal class group (i.e those prime ideals which are principal and generated by an element α ≡ 1 (mod q)).

It is well-known that for elliptic curves with CM that K(E[b])/K contains K_{b} the ray class field belonging to bO_{K} where K = Q(\sqrt{−d}). [10]

Lemma 6. Let E an elliptic curve over Q with CM by an order O in K. There is an ideal f, depending only on E, such that

K_{m} ⊂ L_{m} ⊂ K_{fm},

where K_{m}, K_{fm} are the ray class fields belonging to m and fm respectively, and L_{m} = K(E[m]).

proof. See Ram Murty [11]

Coming back down to Q,

Lemma 7. K(E[m]) = Q(E[m]) for any m > 2. (K = Q(\sqrt{−D}))

proof. Clearly, it is enough to show that K ⊂ Q(E[m]). Let τ ∈ Gal (Q̄/Q) fixing Q(E[m]). Suppose that τ does not, however, fix K. Then τ restricted to K is complex conjugation. Let ϕ_{λ} ∈ End(E) be multiplication by λ. Then Gal (Q̄/Q) acts on End(E) as follows: for σ ∈ Gal (Q̄/Q) , σϕ_{λ} = ϕ_{σ(λ)}. Thus, τϕ_{λ} = ϕλ̄. Let x ∈ E[m], then ϕ_{λ}(x) ∈ E[m] since

m(λx) = λ(mx) = 0,

and therefore τ(ϕ_{λ}(x)) = ϕ_{λ}(x) since τ fixes E[m]. On the other hand, ϕ_{λ}(x) = ϕλ̄(x), hence

(ϕ_{λ} − ϕλ̄)(x) = ϕ_{λ−λ̄}(x) = 0.

Thus λ ≡ λ̄ (mod mO_{K}). Let f denote the conductor of O, then as every order O of K is of the form Z + fO_{K}, the above congruence holds in particular for λ = f\sqrt{−D}, whence

2f\sqrt{−D} ≡ 0 (mod mO),

in which case 2f\sqrt{−D} = mbf\sqrt{−D} for some b. We conclude that mb = 2 so m | 2.

As long as m > 2 then τ acts trivially on K, so Q(E[m]) ⊃ K as desired, whence Q(E[m]) = K(E[m]).

Finally, by very elementary means, one proves the useful estimate

Lemma 8. #α ∈ O_{K}, α ∉ Z, and Nα ≤ x, such that α ≡ 1 (mod mO_{K}) is

≪ \frac{x}{m^{2}} + \frac{\sqrt{x}}{m}.

(Here Nα is the norm of α. )

proof. Let 1, ω be an integral basis of O_{K}. Then, α = a + bω for some a, b, ∈ Z. Since α ≡ 1 (mod mO_{K}), a − 1 = mc and b = md for some c, d ∈ Z. As N(α) ≤ x, a^{2} + Db^{2} ≤ x or (a + b/2)^{2} + Db^{2}/4 ≤ x, depending on the congruence condition satisfied by D (mod 4). We deal with the former case, the latter one being similar. Thus, |a| ≤ \sqrt{x}. Now a ≡ 1 (mod m) implies that there are

2\frac{\sqrt{x}}{m} + 1

possibilities for a. The number of possibilities for b is ≤ 2\sqrt{x}/m as b ≠ 0. Combining these estimates gives the final result.

We are now ready to prove Theorem 2.

§5 PROOF OF THEOREM 2.

Keeping the notation of the preliminary lemmas, let R(x) = exp(\sqrt{log xlog log x}). Let us write any epsp n ≤ x as n = sL where

\{ \begin{matrix}p | s ⇔ |Γ_{p}| ≤ R(x), \\ p | L ⇔ |Γ_{p}| > R(x). \end{matrix}

We will split the epsp into 4 classes

(1) L = 1.

(2) There is an inert prime p | L.

(3) There is a split prime p | L with |Γ_{p}| < x^{1−δ}.

(4) L > 1 and for all p | L, p splits in K and |Γ_{p}| ≥ x^{1−δ}.

δ > 0 will be chosen later.

We should remark that the above list exhausts all the cases as only finitely many primes p ramify in K. Thus there are only finitely many corresponding Γ_{p}. For large x, therefore, all such Γ_{p} will have |Γ_{p}| ≤ R(x), hence L will then contain only (possibly) split or inert factors.

By Lemma 1 any epsp in class 1 will have at most R(x)^{1+ \frac{2}{r}} prime divisors. Applying Lemma 3 with k = R(x)^{1+ \frac{2}{r}} , so that u = \frac{r}{r+2}(\frac{log x}{log log x})^{1/2}, we find that the number of epsp in class 1 is at most

(5.1)  \frac{x}{R(x)^{c_{1}}} ,  for some c_{1} > 0.

If n is an epsp with p | n then by lemma 4, there is an element of Γ_{p} of order |Γ_{p}^{∗}|. Hence,

(5.2)  \{ \begin{matrix}n ≡ 0 (mod p), \\ n ≡ −1 (mod |Γ_{p}^{∗}|). \end{matrix}

Let us note that (5.2)implies that (p, |Γ_{p}^{∗}|) = 1. So by the Chinese remainder theorem, the number of such n satisfying (5.2) is at most

(5.3)  1 + \frac{x}{p|Γ_{p}^{∗}|}.

However, in class 2, n has an inert prime divisor p which itself satisfies the congruences in (5.2) because |Γ_{p}||p + 1. We remove the prime from our count as we are enumerating composite numbers which pass the pseudoprime test. Therefore, we get at most

\frac{x}{p|Γ_{p}^{∗}|}

composite solutions since (p, |Γ_{p}|) = 1. The number of epsp therefore in class 2 does not exceed

(5.4)

∑_{\begin{matrix}p<x \\ |Γ_{p}|>R(x) \end{matrix}} \frac{x}{p|Γ_{p}^{∗}|} ≪ ∑_{\begin{matrix}p<x \\ |Γ_{p}^{∗}|≥\sqrt{R(x)} \end{matrix}} \frac{x}{p|Γ_{p}^{∗}|} ≪ \frac{x}{\sqrt{R(x)}} ∑_{p<x} \frac{1}{p} ≪ \frac{x log log x}{\sqrt{R(x)}} ≪ \frac{x}{R(x)^{1/4}} ,

where the first inequality is from Corollary 2(a) to Lemma 1.

If n is in class 3, let

(5.5)  p | n, p split in K, R(x) < |Γ_{p}| < x^{1−δ}.

Then using (5.3), the number of epsp in class 3 is at most,

\begin{matrix}∑ & ′ \\ p<x \end{matrix}(1 + \frac{x}{p|Γ_{p}^{∗}|}) ≪ ^{∑′} 1 +^{∑′} \frac{x}{p|Γ_{p}^{∗}|},

where the ^{∑′} indicates the range of summation in (5.5).

The second sum may be estimated as before in (5.4), using Corollary 2 of Lemma 1,

\begin{matrix}∑ & ′ \\ p<x \end{matrix} \frac{x}{p|Γ_{p}^{∗}|} ≪ \frac{x}{R(x)^{1/4}} .

For the first sum, we use Lemma 2. The number of primes p which split in K for which |Γ_{p}| < x^{1−δ} is ≪ x^{(1−δ)(1+1/r)}. Hence

(5.6)  ^{∑′} 1 ≪ x^{(1−δ)(1+1/r)} ≪ x^{1−3η/2},

by writing δ = 1/3 + η, and we will choose η > 0 later. (Since r ≥ 2, any δ > 1/3 works.)

If n is in class 4, then every p dividing n with |Γ_{p}| > R(x), splits in K and has |Γ_{p}| > x^{1−δ}. Using Lemma 4, Corollary 2(a), let us consider 2 subclasses:

(a) The largest (b, b) group ⊂ Γ_{p} (if any) has b ≤ \sqrt{R(x)}.

(b) The largest (b, b) group ⊂ Γ_{p} has b > \sqrt{R(x)}. In (a), |Γ_{p}^{∗}| > x^{1−δ′} for any δ′ > δ by Corollary 2(b) of Lemma 4. As in (5.4) the

number of epsp in this class is at most,

(5.7)  ∑_{\begin{matrix}|Γ_{p}^{∗}|>x^{1−δ′} \\ p split ≤x \end{matrix}}(1 + \frac{x}{p|Γ_{p}^{∗}|}) ≪ ^{∑′′} 1 +^{∑′′} \frac{x}{p|Γ_{p}^{∗}|},

where the double dash indicates the specified condition on Γ_{p}^{∗} and p. The second sum is

(5.8)  ^{∑′′} \frac{x}{p|Γ_{p}^{∗}|} ≪ \frac{x}{R(x)^{1/4}}

as usual. (In fact ≪ x^{1−δ′}.)

In the first sum, we may assume that p > x^{1−ϵ}, where ϵ > 0 to be chosen later. This is because p ≤ x^{1−ϵ} implies

(5.9)  \begin{matrix}∑ & ′′ \\ p≤x^{1−ϵ} \end{matrix} 1 ≪ x^{1−ϵ}.

But now, for p > x^{1−ϵ}, a simple argument shows that the corresponding sum is void for large x. Indeed

p + 1 − a_{p} ≡ 0 (mod |Γ_{p}^{∗}|),
n + 1 ≡ 0 (mod |Γ_{p}^{∗}|),
p | n, n = mp,

thus

mp + 1 ≡ m(a_{p} − 1) + 1 ≡ 0 (mod |Γ_{p}^{∗}|),

so m(a_{p} − 1) + 1 > |Γ_{p}^{∗}| > x^{1−δ′}, whence m ≫ x^{1/2−δ′} as |a_{p}| ≤ 2\sqrt{p}.

But then

(5.10)  n = mp ≫ x^{1/2−δ′}x^{1−ϵ} = x^{3/2−δ′−ϵ}.

Recall that we may choose η and δ′ > 0 freely so that δ′ > δ = 1/3 + η. Choosing ϵ > 0 so that δ′ + ϵ < 1/2, we find from (5.10) that n > x which is a contradiction. It follows that for large x,

(5.11)  \begin{matrix}∑ & ′′ \\ p>x^{1−ϵ} \end{matrix} 1 = 0.

Combining (5.8), (5.9), and (5.11), we conclude that the number of epsp in class 4(a) is ≪ x^{1−δ′}.

(In the rank 1 case we would be forced to choose δ > 1/2, say δ = 1/2 + η, in (5.6). This would make it impossible to choose δ′ > δ and ϵ > 0 so that δ′ +ϵ < 1/2, as was required in (5.10).)

Finally, suppose that n is in class 4(b). Then any prime divisor p with |Γ_{p}| > R(x), splits in K and has |Γ_{p}| > x^{1−δ}. Moreover Γ_{p} contains a (b, b) group with b > \sqrt{R(x)}. By Lemma 5, p splits completely in Q(E[b]). By Lemma 7, p splits completely in K(E[b]). By lemma 6, K(E[b]) ⊇ K_{b}. Hence, if p splits completely in K(E[b]), it splits completely in K_{b}. That is,

p = π_{p}π̄_{p}, π_{p} ≡ 1 (mod bO_{K}).

By Lemma 8, the number of α ∉ Z, α ∈ O_{K} for which α ≡ 1 (mod b) is

≪ \frac{x}{b^{2}} + \frac{\sqrt{x}}{b}.

Therefore the number of epsp in 4(b) is at most

∑′(1 + \frac{x}{p|Γ_{p}^{∗}|}) ≪ ^{∑′} 1 +^{∑′} \frac{x}{p|Γ_{p}^{∗}|} ≪ ^{∑′} 1 + \frac{x}{R(x)^{1/4}}

as usual, where ^{∑′} indicates that the range of summation is:

p < x, p split, |Γ_{p}^{∗}| > x^{1−δ′}, and Γ_{p} ⊃ (b, b) group, b > \sqrt{R(x)}.

But the first sum is

≪ ∑_{\sqrt{R(x)}≤b≤2x}(\frac{x}{b^{2}} + \frac{\sqrt{x}}{b}),

by the remarks above. This is easily estimated to be

(5.12)  ≪ \frac{x}{\sqrt{R(x)}} + \sqrt{x} log x.

Putting all the estimates together (5.1),(5.4),(5.6),(5.9),(5.11) and (5.12), we find that the number of epsp ≤ x is at most xR(x)^{−c} for some c > 0 as desired.

§6 RANK 1 CASE.

During the proof of theorem 2, we remarked that Lemma 2 cannot be applied to as large a range for |Γ_{p}|. Indeed, we were able to estimate the number of elliptic pseudoprimes with a split prime factor p, such that R(x) < |Γ_{p}| < x^{1−δ} provided δ > 1/3. The same argument carries over to the rank 1 case if δ < 1/2. The analysis used in (5.10) however, does not carry over and a more delicate analysis is needed.

We will need the following estimate: Lemma 9.

∑_{y<δ<z} \frac{1}{δ} ≪ \frac{(log log x)^{3/2}}{\sqrt{log x}} ,

where we assume that any p | δ satisfying p > log^{2} x splits in K, and y = x^{1/2} log^{−A} x and z = x^{1/2} log^{A} x, for some fixed A > 0. proof. Since K = Q(\sqrt{−d}), the density of primes which split in K is 1/2. Therefore, by standard analytic number theory, we have that as v → ∞,

∏_{\begin{matrix}q<v \\ q inert in K \end{matrix}}(1 − \frac{1}{q}) ∼ \frac{C_{K}}{\sqrt{log v}} ,

where C_{K} is a constant depending only on K. Using Brun’s sieve [9], we estimate the number C(x; w) of δ ≤ x all of whose prime factors > w split in K. Then, C(x; w) is bounded by

≪ x ∏_{w<q<x^{1/3} q is inert in K} (1 − \frac{1}{q}) ≪ \frac{x\sqrt{log w}}{\sqrt{log x}} .

(See Erdös [4] or Halberstam and Richert[9].)

By partial summation,

∑_{y<δ<z} \frac{1}{δ} ≪ \frac{C(z; w)}{z} + ∫_{y}^{z} \frac{C(t; w)}{t^{2}}dt,

where the summation over δ is as stated in the lemma. With w = log^{2} x and by our choices of y and z, the sum is easily seen to be

≪ \frac{(log log x)^{3/2}}{\sqrt{log x}} . □

Proof of Theorem 1.

To simplify the notation, let e_{p} denote the order of P (mod p). Write as before, any pseudoprime, n ≤ x as n = sL where

\{ \begin{matrix}p | s ⇔ e_{p} ≤ R(x), \\ p | L ⇔ e_{p} > R(x). \end{matrix}

Split the pseudoprimes into 5 classes:

(1) L = 1,

(2) There is an inert prime p | L,

(3) There is a split prime p | L with e_{p} ≤ \sqrt{x} log^{−A} x,

(4) There is a split prime p | L with e_{p} ≥ \sqrt{x} log^{A} x,

(5) L > 1 and all p | L, are split and \sqrt{x} log^{−A} x < e_{p} < \sqrt{x} log^{A} x. Class (1) is identical to the higher rank situation. Lemma 1 provides at most R(x)^{3} prime divisors for n in this class, and Lemma

3 implies at most

(6.0)  \frac{x}{R(x)^{c_{1}}}

such n, for some c_{1} > 0.

Class (2) is as before: If n is a pseudoprime, and p | n then

(6.1)  \{ \begin{matrix}n ≡ 0 (mod p), \\ n + 1 ≡ 0 (mod e_{p}), \\ (p, e_{p}) = 1, \end{matrix}

and the number of solutions to (6.1) is at most

(6.2)  \frac{x}{pe_{p}} + 1.

But when n is in class (2), there is a p inert dividing n which is, itself, a solution of (6.1). Hence the number of composite solutions to (6.1) is at most \frac{x}{pe_{p}} . Therefore the number of pseudoprimes in this class does not exceed

(6.3)  ∑_{\begin{matrix}p<x \\ e_{p}>R(x) \end{matrix}} \frac{x}{pe_{p}} ≪ xR(x)^{−1/2}.

These two classes are therefore treated as in Gordon [6].

For class (3), we estimate

∑′(1 + \frac{x}{pe_{p}}) ≪ ^{∑′} 1 +^{∑′} \frac{x}{pe_{p}} ,

where ^{∑′} means the range of summation:

p < x, p split in K, and R(x) < e_{p} ≤ \sqrt{x} log^{−A} x.

The second sum is

≪ \frac{x}{R(x)^{1/2}} ,

as in (6.3), and the first sum is estimated using Lemma 2, so that

∑′ 1 ≪ \frac{x}{log^{2A} x}.

Therefore, the number of pseudoprimes in this class is at most

(6.4)  \frac{x}{log^{2A} x} + \frac{x}{R(x)^{1/2}} .

For class (4), Γ_{p} =< P > is cyclic, and so we can proceed as in class 4(a) in the proof of the higher rank case. The number of pseudoprimes in this class is at most

∑′(1 + \frac{x}{pe_{p}}) ≪ ^{∑′} 1 +^{∑′} \frac{x}{pe_{p}} ≪ ^{∑′} 1 + \frac{x}{R(x)^{1/2}} ,

as in (6.3), where now ^{∑′} indicates a range of summation:

p < x, p split in K, and e_{p} > \sqrt{x} log^{A} x.

We may assume that p > \frac{3x}{log^{A} x} since

(6.5)  \begin{matrix}∑ & ′ \\ p≤3x log^{−A} x \end{matrix} 1 ≪ \frac{x}{log^{A} x}.

But now for p > \frac{3x}{log^{A} x} we find that ^{∑′} = 0, since (6.1) implies that n = sp, and

s(a_{p} − 1) + 1 > e_{p} > \sqrt{x} log^{A} x,

so that s ≥ \frac{1}{2} log^{A} x using |a_{p}| ≤ 2\sqrt{p}. Therefore n = sp ≥ 3x/2, which is a contradiction.

Thus the number of pseudoprimes in class (4) is at most

(6.6)  \frac{x}{log^{A} x} + \frac{x}{R(x)^{1/2}} .

For n in class (5) we change our strategy a little bit.

Let n be a pseudoprime in this class, with p | L. Again we may assume that p > x log^{−A} x. Let

S = \{p ≤ x : \sqrt{x} log^{−A} x < e_{p} < \sqrt{x} log^{A} x\},

then p ∈ S and is split in K. As e_{p} | n + 1, we may write n + 1 as a product of factors uv, each approximately \sqrt{x}. i.e. up to powers of log. We note that for p split,

e_{p} | p + 1 − a_{p} = (π_{p} − 1)(π̄_{p} − 1),

for some factorization of p in O_{K}. Therefore, if q is inert and q | e_{p}, then q | π_{p} − 1 (and π̄_{p} − 1). But then, by lemma 8, the number of primes p = αᾱ such that α ≡ 1 (mod q) is

≪ \frac{\sqrt{x}}{q} (1 + \frac{\sqrt{x}}{q}) .

If q > log^{2} x then we obtain an estimate of

≪ \frac{x}{log^{2} x} + \sqrt{x} log x

such primes p.

Accordingly, we consider 2 subclasses,

(a) There exists an inert q > log^{2} x dividing e_{p}, or

(b) If q > log^{2} x, and divides e_{p} then q splits in K.

In (a), the above remarks show that the number of elliptic pseudoprimes in this case is

(6.7)  \frac{x}{log^{2} x} + \sqrt{x} log x.

In (b), let

N_{p}(x) = #{n : n is an epsp and p | n},
d′(n; x) = #\{δ : δ | n, \sqrt{x} log^{−A} x < δ < \sqrt{x} log^{A} x,
and if p | δ, and p > log^{2} x then p splits in K}.

Note that if n is in class (b) d′(n+1; x) ≥ 1 because e_{p} is a divisor of n+1 satisfying (b). Therefore, the number of pseudoprimes in this class is at most

(6.8)  \begin{matrix}∑ & ′ \\ p \end{matrix} N_{p}(x) = \begin{matrix}∑ & ′ \\ p \end{matrix} ∑_{\begin{matrix}n=sp \\ e_{p}|n+1 \end{matrix}} 1 ≤ ^{∑′} ; \begin{matrix}p>x log^{−A} x \\ s≤log^{A} x \end{matrix} d′(sp + 1; x),

by the definitions above, where ^{∑′} indicates the range of summation:

p splits, and \sqrt{x} log^{−A} x ≤ e_{p} ≤ \sqrt{x} log^{A} x, and the hypothesis (b).

Interchanging the order of summation, we get

(6.9)  ≤ \begin{matrix}∑ & ′ \\ p,s \end{matrix} ∑_{δ|sp+1} 1 = \begin{matrix}∑ & ′ \\ δ \end{matrix} ∑_{s≤log^{A} x} ∑_{sp≡−1 (mod δ)} 1,

where in the sum, δ satisfies

\sqrt{x} log^{−A} x < δ < \sqrt{x} log^{A} x,

and all prime factors of δ greater than log^{2} x are split in K. If ϕ denotes the Euler function, the innermost sum is, by the Brun-Titchmarsh theorem [9],

≪ \frac{x/s}{ϕ(δ) log (x/sδ)} ≪ \frac{x}{sϕ(δ) log x},

applied to

#p ≤ x, sp + 1 = δt ≤ x so p ≤ x/s.

Thus, the number of elliptic pseudoprimes is

(6.10)  ≪ \begin{matrix}∑ & ′ \\ δ \end{matrix} ∑_{s≤log^{A} x} \frac{x}{sϕ(δ) log x} ≪ \begin{matrix}∑ & ′ \\ δ \end{matrix} \frac{x log log x}{ϕ(δ) log x}.

Since ϕ(δ) ≫ δ/ log log δ, we obtain that this is

≪ \begin{matrix}∑ & ′ \\ δ \end{matrix} \frac{x(log log x)^{2}}{δ log x} .

But then, applying Lemma 9 to the above sum, and noting that \sqrt{x} log^{−A} x < δ < \sqrt{x} log^{A} x, we find that the number of pseudoprimes in this class is

(6.11)  ≪ \frac{x(log log x)^{7/2}}{log^{3/2} x} .

Finally choosing A > 2 we see that our estimates, all together, give

\{#epsp ≤ x\} ≪ \frac{x(log log x)^{7/2}}{log^{3/2} x} ,

as desired.

A slightly more careful analysis might eliminate a part of the log log factor in the numerator.

References

1. J.W.S. Cassels, Arithmetic on an Elliptic Curve, Proc. of London Math. Soc. (1964), 259–296.

2. N.G. de Bruijn, On the number of positive integers ≤ x and free of prime factors > y, Indag. Math. 13 (1951), 50–60.

3. P. Erdös, On Pseudoprimes and Carmichael Numbers, Publ. Math. Debrecen 4 (1956), 201– 206.

4. P. Erdös, On the Converse of Fermat’s Theorem, American Math. Monthly 56 (1949), 623– 624.

5. P. Erdos and Carl Pomerance, On the Number of False Witnesses for a Composite Number, Math. Comp. 46 (1986), 259-279.

6. D.M. Gordon, Pseudoprimes on Elliptic Curves, Math. of Comp (1988), to appear.

7. D.M. Gordon, Private communication (to appear).

8. R. Gupta, and M.Ram Murty, Primitive Points on Elliptic Curves, Compositio Mathematica 58 (1986), 13–44.

9. H. Halbertstam, and H.E. Richert, Sieve Methods, Academic Press, London, 1974.

10. S. Lang, Elliptic Functions, Addison-Wesley, Reading Mass., 1973.

11. M.Ram Murty, On Artin’s Conjecture, Jour. of Number Theory 16 (1983), 147–168.

12. Carl Pomerance, On the Distribution of Pseudoprimes, Math. of Comp. 37 (1981), 587–593.

13. J.H. Silverman, The Arithmetic of Elliptic Curves, Springer-Verlag, New York, 1986.

14. J.T. Tate, The Arithmetic of Elliptic Curves, Inventiones Mathematicae 23 (1974), 171–206.

McGill University, Montréal, Canada