Journal de Théorie des Nombres de Bordeaux

Julien Cassaigne

Marion Le Gonidec

Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables

Henryk Iwaniec

Ritabrata Munshi

The circle method and pairs of quadratic forms

Takashi Fukuda

Keiichi Komatsu

Weber’s class number problem in the cyclotomic $\mathbb{Z}_2$-extension of $\mathbb{Q}$, II

Franck Lalande

A propos de la relation galoisienne $x_1=x_2+x_3$

Anthony Flatters

Power values of certain quadratic polynomials

Kenji Okuda

Syouji Yano

A generalization of Voronoï’s Theorem to algebraic lattices

Olivier Ramaré

Eigenvalues in the large sieve inequality, II

J. Garza

M. I. M. Ishak

M. J. Mossinghoff

C. G. Pinner

B. Wiles

Heights of roots of polynomials with odd coefficients

John E. Cremona

Andrew V. Sutherland

John E. CREMONA et Andrew V. SUTHERLAND
On a theorem of Mestre and Schoof
Tome 22, no 2 (2010), p. 353-358.
<http://jtnb.cedram.org/item?id=JTNB_2010__22_2_353_0>
© Université Bordeaux 1, 2010, tous droits réservés.
L’accès aux articles de la revue « Journal de Théorie des Nom-
bres de Bordeaux » (http://jtnb.cedram.org/), implique l’accord
avec les conditions générales d’utilisation (http://jtnb.cedram.
org/legal/). Toute reproduction en tout ou partie cet article sous
quelque forme que ce soit pour tout usage autre que l’utilisation à
fin strictement personnelle du copiste est constitutive d’une infrac-
tion pénale. Toute copie ou impression de ce fichier doit contenir la
présente mention de copyright.
cedram
Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.cedram.org/
Journal de Théorie des Nombres
de Bordeaux 22 (2010), 353-358
On a theorem of Mestre and Schoof
par John E. CREMONA et Andrew V. SUTHERLAND
Résumé. Un théorème bien connu de Mestre et Schoof implique
que la cardinalité d’une courbe elliptique E définie sur un corps
premier Fq peut être déterminée de manière univoque en calculant
les ordres de quelques points sur E et sur sa tordue quadratique, à
condition que q > 229. Nous étendons ce résultat à tous les corps
finis avec q > 49, et tous les corps premiers avec q > 29.
Abstract. A well known theorem of Mestre and Schoof implies
that the order of an elliptic curve E over a prime field Fq can be
uniquely determined by computing the orders of a few points on
E and its quadratic twist, provided that q > 229. We extend this
result to all finite fields with q > 49, and all prime fields with
q > 29.
Let E be an elliptic curve defined over the finite field Fq with q elements.
The number of points on E/Fq, which we simply denote #E, is known to
lie in the Hasse interval:
Hq = [q + 1− 2
√
q, q + 1 + 2√q].
Equivalently, the trace of Frobenius t = q + 1 −#E satisfies |t| ≤ 2√q. A
common strategy to compute #E, when q is not too large, relies on the
fact that the points on E/Fq form an abelian group E(Fq) of order #E.
For any P ∈ E(Fq), the integer #E is a multiple of the order of P , and
the multiples of |P | that lie in Hq can be efficiently determined using a
baby-steps giant-steps search. If there is only one multiple in the interval,
it must be #E; if not, we may try other P ∈ E(Fq) in the hope of uniquely
determining #E. This strategy will eventually succeed if and only if the
group exponent
λ(E) = lcm{|P | : P ∈ E(Fq)}
has a unique multiple in Hq. When this condition holds we expect to deter-
mine #E quite quickly: with just two random points in E(Fq) we already
succeed with probability greater than 6/π2 (see [2, Theorem 8.1]).
Unfortunately, λ(E) need not have a unique multiple in Hq. However,
for prime q we have the following theorem of Mestre, as extended by
Manuscrit reçu le 10 mars 2009.
354 John E. Cremona, Andrew V. Sutherland
Schoof [1, Theorem 3.2]; the result as stated in [1] refers to the order of a
particular point P , but the following is an equivalent statement.
Theorem 1 (Mestre-Schoof). Let q > 229 be prime and E an elliptic curve
over Fq with quadratic twist E′. Either λ(E) or λ(E′) has a unique multiple
in Hq.
The quadratic twist E′ is an elliptic curve defined over Fq that is isomor-
phic to E over the quadratic extension Fq2 , and is easily derived from E.
The orders of the groups E(Fq) and E′(Fq) satisfy #E + #E′ = 2(q + 1).
For prime fields with q > 229, Theorem 1 implies that we may determine
one of #E and #E′ by alternately computing the orders of points on E
and E′, and once we know either #E or #E′, we know both.
Theorem 1 does not hold for q = 229. Since there are counterexamples
whenever q is a square, it does not hold in general for non-prime finite
fields either. The argument in the proof of [1, Theorem 3.2] does not use
the primality of q, but only that q is both large enough and not a square,
so that the Hasse bound on t cannot be attained. If q = r2 is an even power
of a prime, then there are supersingular elliptic curves E over Fq such that
E(Fq) ∼= (Z/(r − 1)Z)2 and E′(Fq) ∼= (Z/(r + 1)Z)2 .
One may easily check that there are at least 5 multiples of r − 1, and at
least 3 multiples of r + 1, in Hq; however for r > 7 (q > 49), the only pair
that sum to 2(q+1) are (r−1)2 and (r+1)2. This resolves the ambiguity in
these cases, leaving a finite number of small exceptions. For example, when
q = 49 there is more than one pair of multiples of 6 and 8 (respectively)
which sum to 2(q + 1) = 100, since 100 = 36 + 64 = 60 + 40.
The preceding observation led to this note, whose purpose is to extend
Theorem 1 to treat all finite fields (not just prime fields) Fq with q > 49,
and all prime fields with q > 29. Specifically, we prove the following:
Theorem 2. Let q /∈ {3, 4, 5, 7, 9, 11, 16, 17, 23, 25, 29, 49} be a prime power,
and let E/Fq be an elliptic curve. Then there is a unique integer t with
|t| ≤ 2√q such that λ(E)|(q + 1− t) and λ(E′)|(q + 1 + t).
Our proof is entirely elementary, relying on just two properties of elliptic
curves over finite fields:
(a) #E = q+1−t and #E′ = q+1+t for some integer t with |t| ≤ 2√q;
(b) E(Fq) ∼= Z/n1Z× Z/n2Z with n1 dividing both n2 and q − 1.
Proofs of (a) and (b) may be found in most standard references, includ-
ing [3]. We note that n2 = λ(E), and n1 = 1 when E(Fq) is cyclic.
Proof of Theorem 2. Let E be an elliptic curve over Fq, and put #E =
mM with M = λ(E), and #E′ = nN with N = λ(E′). Without loss of
generality, we assume a = q + 1 −#E ≥ 0. Taking t = a shows existence,
On a theorem of Mestre and Schoof 355
by (a) and (b) above, so we need only prove that t = a is the unique t
satisfying the conditions stated in the theorem. For any such t we have t ≡
q+1 modM and t ≡ −(q+1) mod N ; hence t lies in an arithmetic sequence
with difference lcm(M,N). We also have |t| ≤ 2√q; thus if lcm(M,N) >
4√q, then t = a is certainly unique.
We now show that lcm(M,N) ≤ 4√q implies q ≤ 1024. We start from
mMnN = (q+ 1− a)(q+ 1 + a) = (q+ 1)2− a2 ≥ (q+ 1)2− 4q = (q− 1)2,
which yields
(0.1) mn ≥ (q − 1)
2
MN
= (q − 1)
2
gcd(M,N)lcm(M,N)
.
Let d = gcd(m,n). Then d2 divides mM +nN = 2(q+ 1), so d|(q+ 1), but
also d|(q − 1), hence d ≤ 2. This implies 2 lcm(M,N) ≥ 2 lcm(m,n) ≥ mn.
We also have gcd(M,N) ≤ gcd(m,n) gcd(M/m,N/n) ≤ 2 gcd(M/m,N/n).
Applying these inequalities to (0.1) we obtain
(0.2) lcm(M,N)2 ≥ (q − 1)
2
4 gcd(M/m,N/n)
.
We now suppose lcm(M,N) ≤ 4√q, for otherwise the theorem holds. We
have nN = q + 1 + a > q, since we assumed a ≥ 0, and N ≤ 4√q implies
that n > √q/4, so N/n < 16. Applying gcd(M/m,N/n) ≤ N/n < 16 to
(0.2) yields
4√q ≥ lcm(M,N) > (q − 1)/8,
which implies that the prime power q is at most 1024.
The cases for q ≤ 1024 are addressed by a program listed in the appen-
dix that outputs the values of q, M = λ(E), and N = λ(E′) for which
exceptions can arise. This yields the set of excluded q and completes the
proof. 
Application. The proof of Theorem 2 suggests an algorithm to com-
pute #E, provided that q is small enough for the orders of randomly chosen
points in E(Fq) to be easily computed. It suffices to determine integers a
andm for which the set S = {x : x ≡ a mod m} contains t = q+1−#E but
no t′ 6= t with |t′| ≤ 2√q. Beginning with m = 1 and a = 0, we compute |P |
for random points P in E(Fq) or E′(Fq), and update a and m to reflect the
fact that t ≡ q+1 mod |P | when P ∈ E(Fq), and t ≡ −(q+1) mod |P | when
P ∈ E′(Fq). The new values of a andmmay be determined via the extended
Euclidean algorithm. When the set S contains a unique t with |t| ≤ 2√q,
we can conclude that #E = q + 1− t (and also that #E′ = q + 1 + t).
The probabilistic algorithm we have described is a Las Vegas algorithm,
that is, its output is always correct and its expected running time is finite.
The correctness of the algorithm follows from property (a). Theorem 2
356 John E. Cremona, Andrew V. Sutherland
ensures that the algorithm can terminate (provided that q is not in the
excluded set), and [2, Theorem 8.2] bounds its expected running time.
An examination of Table 1 reveals that in many cases an ambiguous t′
could be ruled out if λ(E) or λ(E′) were known. For example, when q =
49, the trace t′ = −10 yields #E = 60 and #E′ = 40, so both λ(E)
and λ(E′) are divisible by 5 (and are not 6 or 8). If E has trace −10,
the algorithm above will likely discover this and terminate within a few
iterations. But when the trace of E is 14 (and λ(E) = 6 and λ(E′) =
8), we can never be completely certain that we have ruled out −10 as a
possibility. Thus when an unconditional result is required, we must avoid
q ∈ {3, 4, 5, 7, 9, 11, 16, 17, 23, 25, 29, 49}.
However, when λ(E) and λ(E′) are known we have the following corol-
lary, which extends Proposition 4.19 of [3].
Corollary 1. Let E/Fq be an elliptic curve. Up to isomorphism, the in-
tegers λ(E) and λ(E′) uniquely determine the groups E(Fq) and E′(Fq),
provided that q /∈ {5, 7, 9, 11, 17, 23, 29}. In every case, λ(E) and λ(E′)
uniquely determine the set {E(Fq), E′(Fq)}.
Note that λ(E) and #E together determine E(Fq), by property (b).
To prove the corollary, apply Theorem 1 with a modified version of the
algorithm in the appendix that also requires (q + 1 − t′)/M to divide M
and (q + 1 + t′)/N to divide N .
As a final remark, we note that all the exceptional cases listed in Table 0.1
can be eliminated if the orders of the 2-torsion and 3-torsion subgroups
of E(Fq) are known (these orders may be computed using the division
polynomials). Alternatively, one can simply enumerate the points on E/Fq
to determine #E when q ≤ 49.
Appendix
For a prime power q, we wish to enumerate all M , N , and t such that:
(i) M divides q + 1− t and N divides q + 1 + t, with 0 ≤ t ≤ 2√q.
(ii) (q + 1 − t)/M divides M and q − 1, and (q + 1 + t)/N divides N
and q − 1.
(iii) M divides q + 1 − t′ and N divides q + 1 + t′ for some t′ 6= t with
|t′| ≤ 2√q.
Any exception to Theorem 2 must arise from an elliptic curve E/Fq with
λ(E) = M , λ(E′) = N , and #E = q + 1 − t (or from its twist, but the
cases are symmetric, so we restrict to t ≥ 0). Properties (i) and (ii) follow
from (a) and (b) above, and (iii) implies that t does not uniquely satisfy
the requirements of the theorem.
Algorithm 1 below finds all M , N , and t satisfying (i), (ii), and (iii). For
q ≤ 1024, exceptional cases are found only for the twelve values of q listed
On a theorem of Mestre and Schoof 357
in Theorem 2. Not every case output by Algorithm 1 is actually realized
by an elliptic curve (in fact, all but one of the exceptions fail the condition
that (q + 1− t)/M ≡ (q + 1 + t)/N (mod 2)), but for each combination of
q and t at least one is. An example of each such case is listed in Table 0.1,
where we only list cases with t ≥ 0: for the symmetric cases with t < 0,
change the sign of t and swap M and N .
Algorithm 1. Given a prime power q, output all quadruples of integers
(M,N, t, t′) satisfying (i), (ii), and (iii) above:
for all pairs of integers (M,N) with √q − 1 ≤M,N ≤ 4√q do
for all integers t ∈ [0, 2√q] with M |(q + 1− t) and N |(q + 1 + t) do
Let m = (q + 1− t)/M and n = (q + 1 + t)/N .
if m|M and m|(q − 1) and n|N and n|(q − 1) then
for all integers t′ ∈ [−2√q, 2√q] do
if M |(q + 1− t′) and N |(q + 1 + t′) then
print M,N, t, t′.
end if
end for
end if
end for
end for
q M N t E t′
3 2 2 0 y2 = x3 − x -2,2
4 1 3 4 y2 + y = x3 + α2 -2,1
5 2 4 2 y2 = x3 + x -2
7 2 6 4 y2 = x3 − 1 -2
7 4 4 0 y2 = x3 + 3x -4,4
9 2 4 6 y2 = x3 + α2x -6,-2,2
11 4 8 4 y2 = x3 + x+ 9 -4
11 6 6 0 y2 = x3 + 2x -6,6
16 3 5 8 y2 + y = x3 -7
17 6 12 6 y2 = x3 + x+ 7 -6
23 8 16 8 y2 = x3 + 5x+ 15 -8
25 4 6 10 y2 + y = x3 + α7 -2
29 10 20 10 y2 = x3 + x -10
49 6 8 14 y2 = x3 + α2x -10
Table 0.1. Exceptional Cases with t ≥ 0.
The coefficient α denotes a primitive element of Fq.
References
[1] René Schoof, Counting points on elliptic curves over finite fields. Journal de Théorie des
Nombres de Bordeaux 7 (1995), 219–254.
358 John E. Cremona, Andrew V. Sutherland
[2] Andrew V. Sutherland, Order computations in generic groups. PhD thesis, M.I.T., 2007,
available at http://groups.csail.mit.edu/cis/theses/sutherland-phd.pdf.
[3] Lawrence C. Washington, Elliptic curves: Number theory and cryptography, 2nd ed. CRC
Press, 2008.
John E. Cremona
Mathematics Institute
University of Warwick
Coventry CV4 7AL
UK
E-mail: J.E.Cremona@warwick.ac.uk
URL: http://www.warwick.ac.uk/staff/J.E.Cremona/
Andrew V. Sutherland
Massachusetts Institute of Technology
Department of Mathematics
77 Massachusetts Avenue
Cambridge, MA 02139-4307
USA
E-mail: drew@math.mit.edu
URL: http://math.mit.edu/~drew/


On a theorem of Mestre and Schoof

Maosheng Xiong

The fluctuations in the number of points on a family of curves over a finite field

Not a member yet