Mathematische Annalen

Math. Ann. 330, 601–625 (2004)
DOI: 10.1007/s00208-004-0562-x

Cyclicity of elliptic curves modulo p and elliptic curveanalogues of Linnik’s problem
Alina Carmen Cojocaru · M. Ram Murty
Received: 28 July 2003 / Revised version: 11 April 2004 /Published online: 13 July 2004 – © Springer-Verlag 2004
Abstract. Let E be an elliptic curve defined over Q and of conductor N . For a prime p  N wedenote by E the reduction of E modulo p. We obtain an asymptotic formula for the number ofprimes p ≤ x for which E(Fp ) is cyclic, assuming a certain generalized Riemann hypothesis.
The error terms that we get are substantial improvements of earlier work of J-P. Serre and M.
Ram Murty. We also consider the problem of finding the size of the smallest prime p = pE forwhich the group E(Fp ) is cyclic and we show that, under the generalized Riemannhypothesis,
pE = O (log N)4+ε if E is without complex multiplication, and pE = O (log N )2+ε if E
is with complex multiplication, for any 0 < ε < 1.
Mathematics Subject Classification (2000): 11G05, 11N36, 11R45

1. Introduction
Let E be an elliptic curve defined over Q and of conductor N. For a prime p  N
let E be the reduction of E modulo p. This is again an elliptic curve, defined overthe finite field Fp with p elements. Many natural and interesting questions arise
regarding the group E(Fp ) of Fp -rational points of E. The most basic ones areto estimate the size and to find the structure of the group E(Fp ). Other questions
arise as elliptic curve analogues of classical problems and conjectures in number
theory. We will discuss a few such examples in what follows.
First we recall that we have information about the size of E(Fp ). Indeed, if
we write#E(Fp ) = p + 1 − ap
A. C. Cojocaru
Pinceton University, Mathematics Department, 810 Fine Hall, Washington Road, Princeton, NJ
08540, USA (e-mail: cojocaru@math.princeton.edu)
M. R. MurtyDepartment of Mathematics and Statistics, Queen’s University, Kingston, Ontario, K7L 3N6
Canada (e-mail: murty@mast.queensu.ca)
 Research supported in part by an Ontario Graduate Scholarship.
 Research supported in part by an NSERC grant.

602

A. C. Cojocaru, M. R. Murty

for some integer ap , where #S denotes the cardinality of a set S, then the famous
Riemann Hypothesis for E, proven by Hasse in 1933, asserts that√|ap | ≤ 2 p.
We also have information about the structure of E(Fp ). Let Fp denote an algebraic closure of Fp and for a positive integer k let E(Fp )[k] and E(Fp )[k] denotethe groups of Fp - and Fp -rational points of E, respectively, which are annihilated
by k. We see that E(Fp ) is a subgroup of E(Fp )[k] for some positive integer k suchthat #E(Fp )|k, and we recall from classical theory that E(Fp )[k] is isomorphic
to a subgroup of Z/k Z × Z/k Z (see [Si1, p.89]). We deduce that E(Fp ) can be
written as the product of two finite cyclic groups Z/dp Z × Z/dp ep Z for uniquelydetermined positive integers dp , ep , depending on p.
There is some interest in determining when the group E(Fp ) is actually cyclic.
In 1975, I. Borosh, C.J. Moreno and H. Porta calculated the structure of E(Fp )for various primes p and various elliptic curves E defined over Q. They conjectured that for ‘many’ elliptic curves E defined over Q, there are infinitely many
primes p for which E(Fp ) is cyclic (see [BoMoPo, pp. 963–964]). As we willsee (statement (5) below), this prediction is indeed true. In 1976, S. Lang and H.
Trotter formulated an elliptic curve analogue of Artin’s conjecture on primitiveroots (see [LaTr]): let E be an elliptic curve defined over Q, of conductor N andhaving arithmetic rank ≥ 1; let a ∈ E(Q) be a fixed rational point on E of infinite
order; then the density of the primes p  N for which E(Fp ) = a(mod p) exists.
Clearly, showing that the density of the primes p  N for which E(Fp ) is cyclic
exists is a natural subproblem of Lang and Trotter’s conjecture.
With the increasing development of elliptic curve public-key cryptography
initiated by N. Koblitz and V. Miller in the late 1980’s, the problem of determining how often the group E(Fp ) is cyclic acquired yet a new significance. Moreprecisely, certain public-key cryptosystems based on the presumed intractabilityof the discrete logarithm problem can be implemented using the group of pointsof an elliptic curve E defined over a finite field (see [Ko1]). Then one wants thecyclic group generated by a certain point a on E to have order divisible by a large
prime. One way to accomplish this is to choose the elliptic curve E and the finite
field so that the group of points of E has prime order; then the desired condition
holds for any nontrivial point a on E. To find such an elliptic curve, we can startby fixing an elliptic curve E defined over Q (possibly of rank at least 1), thenwe reduce E modulo primes p of good reduction and choose a prime p suchthat #E(Fp ) is prime, or such that the group E(Fp ) is cyclic and generated bya(mod p) for some fixed global point a ∈ E(Q) of infinite order (if such a point
exists). We are naturally led to the above 1976 question of Lang and Trotter onprimitive points, or to the 1988 question of Koblitz of determining the proportionof the primes p for which #E(Fp ) is prime (see [Ko2]). The cyclicity of E(Fp )is a common subproblem of both these questions.

Cyclicity of elliptic curves modulo p and elliptic curve analogues of Linnik’s problem

for

603

The precise goal in this paper is to determine an explicit asymptotic formula(1)
f (x, Q) := # p ≤ x : p  N, E(Fp ) cyclic

and to obtain upper bounds in terms of the conductor N for the smallest primep = pE for which E(Fp ) is cyclic. This latter problem can be viewed as anelliptic curve analogue of Linnik’s question about the size of the least prime in anarithmetic progression (see [Li1] and [Li2]).
In 1976, J-P. Serre adapted Hooley’s conditional proof of Artin’s conjecture[Ho, chapter 3] to obtain an asymptotic formula for the number of primes p ≤ x
for which the group of points modulo p of an elliptic curve is cyclic (see [Se3]or [Mu1, pp. 159–161]). Before stating Serre’s result, let us introduce some morenotation. For any positive integer k let E[k] denote the group of points of E which
are annihilated by k (called the k-division group of E) and let Q(E[k]) be the fieldobtained by adjoining to Q the x- and y-coordinates of the points of E[k] (called
the k-division field of E). Serre showed that if we assume the generalized Riemannhypothesis (denoted GRH) for the Dedekind zeta functions of the division fieldsof E, then, as x → ∞,f (x, Q) = fE li x + error(E, x),
where



(2)

µ(k)
(3)
[Q(E[k]) : Q]k≥1
 x dtdenoting the logarithwith µ(·) denoting the Möbius function and li x = 2 logt
mic integral, and where


x
.
(4)
error(E, x) = olog x
It is not difficult to see that fE is finite and that it is positive if and only if E
has an irrational 2-division point. For clarity and completeness, we will explain
this in detail in Section 6 of the paper.
In 1979 [Mu1, pp. 161–167], R. Murty eliminated the use of GRH in Serre’s
argument for elliptic curves with complex multiplication (denoted CM). His proof
uses class field theoretical properties of CM elliptic curves and the large sieve fornumber fields in the form of a number field version of the Bombieri-Vinogradov
Theorem. In 1987 [Mu2], R. Murty also demonstrated unconditionally the existence of infinitely many primes p for which E(Fp ) is cyclic for certain elliptic
curves E without complex multiplication (denoted non-CM). More precisely, heshowed that for elliptic curves Ea : y 2 = x 2 + 1 (x + a) with a ∈ Q and such
/ Z, the group of points of Ea modulo p isthat its j -invariant jEa satisfies jEa ∈cyclic for any supersingular prime p of Ea . By 1987 results of N. Elkies, there
are infinitely many supersingular primes, hence there are infinitely many primes
p for which Ea (Fp ) is cyclic. In 1990 [GuMu2], R. Gupta and R. Murty showed

fE =

604

A. C. Cojocaru, M. R. Murty

unconditionally that for any elliptic curve E which has an irrational 2-division
point, we havef (x, Q)E

x.
(log x)2(5)

The implied E -constant depends on E. In 2000 [Co1], A.C. Cojocaru showedthat if E is a non-CM elliptic curve, then Serre’s result holds under the assumptionof a quasi-GRH, namely a zero-free region of Re s > 3/4 for the Dedekind zetafunctions of the division fields of E, and with

x log log x.
(6)error(E, x) = ON(log x)2
In 2001 [Co2], she also gave a new simpler unconditional proof for formula (2)in the case of a CM elliptic curve, and obtained
error(E, x) = ONx(log x)(log log log x)

=Ox
log log x·(log x)(log log log x) log log2x

. (7)

N

The implied ON -constants above depend on N, while the O-constant is absolute.
In this paper  we will obtain asymptotic formulae for f (x, Q) with error termsof type ON x δ for some 0 < δ < 1. It will be the first time such error terms are
obtained in such questions. Moreover, we will obtain an explicit dependence ofthe error terms on the conductor N. This feature will allow us to deduce estimates
for the smallest prime p for which E(Fp ) is cyclic.
Before stating the principal results of the paper, let us recall that associatedto an elliptic curve E defined over Q one can define a natural representation
φk : Gal(Q(E[k])/Q) −→ GL2 (Z/k Z), which is easily seen to be injective. A
famous result of Serre (see [Se2]) asserts that if the curve E is non-CM, then there/ SE .
exists a finite set of primes SE such that φl is surjective for any prime l ∈Moreover, if we set A(E) := 2 · 3 · 5 · l∈SE l, where the product is over primes
l, then φk is surjective for any positive integer k coprime to A(E) (see Appendix
of [Co4]). We will refer to A(E) as Serre’s constant associated to E.
The main results of the paper are as follows.
Theorem 1.1. Let E be a non-CM elliptic curve defined over Q and of conductor
N. Let A(E) be Serre’s constant associated to E. Let x ≥ 9.
1. Assuming GRH for the Dedekind zeta functions of the division fields of E, wehave thatf (x, Q) = fE li x + ON x 5/6 (log x)2/3 ,or, more precisely,




 5/6
(log log x)(log(Nx))
2/3
3f (x, Q) = fE li x+O x (log(N x))
A(E) .
+Olog xCyclicity of elliptic curves modulo p and elliptic curve analogues of Linnik’s problem

605

2. Assuming GRH, Artin’s Holomorphy Conjecture (denoted AHC) and a Pair
Correlation Conjecture (denoted PCC) for the L-functions associated to theirreducible characters of the Galois groups of the division fields of E, we havethatf (x, Q) = fE li x + ON x 7/10 (log x)4/5 ,or, more precisely,
f (x, Q) = fE li x + O x 7/10 (log(Nx))4/5 A(E)(log log x)(log(Nx))6/5
3+O
A(E) .
x 1/5 log x
The ON -constants above depend on N , and the O-constants are absolute.
For formulations of AHC and PCC we refer the reader to [Mu5].
Theorem 1.2. Let E be an elliptic curve defined over Q, of conductor N , andwith complex multiplication by the full ring of integers of an imaginary quadratic
field. Let x ≥ 9. Assuming GRH for the Dedekind zeta functions of the division
fields of E, we have thatf (x, Q) = fE li x + O x 3/4 (log(Nx))1/2 .
The implied O-constant is absolute.
Theorem 1.3. Let E be a non-CM elliptic curve defined over Q, of conductor N
and such that Q(E[2]) = Q. Assuming GRH for the Dedekind zeta functions of
the division fields of E, we have that the smallest prime p = pE for which E(Fp )is cyclic has size
pE = Oε (log N )4+ε ,where ε > 0 is any small real number. The implied Oε -constant depends onlyon ε.
Theorem 1.4. Let E be an elliptic curve defined over Q, of conductor N , withcomplex multiplication by the full ring of integers of an imaginary quadratic field,
and such that Q(E[2]) = Q. Assuming GRH for the Dedekind zeta functions of
the division fields of E, we have that the smallest prime p = pE for which E(Fp )is cyclic has size
pE = Oε (log N )2+ε ,where ε > 0 is any small real number. The implied Oε -constant depends onlyon ε.
In what follows, p, q, l will denote rational primes, k a positive integer, and x,
y positive real numbers tending to infinity. Given an elliptic curve E defined over

606

A. C. Cojocaru, M. R. Murty

Q and of conductor N, the prime p will be such that p  N . Given k, φ(k) will
denote the Euler function of k, that is, the number of positive integers ≤ k andcoprime to k, and ν(k) will denote the number of distinct prime factors of k. We
recall that for functions f, g : D ⊆ C −→ R with g taking positive values, wewrite f (x) = O(g(x)), f (x)g(x), or g(x)f (x) if there exists a positive
constant M such that |f (x)| ≤ Mg(x) for any x ∈ D. In case f takes positive
values and f (x)g(x)
f (x), we write f (x) g(x). If D is infinite and g is(x)
= 1, and f (x) = o(g(x))
non-zero on D, we write f (x) ∼ g(x) if limx→∞ fg(x)(x)
if limx→∞ fg(x)= 0. We also make the following convention about the implicit, , and O-constants: whenever we write c , c , c or Oc for some c, we
indicate that the implicit constant M depends on c; whenever we write , ,or O, we indicate that the implicit constant M is absolute.

2. Outline of the proofs
In order to estimate f (x, Q) we use the following important result.
Lemma 2.1. Let E be an elliptic curve defined over Q, of conductor N , and let p
be a prime with p  N . If q = p, then E(Fp ) contains a (q, q)-type subgroup (thatis, a subgroup isomorphic to Z/q Z × Z/q Z) if and only if p splits completely inQ(E[q]). Consequently, E(Fp ) is a cyclic group if and only if p does not split
completely in the q-division field Q(E[q]) of E for any prime q = p.
Proof. First we remark that p is an unramified prime of Q(E[q]), since it iscoprime to qN (see Proposition 3.5 below). Then we letπp : E Fp −→ E Fp , πp (x, y) = x p , y p
be the Frobenius endomorphism and we observe thatKer(πp − 1) = E(Fp ).

(8)Now, E(Fp ) contains a (q, q)-type subgroup if and only if E(Fp )[q] ⊆ E(Fp ),and, from (8), if and only if E(Fp )[q] ⊆ Ker(πp −1). But from classical algebraic
number theory this is equivalent to p splitting completely in Q(E[q])/Q. Thisconcludes the proof of the lemma.
We√also observe that if p ≤ x splits completely in Q(E[k]) for some k, thenk ≤ 2 x. Indeed, on the one hand from Lemma 2.1 we get that k 2 |#E(Fp ). On
√
2
F
)
≤
p
+
1
.
the other hand,√from Hasse’s
inequality
we
know
that
#E(
p
√
Therefore k ≤ x + 1 ≤ 2 x.
By using the above and the inclusion-exclusion principle, we can writef (x, Q) =µ(k)π1 (x, Q(E[k])/Q),
(9)
√
k≤2 x

Cyclicity of elliptic curves modulo p and elliptic curve analogues of Linnik’s problem

607

where for a number field L/Q we use the notation
π1 (x, L/Q) := # {p ≤ x : p splits completely in L/Q} .
From (9) we see that explicit formulae for π1 (x, Q(E[k])/Q) shall give us
an explicit formula for f (x, Q). As will be recalled in Section 3, an explicit
formula for π1 (x, Q(E[k])/Q) is provided by effective versions of the Chebotarev Density Theorem.
However, the best error term in each of√ these formulae isO x 1/2 log(kNx) , and it is clear that by summing over k ≤ 2 x we obtain something bigger than the expected main term fE li x ∼ fE logx x . The usual techniquein analytic number theory for overcoming this difficulty is to split the sum (9)describing f (x, Q) into subsums, some of which are to be handled as suggested
above, the others differently.
In his 1976 treatment of f (x, Q), Serre considered the splittingf (x, Q) =µ(k)π1 (x, Q(E[k])/Q) + O 
π1 (x, Q(E[q])/Q) ,√y<q≤2 xkwhere the sum





k

are ≤ y, the sum

is over square-free positive integers k whose prime divisors√y<q≤2 xis over rational primes q, and y = y(x) is some realparameter which is optimally chosen in each case. This approach emulates the oneused by Hooley in his conditional treatment of Artin’s primitive root conjecture(see chapter 3 of [Ho]). It was also used by the authors for obtaining their earlier
respective results mentioned in Section 1.
A more natural splitting, however, isµ(k)π1 (x, Q(E[k])/Q) +µ(k)π1 (x, Q(E[k])/Q)
f (x, Q) =
k≤y

=:


main

+


error

√
y<k≤2 x(10)

for some parameter y = y(x), to be chosen later. The first sum will provide themain term in the asymptotic formula for f (x, Q) and will be estimated using
effective versions of the Chebotarev Density Theorem. The second sum will provide the error term for f (x, Q) and will be estimated using various sieve methods.
consists not only in the
We emphasize that the novelty in our treatment of f (x, Q)
new splitting (10), but also in the new ways of estimating error . As will be seen,
our approach leads to much better error terms than the ones obtained following
Serre’s (or Hooley’s) approach.
In our estimates we will also be careful in keeping track of the dependence ofthe error terms on the conductor N of E. This feature will allow us to determine

608

A. C. Cojocaru, M. R. Murty

the size of the smallest prime p for which E(Fp ) is cyclic, by comparing the main
term with the error term in the formula for f (x, Q).
3. Preliminaries
3.1. The Chebotarev Density Theorem
The Chebotarev Density Theorem is one of the principal tools needed for proving
the main theorems of this paper. We recall it in what follows.
We let L/Q be a finite Galois extension with group G, of degree nL and discriminant dL . The set of conjugacy classes contained in G is denoted by G̃. We
denote by P (L/Q) the set of rational primes p which ramify in L/Q and setp.
M(L/Q) := (#G)
p∈P (L/Q)

The Chebotarev Density Theorem asserts that, as x → ∞,
1
li x.
#G
In our calculations we need effective versions of this theorem (that is, versions
with explicit error terms). They were first derived by J. Lagarias and A. Odlyzko in
1976 (see [LaOd]), refined by J-P. Serre (see [Se4]), and subsequently improvedby K. Murty, R. Murty and N. Saradha (see [MuMuSa] and [MuMu]).
π1 (x, L/Q) ∼Theorem 3.1. Assuming GRH for the Dedekind zeta function of L, we have that
1
1/2 log |dL |li x + O x+ log x.
π1 (x, L/Q) =#GnL
The implied O-constant is absolute.
This version of the effective Chebotarev Density Theorem is slightly more refined
than a statement given in [LaOd] and is due to Serre (see [Se4, p. 133]).
By assuming, in addition to GRH, Artin’s Holomorphy Conjecture (denoted
AHC) and a Pair Correlation Conjecture (denoted PCC), one can improve theerror term in the above asymptotic formula for π1 (x, L/Q).
Theorem 3.2. Assuming GRH, AHC and PCC for the Artin L-functions attachedto the irreducible characters of G, we have that


1/4
1
#G̃
log(M(L/Q)x) ,li x + O x 1/2
π1 (x, L/Q) =#G#G
where G̃ denotes the set of conjugacy classes of G. The implied O-constant isabsolute.
This result is due to K. Murty and R. Murty (see [MuMu]).

Cyclicity of elliptic curves modulo p and elliptic curve analogues of Linnik’s problem

609

Remark 3.3. If L/Q is an abelian extension, then all the conjugacy classes ofG̃
G = Gal(L/Q) are singleton sets; consequently, the quotient ##G
becomes 1 andthe error terms given in Theorems 3.1 and 3.2 have the same size. Similarly, ifG̃
the quotient ##G
is not ‘very small’, then the error term given in Theorem 3.2 is
not significantly different from the one given in Theorem 3.1. In such a situation
we say that the group G is ‘almost abelian’. The improvement made in Theorem
3.2 is most significant in the case of a non-abelian extension L/Q whose Galois
group G has few conjugacy classes. This will be apparent in our applications of
the Chebotarev Density Theorem in Section 4.
The following result is very helpful in estimating the error terms in the effective
Chebotarev Density Theorem.
Lemma 3.4. Let L/Q be a finite Galois extension of degree nL and discriminant
dL . Using the same notation as before, we have thatlog |dL |≤ log nL +log p.
nLp∈P (L/Q)

For a proof of this lemma we refer the reader to [Se4, p. 130].
3.2. Division fields of elliptic curves
In this section we gather some properties of the division fields Q(E[k]) of anelliptic curve E defined over Q. We writen(k) = [Q(E[k]) : Q]

(11)

for the degree of Q(E[k]) over Q.
Proposition 3.5. Let E be an elliptic curve defined over Q and of conductor N .
Let k be a positive integer.
1. Q(E[k])/Q is a finite Galois extension for which Gal(Q(E[k])/Q) ≤ GL2(Z/k Z). Consequently,



1
1
4
1 − 2 ≤ k4.
1−
n(k) ≤ kqqq|k
2. The ramified primes of Q(E[k])/Q are divisors of kN .
3. The cyclotomic field Q(ζk ) is contained in Q(E[k]). Therefore
φ(k)|n(k),and a rational prime p which splits completely in Q(E[k]) satisfies p ≡1(mod k).

610

A. C. Cojocaru, M. R. Murty

Part 1 of this proposition is a direct consequence of the injectivity of the Galois
representation φk : Gal(Q(E[k])/Q) −→ GL2 (Z/k Z) associated to E; for parts
2 and 3 we refer the reader to [Si1, p. 179 and p. 98].
Proposition 3.5 gives us lower and upper bounds for n(k). We are interested
in determining even more precise estimates for n(k). As will be recalled below,
the size of n(k) differs drastically according to whether E is a CM or a non-CM
curve.
From the celebrated theorem of Serre on the surjectivity of φk we deduce thefollowing (see, for example, Appendix of [Co4]).
Proposition 3.6. Let E be a non-CM elliptic curve defined over Q and let A(E)be Serre’s constant associated to E.
1. For any integer k coprime to A(E) we have that



1
1
4
1− 2
1−
n(k) = kqqq|kand that Q(ζk ) is the maximal abelian extension of Q which is contained inQ(E[k]).
2. Let k be a positive integer. We write it uniquely as k = k1 k2 with k1 composedof primes which are divisors of A(E) and k2 composed of primes which are
coprime to A(E). Thenn(k) ≥ φ(k1 )n(k2 )φ(k)k23 .

Proof. 1. For the first statement of part 1 we refer the reader to [Se1] or [Co4,Appendix]. Now for k coprime to A(E) let us show that Q(ζk ) is the maximalabelian extension contained in Q(E[k]). We have Gal(Lk /Q)  GL2 (Z/k Z) andGal(Q(ζk )/Q)  (Z/k Z)∗ ,GL2 (Z/k Z)
 (Z/k Z)∗ .
SL2 (Z/k Z)

Thus, to prove the desired assertion it suffices to show that the commutator
GL2 (Z/k Z) of GL2 (Z/k Z) is SL2 (Z/k Z). This can be deduced easily by using the Chinese Remainder Theorem to write GL2 (Z/k Z)  q r ||k GL2 (Z/q r Z)
and by using [Br, Theorem 1.4 a, p. 474] that for odd primes q, GL2 (Z/q r Z) =SL2 (Z/q r Z). Since k is coprime to A(E), all its prime factors are odd, and so weare done.
2. Let k1 be a positive integer composed of primes dividing A(E), and k2 a
positive integer composed of primes coprime to A(E). Then (k1 , k2 ) = 1. Usingparts 2 and 3 of Proposition 3.5 and part 1 of our proposition, we obtain thatQ(ζk1 ) ∩ Q(E[k2 ]) = Q. Since Q(E[k1 k2 ]) = Q(E[k1 ])Q(E[k2 ]), we obtainn(k1 k2 ) ≥ [Q(ζk1 ) : Q][Q(E[k2 ]) : Q] = φ(k1 )n(k2 ).

Cyclicity of elliptic curves modulo p and elliptic curve analogues of Linnik’s problem

611

Now we note that part 1 tells us that





1
1
1
4
3
n(k2 ) = # GL2 (Z/k2 Z) = k2
1 − 2 = φ(k2 )k2
1−
1− 2 ,
l
l
l
l|k
l|k
2

2

where the products are over primes l. Thusn(k) = n(k1 k2 ) ≥ φ(k)k23


l

1
1− 2
l


φ(k)k23 .
As explained in [Co3, p. 27] or [Co4], one can refine the proof of [Se4, Lemma
19, p. 198] to deduce upper bounds for A(E).
Proposition 3.7. Let E be a non-CM elliptic curve defined over Q and of conductor N. Let A(E) be Serre’s constant associated to E. We assume GRH for the
Dedekind zeta functions of the division fields of E. Then there exists a positive
constant a, not depending on E, such that
A(E) ≤ a(log N)(log log 2N )3 .
We also recall that, unconditionally, A(E) ε N 1+ε for any ε > 0 (see [Co4])
and, moreover, if E is semistable (that is, N is square-free), then A(E) is anabsolute constant (see [Ma]).
Good estimates for the size of n(k) in the case of a CM elliptic curve can beobtained as a consequence of deep results in the theory of complex multiplication.
Before stating the result, we recall that if OK is the ring of integers of a number field K and if p is a non-zero prime ideal of OK , then the generalized Euler
function of pa for some positive integer a is


1
a
a
,
(p ) = NK/Q (p ) 1 −NK/Q (p)where NK/Q (·) denotes the norm of K over Q; by multiplicativity, one extends
the definition of (·) to all non-zero ideals of OK .
Proposition 3.8. Let E be a CM elliptic curve defined over Q and with complex
multiplication by the full ring of integers OK of an imaginary quadratic field K.
Then for any positive integer k ≥ 3 we haven(k)(k OK ),where (·) denotes the generalized Euler function corresponding to the ring ofintegers OK . In particular,
φ(k)2

n(k)

k2.

612

A. C. Cojocaru, M. R. Murty

Proof. The very first estimate is obtained as a consequence of deep results in thetheory of complex multiplication, as follows. We let h(·) denote the Weber function of E. Then we know that K(jE , h(E[k])) is the ray class field of K modulo
k (see [Si2, Theorem 5.6, p. 135]), where jE denotes the j -invariant of E. We
obtain thathK (k OK ),[K(jE , h(E[k])) : K] =WK
where hK denotes the class number of K and WK the number of roots of unity inK.
Since E is a CM elliptic curve defined over Q, we have that its CM field K is an
imaginary quadratic field of class number 1. This implies that K(jE , h(E[k])) =K(h(E[k])), that WK is bounded absolutely, and, moreover, that
[K(h(E[k])) : K](k OK ).

Now let us recall that E[k]  Z/k Z ⊕ Z/k Z, and so, by choosing two fixed
generators for E[k], we get that [K(E[k]) : K(h(E[k]))] is bounded absolutely.
Putting all these observations together we obtain[Q(E[k]) : Q]

[K(E[k]) : K]

[K(h(E[k])) : K](k OK ).


4. Proof of Theorem 1.1

1. We estimate main by using the effective Chebotarev Density Theorem 3.1,
together with the estimates given in Lemma 3.4 and with parts 1 and 2 of Proposition 3.5. We obtain that=µ(k)π1 (x, Q(E[k])/Q)
main

k≤y


 
 µ(k)
 li x +O x 1/2 log(kNx)
=
n(k)
k≤y
k≤y


 µ(k)
 li x + O yx 1/2 log(Nx) ,
=
n(k)
k≤y

(12)

where n(k) is defined in (11).
√
It remains to estimate error . For each integer a with |a| ≤ 2 x and for eachpositive square-free integer k we let
Sa (k) := p ≤ x : ap = a, p splits completely in Q(E[k])/Q .

Cyclicity of elliptic curves modulo p and elliptic curve analogues of Linnik’s problem

613

Then, using Hasse’s inequality,
 



≤

(13)

error





√
a∈Z√
y<k≤2 xk square-free |a|≤2 x#Sa (k).

We see that by using part 3 of Proposition 3.5 and Lemma 2.1 we have thatp ∈ Sa (k) implies p ≡ 1(mod k) and p + 1 − a ≡ 0(mod k 2 ); hence k|(a − 2).
We then obtain





#Sa (k) ≤1√
a∈Z√y<k≤2 xk square-free |a|≤2 x√y<k≤2 xk square-free+=:
We use elementary estimates to handle
∗

≤


√
y<k≤2 xk square-free√y<k≤2 xk square-free



p≤x
a∈Z√
ap =a
|a|≤2 x2
a =2,k|a−2 k |p+1−a√y<k≤2 xk square-free

∗
∗

+

∗∗

and


a∈Z√
|a|≤2 xa =2,k|a−2

x
+1
k2

1

p≤x
ap =2
k 2 |p−1

(14)

.

∗∗

:

x
+1
k2

√
x
+1
k

x √
x 3/2 x √+ + x log + x;
2
y
y
y
∗∗

≤


√
y<k≤2 xk square-free

x
+1
k2

x √
+ x.
y

Plugging (12)–(16) into (10) gives µ(k)
 li x + O x 1/2 y log(Nx)f (x, Q) = 
n(k)
k≤y

 
 3/2 

√
x
x
x
+
O
.
+O
x
log
+
O
y2
y
y

(15)

(16)

614

A. C. Cojocaru, M. R. Murty
3/2

Now we choose y such that x 1/2 y log(N x) = xy 2 , that is, we choose

y :=
Then


f (x, Q) =  µ(k)n(k)k≤yxlog(N x)

1/3
.





 li x + O x 5/6 (log(Nx))2/3 .

(17)

It remains to analyze the tail µ(k)
 µ(k)
 li x = fE li x −  li x.
n(k)
n(k)
k>y
k≤y
In what follows, k, k1 , and k2 will denote positive square-free integers. We write
each k > y as k = k1 k2 with k1 , k2 uniquely determined such that k1 is composedof primes dividing A(E) and k2 is composed of primes coprime to A(E). Using
part 2 of Proposition 3.6 we get 1  log log k2
 1 
1
1
≤
3
n(k)
φ(k1 )φ(k1 )k24
y φ(k2 )k2
y
k>y
k
k
k square-free
k=k1 k2

k2 > k1

1

1

k2 > k1

 ∞log log y  k13
log log t
dt
y
t4
y3
φ(k1 )
k1
k1
k1


q3
log log y 
1
+
=
y3
q −1
1
φ(k1 )

q|A(E)

log log yA(E)2 exp(ν(A(E)))≤
y3
log log yA(E)3 ,≤
y3where we have also used that φ(t)(17) finally gives

(18)

log t
t
and ν(t) ≤ log. Plugging (18) into
log log t
2



 5/6

(log log x)(log(Nx))
2/3
3f (x, Q) = fE li x + O x (log(N x))
A(E) .
+O
log xThis completes the proof of part 1 of Theorem 1.1.
2. Now we assume that GRH, AHC and PCC hold for the Artin L-functions
attached to the irreducible charactersof the Galois groups of the division fields of
E. Therefore, in estimating main we can use the improved Chebotarev Density

Cyclicity of elliptic curves modulo p and elliptic curve analogues of Linnik’s problem

615

Theorem given by Theorem 3.2. To use this result, we first need to estimate thekG
for all positive square-free integers k ≤ y, where Gk is the image offactor ##Gkk isGal(Q(E[k])/Q) under the Galois representation φk associated to E and G
the set of conjugacy classes of Gk . As before, we write k ≤ y as k = k1 k2 with k1
composed of primes dividing A(E) and k2 composed of primes coprime to A(E).
Since





k ≤ #G
#G
#G
k1
k2 ,


it suffices to estimate #G
k1 and # Gk2 . Using the description of the possible groups
Gq for primes q|A(E) given in [Se2] and [Se4, p. 197], we obtain that



q ≤
#G
#G
#Gq
k12 φ(k1 ),
k1 ≤
q|k1

q|k1

and using the surjectivity of φk2 , we obtain that#G
k2 = # GL2 (Z/k2 Z) = k2 φ(k2 ).
These estimates and the lower bound for #Gk given by part 2 of Proposition 3.6
give usk#G
k12 k2 φ(k)
k12
=
.
#Gk
φ(k)k23
k22
Lemma 3.4 andThen, with M(Lk /Q) defined as in Section 3.1 and estimated using
parts 1 and 2 of Proposition 3.5, we obtain that the error term in main becomesk≤yk square-free
k=k1 k2

O x

1/2

  1/4#Gklog(M(Lk /Q)x)
#Gk




 1/2 
k1
= O x 1/2 log(N x)k1k2 ≤ ky

1 

1/2 
k2

1

 1/2  y 1/2
k1
= O x 1/2 log(N x)k1k 1/2 1/2 ν(A(E)) 1
=O x y 2log(Nx) 1/2 1/2

= O x y A(E) log(Nx) ,



log t
where we have also used that ν(t) ≤ log. Therefore2 µ(k) li x + O x 1/2 y 1/2 A(E) log(Nx) .
=
main
n(k)
k≤y

616

A. C. Cojocaru, M. R. Murty

We point out that the additional conjectures AHC and PCC allowed usto obtainy 1/2 instead of y in the above error terms (compare with (12)). For error and µ(k)
li x we proceed exactly as in part 1. We now choose y such thatthe tail
n(k)
k>y
3/2

x 1/2 y 1/2 log(Nx) = xy 2 , that is, we choose

2/5
x
y :=
.
log(N x)Plugging this into our estimates leads tof (x, Q) = fE li x + O x 7/10 (log(Nx))4/5 A(E)(log log x)(log(Nx))6/5
3+O
A(E) .
x 1/5 log x
This completes the proof of part 2 of Theorem 1.1.
Remark 4.1. If we use the estimate ν(t)log tinstead of the more elementary
log log t

log t
one ν(t) ≤ log, then we can slightly improve our error terms above to obtain
2


 5/6

(log log x)(log(Nx))
2/3
2+ε
A(E)
+ Oε
f (x, Q) = fE li x + O x (log(N x))
log x

under GRH, and
f (x, Q) = fE li x + Oε x 7/10 (log(Nx))4/5 A(E)ε(log log x)(log(Nx))6/5
2+ε
+ Oε
A(E)
x 1/5 log x

under GRH, AHC and PCC, for any 0 < ε < 1.

5. Proof of Theorem 1.2

The sum  main is estimated exactly as in the proof of part 1 of Theorem 1.1. For
the sum error we make two separate analyses according to whether ap = 0 or
ap = 0. We recall that a prime p is said to have ordinary reduction if ap = 0, andsupersingular reduction otherwise. We write≤
π1o (x, Q(E[k])/Q) +π1s (x, Q(E[k])/Q), (19)error√y<k≤2 xk square-free√y<k≤2 xk square-freewhere
π1o (x, Q(E[k])/Q):= #{p ≤ x : p has ordinary reduction and splits completely in Q(E[k])/Q},

Cyclicity of elliptic curves modulo p and elliptic curve analogues of Linnik’s problem617

π1s (x, Q(E[k])/Q):= #{p ≤ x :p has supersingular reduction and splits completely in Q(E[k])/Q}.
Let us estimate√y<k≤2 xk square-free

π1o (x, Q(E[k])/Q).

As explained for example in [Co2] we have that p splits completely in Q(E[k])/Q
π −1
if and only if pk is an algebraic integer, where πp denotes a complex root of the√polynomial X 2 − ap X + p. Since E has complex multiplication by Q( −D) forsome square-free√ D < 0, we obtain that, for primes p of ordinary good reduction,Q(πp ) = Q( −D). Therefore
πp − 1o√π1 (x, Q(E[k])/Q) ≤ # p ≤ x :∈ OQ( −D) ,k√where OQ(√−D) denotes the ring of algebraic integers of Q( −D). We observe√that the norm of πp in Q( −D)/Q is p, hence
πp − 1√# p≤x:∈ OQ( −D) ≤ Sk ,kwhere Sk is Sk1 if −D ≡ 2, 3(mod 4), and Sk2 if −D ≡ 1(mod 4), and
Sk1 := # p ≤ x : p = (αk + 1)2 + Dβ 2 k 2 for some α, β ∈ Z ,


2
α
β2 2
2
k + 1 + D k for some α, β ∈ Z .
Sk := # p ≤ x : p =2
4
For any k, x and 1 ≤ i ≤ 2 we have the elementary estimate
√  √

x
2 x
i
Sk
+1 .
√
k
k D
Therefore√y<k≤2 xk square-free

π1o (x, Q(E[k])/Q)√
y<k≤2 xk square-free

x
√ +
y D
The summation

√y<k≤2 xk square-free





√

√ 
x
x
√ + √
k2 D k D

x log x.
√D

π1s (x, Q(E[k])/Q)

(20)

618

A. C. Cojocaru, M. R. Murty

counts primes p for which k 2 |(p + 1 − ap ) and k|(p − 1). Hence k|2, which is acontradiction with k > y = y(x). This implies that
π1s (x, Q(E[k])/Q) = 0.
(21)√
y<k≤2 xk square-free

Plugging (12) and (19)–(21) into (10) gives




√

 µ(k)
 1/2
xx log xli x +O x y log(N x) +O+O.
f (x, Q) =
√
√
n(k)
y D
D
k≤y
We note that the discriminant D is fixed and, moreover, bounded, as we are in
the CM case. Thus it will play no role in our error terms above.
We now choose y such that x 1/2 y log(N x) = xy , that is, we choose
y :=

x 1/4
.
(log(N x))1/2

This implies thatf (x, Q) =  µ(k)
k≤y

n(k)





 li x + O x 3/4 (log(Nx))1/2 .

 µ(k)

It remains to analyze the tail 

n(k)
k>y


 li x. From Proposition 3.8 we knowthat for any positive square-free integer k ≥ 3, n(k)φ(k)2 . Also, we recallk. Then, by partial summation, we get thatthat as k → ∞, φ(k)log log k µ(k)
k>y

n(k)


k>y
k square-free(log log k)2
k2(log log y)2
.
y

(22)

Using our previous estimates and our choice of y we finally obtain
f (x, Q) = fE li x + O x 3/4 (log(Nx))1/2 .
This completes the proof of Theorem 1.2.
Remark 5.1. We observe that in the CM case the Galois group Gal(Q(E[k])/Q)
is ‘almost abelian’ (in the sense explained in Remark 3.3 of Section 3). Therefore
Theorem 3.2 will not give us better error terms than the ones already obtained byusing Theorem 3.1.

Cyclicity of elliptic curves modulo p and elliptic curve analogues of Linnik’s problem

619

6. Finiteness and positivity of the density fE
Let E be an elliptic curve defined over Q and let fE be its cyclicity constantdefined by (3). We want to justify that fE is finite and that it is positive if and only
if Q(E[2]) = Q.
If E is a non-CM curve, then let A(E) be Serre’s constant associated to E andwrite each positive square-free integer k as k = k1 k2 for some positive square-free
integers uniquely determined such that k1 is composed of prime divisors of A(E)and k2 is coprime to A(E). Then, as in the discussion for (18), we have 
log log k2
1
fE
,
1+
q − 1 k ≥9
k24
q|A(E)
2

which is certainly finite.
If E is a CM curve, then, as in the discussion for (22), we have (log log k)2
fE
,
k2
k≥9
which, again, is finite.
Let us justify that if fE = 0, then Q(E[2]) = Q. We observe that if Q(E[2]) =Q, then the torsion group E(Q)tors of rational points on E contains a subgroup of
the form Z/2Z × Z/2Z. Since for all primes p, except for a finite number of them,
the group E(Q)tors embeds into E(Fp ), we deduce that fE = 0. This observation
also shows the stronger fact that if Q(E[2]) = Q, then there are only finitely
many primes p for which E(Fp ) is cyclic.
The converse of the above statement can be proven immediately by combining(5) with part 1 of Theorem 1.1 and with Theorem 1.2. Indeed, if Q(E[2]) = Q,
then


x
fE li x + OE x θ (log x)δ
,(23)E(log x)2
where θ = 56 , δ = 23 in the non-CM case, and θ = 43 , δ = 21 in the CM case. By
multiplying (23) by log x/x and by taking x → ∞, we obtain fE > 0.
Now let us give unconditional arguments for why fE > 0 if Q(E[2]) = Q(recall that Theorems 1.1 and 1.2 assume GRH). We will consider the non-CM
and CM cases separately. First we will prove a lemma of a more general interest.
Lemma 6.1. Let F = (Lq )q∈P , F  = (Lq )q∈P  be two families of finite Galois
extensions of a number field L, indexed over sets of rational primes P ⊇ P  . For
any square-free integer k composed of primes of P or P  , let Lk := q|k,q∈P Lq
and Lk := q|k,q∈P  Lq , respectively. Also let n(k) := [Lk : L], n (k) := [Lk :L], and µ(k)
 µ(k),, δ(F  ) :=δ(F ) :=n(k)n (k)kk
q|k⇒q∈Pq|k⇒q∈P 

620

A. C. Cojocaru, M. R. Murty

where n(1) = n (1) = 1. We assume that:
1. F covers F  , that is, for any q  ∈ P  there exists q ∈ P such that Lq  ⊆ Lq
and for any q ∈ P there exists q  ∈ P  such that Lq  ⊆ Lq ;


1
1
< ∞,
< ∞.
2.

n(k)
n (k)
k
k
q|k⇒q∈P 

q|k⇒q∈P

Then δ(F ) ≥ δ(F  ).
Proof. Let us consider an arbitrary finite subset Pf of P and take Pf to be thefinite subset of P  such that (Lq )q∈Pf covers (Lq )q∈Pf (in the sense of assumption1). Also, setδPf (F ) :=kq|k⇒q∈Pf

µ(k)
,
n(k)



δPf (F  ) :=kq|k⇒q∈Pfµ(k),n (k)

P (x, F , Pf ) := #{p : NL/Q (p) ≤ x, p does not split completely in Lq ∀q ∈ Pf },P (x, F  , Pf ) := #{p : NL/Q (p) ≤ x, p does not split completely in Lq ∀q ∈ Pf },where x is any positive real number, p are prime ideals of the ring of integers ofL, and NL/Q is the norm of L/Q.
Since Pf covers Pf , we clearly have
P (x, F , Pf ) ≥ P (x, F  , Pf )(24)

for any x. On the other hand, by the inclusion-exclusion principle and theChebotarev Density Theorem we have
 µ(k)x
li x + o,(25)
P (x, F , Pf ) =
n(k)
log x
k
q|k⇒q∈Pf

P (x, F , Pf ) =kq|k⇒q∈Pf



x
µ(k)
li x + o,n (k)
log x(26)

since the sums over k are finite. Combining (24) with (25) and (26), and taking
x → ∞, leads us toδPf (F ) ≥ δPf (F  ).
This inequality holds for any finite subset Pf of P and its corresponding finite
subset Pf of P  . By taking the limit as Pf approaches P we obtain the desired
inequality.
Cyclicity of elliptic curves modulo p and elliptic curve analogues of Linnik’s problem

621

Corollary 6.2. We keep the setting and the hypotheses of Lemma 6.1. If the fields
in F  are mutually independent, then1
δ(F ) ≥
.
1− 
n (q)

q∈P

We will use Corollary 6.2 to show that if E is a non-CM elliptic curve definedover Q and such that Q(E[2]) = Q, then fE > 0. As usual, let N be the conductor of E and A(E) be Serre’s constant associated to E. We define F = (Lq =Q(E[q]))q≥2 . To define F  = (Lq )q , let us first note that [Q(E[2]) : Q] is either
2, 3 or 6, and let K2 be the unique abelian subextension contained in Q(E[2])(note that we may have Q(E[2]) = K2 ). Then we define Lq if q  N A(E),Lq := Q(ζq ) if q|N A(E), q = 2, Q(ζq ) ∩ K2 = Q,
K2 if q = 2 or q|N A(E), q = 2, Q(ζq ) ∩ K2 = Q.
We see that the families F , F  satisfy the hypotheses of Lemma 6.1.
Moreover, from part 2 of Proposition 3.5 and part 1 of Proposition 3.6 we seethat F  consists of mutually independent fields. Therefore
  



1
1
1
fE ≥
> 0.
1−
1−
2
φ(q)
n(q)
q NA(E)q|NA(E)q =2
Q(ζq )∩K2 =Q

The above analysis also shows that
 
fE
1−
q|NA(E)


1
,
q −1

since for q  NA(E) we have that n(q) q 4 , by Serre’s theorem. We can invoke
now Mertens’ theorem [HaWr, p. 351] (or elementary estimates for the Euler
function) to deduce that

 
1
1
.
1−
q −1
log log(NA(E))
q|NA(E)q =2

Then, by Proposition 3.7 we obtain that, under GRH,

fE

1.
log log log N

Similarly, by the unconditional upper bound A(E)that, under no hypothesis,
1fE.
log log N

(27)
ε N

1+ε

for any ε we obtain

622

A. C. Cojocaru, M. R. Murty

Now let us consider the case of a CM elliptic curve E defined over Q andsuch that Q(E[2]) = Q, and let us use again Corollary 6.2 to show that fE > 0.
We let F = (Lq = Q(E[q]))q≥2 , and, as before, we let K2 be the unique abeliansubextension of Q(E[2]). Also let K be the complex multiplication field of E. We
recall that K(E[q]) = Q(E[q]) for any prime q ≥ 3 (see [Mu1, Lemma 6]) and
we observe that since K is a quadratic field and K2 is a cubic or quadratic field,
we have either K2 = K or K2 ∩ K = Q. If K2 = K we take F  = (K2 ) and so1
fE ≥ ,
2and if K2 ∩ K = Q we take F  = (K2 , K) and so1
fE ≥ .
4
This completes the proof of the finiteness and positivity of fE .
Remark 6.3. A careful study of the arguments in [Mu1, pp.161–167] for an unconditional proof of the asymptotic formula (2) in the case of a CM elliptic curve
E defined over Q and of conductor N will lead to error(E, x) = ON (logxx)B
for any sufficiently large positive constant B. By combining this with (5) we candeduce again, unconditionally, that if Q(E[2]) = Q, then fE > 0.
7. Proof of Theorem 1.3
We use the asymptotic formula for f (x, Q) given by part 1 of Theorem 1.1 more
precisely, we compare the main term fE li x ∼ fE logx x with the error terms
(log log x)(log(Nx))
O x 5/6 (log(N x))2/3 and O
A(E)3 .
log x
In doing so, we recall that under the current hypothesis we have A(E) = O (log N )(log log 2N)3 (see Proposition 3.7). Thus the second error term above is(log log x)(log(N x))
36(log N ) (log log 2N ) .
Olog x
To find an upper estimate for the smallest x for which the main term is bigger
than the error terms we can take x = (log N )α for some α, chosen such that(log N )αα(log log N)(log log log N)
and

5

2

(log N ) 6 α (log N + α log log N ) 3(28)

Cyclicity of elliptic curves modulo p and elliptic curve analogues of Linnik’s problem(log N)αα(log log N)(log log log N)

623(log α + log log log N )(log N + α log log N )α log log N× (log N )3 (log log 2N )6 ,(29)

where we have also used the lower bound (27) for the density fE . Inequality (28)gives us α ≥ 56 α + 23 + ε, or, equivalently, α ≥ 4 + ε for any ε > 0, and inequality(29) gives us α ≥ ε + 1 + 3, or, equivalently, α ≥ 4 + ε for any ε > 0. Thus thesmallest x for which the main term is bigger than the error terms isOε (log N )4+ε ,as claimed in the statement of the theorem.
Remark 7.1. The additional hypotheses AHC and PCC do not seem to lead to better estimates for pE following this approach. Also, the slight improvements given
in Remark 4.1 do not lead to better estimates for pE , either.
8. Proof of Theorem 1.4
Similarly to the non-CM case, this result follows easily from Theorem 1.2 bycomparing the main term with the error term. Note that in this case we can use
the absolute lower bound fE ≥ 1/4 in the main term.
9. Final remarks
The high quality of the error terms in Theorems 1.1 and 1.2 leads us to suspectthat the question about the cyclicity of E(Fp ) has a sharp divergence with theclassical primitive root conjecture of Artin. Under GRH, it seems that we can do
no better than obtain an error term of the form
x log log xO(log x)2
in the primitive root problem.
It is possible that a delicate application of the lower bound sieve may lead tounconditional versions of Theorems 1.3 and 1.4. We reserve these investigations
for a future paper. It will suffice for the moment to say that, in the CM case, theavailability of a Bombieri-Vinogradov type theorem should make this hope feasible. As a first step, this would mean re-working the lower bound sieve techniqueand keeping track of the dependence of the error terms on the conductor of theelliptic curve.
Acknowledgements. We would like to thank the referee for helpful comments.

624

A. C. Cojocaru, M. R. Murty

References[BoMoPo] Borosh, I., Moreno, C.J., Porta, H.: Elliptic curves over finite fields II. Math. Comput. 29, 951–964 (1975)[Br]
Brenner, J.: The linear homogeneous group. Ann. Math. 39, 472–493 (1938)[Co1]
Cojocaru, A.C.: On the cyclicity of the group of Fp -rational points of non-CM
elliptic curves. J. Number Theory 96, 335–350 (2002)[Co2]
Cojocaru, A.C.: Cyclicity of CM elliptic curves modulo p. Trans. AMS 355, 2651–
2662 (2003)[Co3]
Cojocaru, A.C.: Cyclicity of elliptic curves modulo p. PhD thesis, Queen’s University, Canada, 2002
[Co4]
Cojocaru, A.C.: On the surjectivity of the Galois representations associated to nonCM elliptic curves. With an Appendix by E. Kani, to appear in Canadian Math.
Bulletin[GuMu1] Gupta, R., Murty, M.R.: Primitive points on elliptic curves. Compositio Math. 58,
13–44 (1986)[GuMu2] Gupta, R., Murty, M.R.: Cyclicity and generation of points modulo p on elliptic
curves. Invent. Math. 101, 225–235 (1990)[HaWr]
Hardy, G.H., Wright, E.M.: An introduction to the theory of numbers. 5th ed.,Oxford University Press, 1979
[Ho]
Hooley, C.: Applications of sieve methods to the theory of numbers. Cambridge
University Press, 1976
[Ko1]
Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48, 203–209 (1987)[Ko2]
Koblitz, N.: Primality of the number of points on an elliptic curve over a finite field.
Pacific J. Math. 131, 157–165 (1988)[LaOd]
Lagarias, J., Odlyzko, A.: Effective versions of the Chebotarev density theorem.
In: Algebraic Number Fields, A. Fröhlich (ed.) New York: Academic Press,1977,
pp. 409–464[LaTr]
Lang, S., Trotter, H.: Primitive points on elliptic curves. Bull. Am. Math. Soc. 83(2),289–292 (1977)[Li1]
Linnik, Y.V.: On the least prime in an arithmetic progression. I. The basic theorem.
Rec. Math. (Mat. Sbornik) N. S. 15(57), 139–178 (1944)[Li2]
Linnik, Y.V.: On the least prime in an arithmetic progression. II. The Deuring-Heilbronn phenomenon. Rec. Math. (Mat. Sbornik) N. S. 15(57), 347–368 (1944)[Ma]
Mazur, B.: Rational isogenies of prime degree. Invent. Math. 44, 129–162 (1978)[Mu1]
Murty, M.R.: On Artin’s conjecture. J. Number Theory 16, 147–168 (1983)[Mu2]
Murty, M.R.: On the supersingular reduction of elliptic curves. Proc. Indian Acad.
Sci. (Math. Sci.) 97(1–3), 247–250 (1987)[Mu3]
Murty, M.R.: Artin’s conjecture for primitive roots. Math. Intelligencer 10, 59–67(1988)[Mu4]
Murty, M.R.: Artin’s conjecture and elliptic analogues. In: Sieve Methods, Exponential Sums and their Applications in Number Theory, G.R.H. Greaves, G. Harman, M.N. Huxley (eds.), Cambridge University Press, 1996, pp. 326–344[Mu5]
Murty, M.R.: An introduction to Artin L-functions, J. Ramanujan Math. Soc. 16,
261–307 (2001)[MuMu]
Murty, M.R., Murty, V.K.: The Chebotarev density theorem and pair correlation ofzeros of Artin L-functions. To appear[MuMuSa] Murty, M.R., Murty, V.K., Saradha, N.: Modular forms and the Chebotarev density
theorem. Am. J. Math. 110, 253–281 (1988)[Se1]
Serre, J-P.: Abelian l-adic representations and elliptic curves. W.A. Benjamin, Inc.,New York, 1968

Cyclicity of elliptic curves modulo p and elliptic curve analogues of Linnik’s problem
[Se2]
[Se3]
[Se4]
[Se5]
[Si1]
[Si2]

625

Serre, J-P.: Propriétés galoisiennes des points d’ordre fini des courbes elliptiques.
Invent. Math. 15, 259–331 (1972)
Serre, J-P.: Résumé des cours de 1977-1978. Annuaire du Collège de France, 67–70(1978)
Serre, J.-P.: Quelques applications du théorème de densité de Chebotarev. Publ.
Math. I.H.E.S., 123–201 (1981)
Serre, J-P.: Collected papers. volume III, Springer Verlag, 1985
Silverman, J.H.: The arithmetic of elliptic curves. Graduate Texts in Mathematics
106, Springer Verlag, New York, 1986
Silverman, J.H.: Advanced topics in the arithmetic of elliptic curves. Graduate Texts
in Mathematics 151, Springer Verlag, New York, 1994