Cryptography Reference
In-Depth Information
number of
F
q
-isomorphism classes weighted by #Aut(
E
) (see Section 1.4 of Lenstra [
339
]
for discussion and precise definitions). In other words, each
F
q
-isomorphism class of elliptic
curves with
j
(
E
)
1728 contributes less than one to the total. This makes
essentially no difference to the asymptotic statements in Theorem
9.13.1
. The weighted
sum of all
=
0or
j
(
E
)
=
F
p
-isomorphism classes of elliptic curves over
F
p
is
p
.
Theorem 9.13.1
(Proposition 1.9 of Lenstra [
339
] with the improvement of Theorem 2 of
McKee [
372
]) Th
er
e exists a con
st
ant C
1
∈ R
>
0
such that, for any prime p>
3
and any
S
2
√
p,p
2
√
p
]
⊂
[
p
+
1
−
+
1
+
∩ Z
, the weighted s
um
of
F
p
-isomorphism classes of
S is at most C
1
#
S
√
p
log(
p
) log(log(
p
))
.
The
re
exists a co
n
stant C
2
∈ R
>
0
such that, for any prime p>
3
and any S
elliptic curves E/
F
p
with
#
E
(
F
p
)
∈
⊂
[
p
+
−
√
p,p
+
√
p
]
1
+
1
∩ Z
, the weighted sum of
F
p
-isomorphism classes of elliptic curves
2)
√
p/
log(
p
)
.
E/
F
p
with
#
E
(
F
p
)
∈
S is at least C
2
(#
S
−
Lenstra also gave a result about divisibility of the group order by small primes.
Theorem 9.13.2
(Proposition 1.14 of [
339
]) Let p>
3
and l
=
p be primes. Then t
he
O
(
l
√
p
)
weighted sum of all elliptic curves E over
F
p
such that l
|
#
E
(
F
p
)
is p/
(
l
−
1)
+
O
(
l
√
p
)
if p
1(mod
l
)
and pl/
(
l
2
if p
≡
−
1)
+
≡
1(mod
l
)
. (Here the constants in the
O are independent of l and p.)
This result was generalised by Howe [
267
] to count curves with
N
|
#
E
(
F
q
) where
N
is not prime.
For cryptography it is important to determine the probability that a randomly chosen
elliptic curve over
F
q
uniformly at random) is prime.
A conjectural result was given by Galbraith and McKee [
208
].
Conjecture 9.13.3
Let P
1
be the probability that a number within
2
√
p of p
F
q
(i.e., choosing coefficients
a
4
,a
6
∈
+
1
is prime.
Then the probability that an elliptic curve over
F
p
(p prime) has a prime number of points
is asymptotic to c
p
P
1
as p
→∞
, where
1
1
.
3
l>
2
2
1
1
c
p
=
−
+
(
l
−
1)
2
(
l
+
1)(
l
−
2)
l
|
(
p
−
1)
,l>
2
Here the products are over all primes l satisfying the stated conditions.
Galbraith and McKee also give a precise conjecture for the probability that a random
elliptic curve
E
over
is small.
Related problems have also been considered. For example, Koblitz [
310
] studies the
probability that #
E
(
F
p
has #
E
(
F
p
)
=
kr
where
r
is prime and
k
∈ N
as
p
varies. A similar
situation arises in the Sato-Ta
te
distribution; namely, the distribution on [
F
p
) is prime for a fixed elliptic curve
E
over
Q
−
1
,
1] arising
1))
/
(2
√
p
) for a fixed elliptic curve
E
over
from (#
E
(
as
p
varies. We refer to
Murty and Shparlinksi [
401
] for a survey of other results in this area (including discussion
of the Lang-Trotter conjecture).
F
p
)
−
(
p
+
Q
