ELLIPTIC PSEUDOPRIMES, II

R. Balasubramanian and M. Ram Murty

1. Introduction. Given an integer n, the problem of determining whether n is prime or not, in the most efficient manner, is fundamental in mathematics. It is still an open problem whether this can be done in polynomial time. The interested reader may consult the work of Adleman and Huang [7] or Goldwasser and Kilian [8] for the current status of the problem.

Fermat’s criterion, namely that if p is prime, then 2^{p−1} ≡ 1( mod p), can be used to test a number n for primality. However, it still may happen that n is composite and

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

For example, for n = 561, (1) is satisfied. Such numbers are called pseudoprimes (to the base 2). If P_{2}(x) denotes the number of such composite numbers n satisfying (1), then Erdös [2] showed that for some positive constants c_{1} and c_{2},

c_{1} log x ≤ P_{2}(x) ≤ x exp (−c_{2}\sqrt{log x log log x}) .

Pomerance [6] improved these bounds to

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

where L(x) = exp (log x log log log x/ log log x) .

Analogous results have been obtained by Erdös, Kiss and Sarkozy [9] for Lucas pseudoprimes.

Recently, elliptic curves have been introduced into the theory of primality testing. Gordon [3], for example, introduced the analogue of the Fermat test (1) above and defined the concept of an elliptic pseudoprime. For instance, let E be an elliptic curve over ℚ with complex multiplication by the Gaussian ring of integers, ℤ[i]. If E has good reduction at p and p ≡ 3( mod 4), then E(𝔽_{p}) has size p + 1. If a is a rational point of infinite order on E, then

(2)  (p + 1)a = 0 in E(𝔽_{p}).

This is an elliptic analogue of (1) and so can be used to formulate a pseudoprimality test for composite numbers n ≡ 3( mod 4). More precisely, let ψ_{n} denote the n-th division polynomial. The equation (2) can be rephrased as

p|ψ_{p+1}(a).

We therefore say that a composite number n is an elliptic pseudoprime for E if

n|ψ_{n+1}(a).

More generally, let E be an elliptic curve over ℚ with complex multiplication by ℚ(\sqrt{−d}). Denote by Δ the discriminant of E. Let us fix a rational point P of infinite order in E(ℚ). (If E has no such points, then we have no test.) A composite number n satisfying

(n, 6Δ) = 1 and (\frac{−d}{n}) = −1

is called an elliptic pseudoprime for E to the base P if

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

Gordon [3] has shown that there are infinitely many elliptic pseudoprimes. Assuming a generalised Riemann hypothesis, he proved [3] that the number of elliptic pseudoprimes up to x is

≪ \frac{x log log x}{log^{2} x}.

I. Miyamoto and M. Ram Murty [5] showed unconditionally that the number of elliptic pseudoprimes up to x is

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

The purpose of this paper is to obtain a substantial improvement of this result, which is still unconditional. We prove:

Theorem. Let E be an elliptic curve over ℚ with complex multiplication. The number N(x) of elliptic pseudoprimes for E which are ≤ x satisfies

N(x) ≤ x exp (−c\sqrt{log x log log x})

for some positive constant c.

This theorem is analogous to the upper bound of Erdös for the number of pseudoprimes to the base 2.

The methods of the present paper emanate from the second author’s previous work [4] and [5]. The substantial improvement is obtained by making one of the estimates of [5] in a different way.

Acknowledgements. This work was done while the authors were in France. The authors would therefore like to thank Institut Henri Poincaré and Université de Paris (Orsay) for their financial assistance. In particular, discussions with M. Waldschmidt and E. Fouvry (mathematical and otherwise) made our stay in Paris very enjoyable.

2. Preliminaries. 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

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 a simpler model of the form:

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 was noticed by Henri Poincaré that one can define an addition law on E for any field k. This makes the set E(k) of k-rational points on E into an abelian group. If k is a global field, that is either an algebraic number field or a function field of transcendence degree one over a finite field, then E(k) is a finitely generated abelian group. This is the classic theorem of Mordell and Weil. For standard facts about elliptic curves, the reader may consult Silverman [10].

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,

{ψ_{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 :

\begin{aligned}ψ_{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{aligned}

and the recursive relation,

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

By setting m = n + 1 above 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

\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

[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}. All of these properties of the division polynomials are contained in Silverman [10].

Let End_{k}E denote the ring of endomorphisms of E defined over k. Since multiplication by m is an endomorphism over k̄, we see that End k̄E ⊇ ℤ. If k has characteristic zero, it is known that End k̄E = ℤ or is an order in an imaginary quadratic field K = ℚ(\sqrt{−d}). If End k̄E ≠ ℤ, then E is said to have complex multiplication (CM) by an order in K (or more briefly, by K).

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

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

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

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

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

Let E be an elliptic curve defined over ℚ 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 = ℚ(\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 of generality 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 𝔽̄_{p}. If E(𝔽_{p}) is the group of 𝔽_{p} rational points, then

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

by a theorem of Hasse. Also, as E is a CM curve, a_{p} = 0 if p does not split in K.

We would like to view the fact that |E(𝔽_{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 𝔽_{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

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

This calculation can be carried out for any n, prime or not. Accordingly, Gordon [3] fixes a point P ∈ E(ℚ) of infinite order and tests: given n with (n, 6Δ) = 1 and (−d/n) = −1 check whether or not

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

If so, and n is composite, we call n an elliptic pseudoprime for E (to the base P).

So one has a pseudo-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. This was done by Miyamoto and Ram Murty [5].

3. Lemmas.

Henceforth, let us fix E and a point P of E(ℚ) of infinite order. As remarked above, by a suitable transformation, we can assume without loss that P has integral co-ordinates. For each prime p, let e_{p} denote the order of P in E(𝔽_{p}).

Keeping the notation established so far we will need

Lemma 1. The number of primes p for which e_{p} < y is O(y^{3}).

Proof. This is the case r = 1 of Lemma 14 in Gupta and Ram Murty [4]. 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.

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

Lemma 2. The number of primes p for which e_{p} < y and p splits in K is O(y^{2}).

We will need the following estimate adapted by Erdös [2] from the work of de Bruijn [1] 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 [2] and de Bruijn [1].

4. Proof of the theorem. We will here consider the case d ≡ 1( mod 4). The analysis for the case d ≡ 2 or 3( mod 4) is similar. Let

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

and let e_{p} denote the order of P in E(𝔽_{p}). If n ≤ x and n is an elliptic pseudoprime for E, write n = sL where

p|s ⟺ e_{p} ≤ R(x)
p|L ⟺ e_{p} > R(x).

We will split the elliptic pseudoprimes into five classes:

(1) L = 1.

(2) There is a prime p inert in K such that p|L.

(3) There is a prime p which splits in K such that p|L and e_{p} ≤ \sqrt{x}/R(x).

(4) There is a prime p which splits in K such that p|L and e_{p} ≥ \sqrt{x}R(x).

(5) L > 1 and for all p|L, p splits in K and \sqrt{x}/R(x) < e_{p} < \sqrt{x}R(x).

We estimate class (1) as follows. Lemma 1 shows that there are at most O(R(x)^{3}) prime divisors for n in this class. Lemma 3 implies that there are at most

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

such n ≤ x for some constant c_{1} > 0. If n is an elliptic pseudoprime in class (2), then there is a prime p|n which is inert in K. Hence,

(∗)  n ≡ 0( mod p) n + 1 ≡ 0( mod e_{p}) (p, e_{p}) = 1.

The number of solutions n ≤ x for the system (∗) is at most

\frac{x}{pe_{p}} + 1.

But the inert prime p itself is a solution of (∗) which should not be counted as a pseudoprime is by definition composite. Hence, the number of composite solutions of (∗) is at most

\frac{x}{pe_{p}} .

Since p|L, we have e_{p} > R(x) and so the number in class (2) does not exceed

∑_{{p<x \atop ep>R(x)}} \frac{x}{pe_{p}} ≪ xR(x)^{−1/2}.

In class (3), we need to estimate

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

where the dash on the summation means p ≤ x, p splits in K, and R(x) < e_{p} < \sqrt{x}/R(x). The last sum is, as before

≪ xR(x)^{−1/2}.

By lemma 2, the penultimate sum is

≪ \frac{x}{R(x)^{2}} .

For class (4), we can suppose that p > 3x/R(x) because otherwise, the penultimate sum above would be

≪ \frac{x}{R(x) log x}.

Now L = p and n = sp together with n + 1 ≡ 0( mod e_{p}) imply

sp + 1 ≡ s(a_{p} − 1) + 1 ≡ 0( mod e_{p}).

This means that

s(a_{p} − 1) + 1 > e_{p} > \sqrt{x}R(x).

Since |a_{p}| ≤ 2\sqrt{x}, we find s ≥ R(x)/2. Therefore, n = sp > 3x/2 > x. Therefore, with our choice of parameters, class (4) is empty.

Thus far, our analysis is similar to [5] except for our choice of parameters. In class (5), we would like to count the composite numbers n ≤ x such that n = sp where p splits in K and e_{p} satisfies

\sqrt{x}/R(x) < e_{p} < \sqrt{x}R(x).

The number of such n does not exceed the number of 4-tuples

(j, r, s, k)

where

r^{2} + ds^{2} = p, j = n/p ≤ R(x), \sqrt{x}/R(x) < k = e_{p} < \sqrt{x}R(x).

We have

e_{p}|j(r^{2} + ds^{2}) + 1,

since j(r^{2} + ds^{2}) + 1 = n + 1. But then, e_{p} divides p + 1 − a_{p} = r^{2} + ds^{2} + 1 − 2r. (Recall that a_{p} = tr(π_{p}) where π_{p}π̄_{p} = p is the factorization of p in K.) Therefore, e_{p} divides j(r^{2} + ds^{2} + 1 − 2r). Hence

e_{p}|j(2r − 1) + 1.

Now fix j and k. Then,

j(2r − 1) + 1 ≡ 0( mod k)

has a unique solution mod k/(k, j). Since p ≤ x, we have r ≤ \sqrt{x}. Hence, the number of solutions r is

\frac{\sqrt{x}}{k}(k, j) + O(1) ≪ R(x)^{2} + O(1).

For each r, the number of solutions s of

r^{2} + ds^{2} + 1 − 2r ≡ 0( mod k)

is bounded by the number of divisors of k which is ≪ x^{ϵ}. As s ≤ \sqrt{x}, the number of possibilities for s is

(\frac{\sqrt{x}}{k} + O(1)) O(x^{ϵ})

solutions. This is ≪ x^{ϵ}. Thus fixing j and k gives only O(x^{ϵ}) solutions for r and s and hence p. Summing over j and k gives a total of

O(x^{1/2+ϵ})

solutions, which is the estimate for the number of elements in class (5). Putting together the estimates from all the classes completes the proof of the theorem.

For the uninitiated, the choice of R(x) may seem arbitrary. However, a careful look at the proof shows that it is constrained by de Bruijn’s theorem. Indeed, if we had worked with a parameter z instead of R(x), the estimates arising from cases (1) and (2) are optimized by the choice of R(x), as is easily checked. Any further improvement in the estimate would therefore have to come from an alternate approach other than through de Bruijn’s theorem.

REFERENCES

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

[2] P. Erdös, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen, 4 (1956) 201-206.

[3] D.M. Gordon, Pseudoprimes on elliptic curves, Math. Comp., 52 (115) (1989) 231-245.

[4] Rajiv Gupta and M.Ram Murty, Primitive points on elliptic curves, Compositio Mathematica 58 (1986) 13-44.

[5] I. Miyamoto and M. Ram Murty, Elliptic pseudoprimes, Math. Comp. 52 (187) (1989) 415-430.

[6] Carl Pomerance, On the distribution of pseudoprimes, Math. Comp., 37 (1981) 587-593.

[7] L.M. Adleman and M.A. Huang, Recognizing primes in random polynomial time, Proc. CRYPTO, 86 (1986) 0-0.

[8] S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, Proc. 18th STOC, Berkeley, (1986) 316-329.

[9] P. Erdös, P. Kiss, and A. Sárközy, A lower bound for the counting function of Lucas pseudoprimes, Math. Comp. (1988).

[10] J. Silverman, Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, Springer-Verlag, New York, 1986.

Institute for Mathematical Sciences, Madras, India and McGill University, Montréal, Canada