Complex Multiplication - Elliptic Curves: Number Theory and Cryptography - page 333

as desired. There is a slight complication caused by the fact that we might
endupwith a p in place of a p . We'll discuss this below.

In order to keep the number of τ k 's small, we want D , in th e above notation,
to be small. This means that we should have a p near

−

2 √ p . A choice that ±

works well for us is

p = 54787 , p = 465 , D = 2923 .

There are six values τ k , corresponding to the polynomials aX 2 + bX + c with

( a, b, c )=(1 , 1 , 731) , (17 , ± 1 , 43) , (11 , ± 5 , 67) , (29 , 21 , 29) .

We obtain a polynomial P ( X ) of degree 6 with integer coe cients, as above.
Oneoftherootsof P ( X )mod p is j = 46514. Recall (see Section 2.7) that

3 j
1728

2 j
1728

y 2 = x 3 +

j x +

(10.4)

− − j

is an elliptic curve E 1 with j -invariant equal to j . In our case, we obtain

y 2 = x 3 + 10784 x + 43714 (mod 54787) .

The point Q =(1 , 36185) lies on E 1 . However, we find that

54323 Q = ∞, 55253 Q = ∞.

Since

55253 = p +1+465 ,

we discover that we have obtained a curve E 1 with a p = − 465 instead of a p =
465. This curve has complex multiplication by the order R of discriminant
− D = a p − 4 p , so the sign of a p is irrelevant for D ), so it is

natural for it to appear. To obtain the desired curve, we twist by a quadratic
nonresidue mod p (see Exercise 4.10). A quick computation shows that 2 is
not a square mod p ,sowelookatthecurve E defined by

D (note that −

y 2 = x 3 +4 · 10784 x +8 · 43714

(mod 54787) .

This has N points mod p . Just to be sure, we can compute

54323 (3 , 38039) = ∞.

Since 54323 is prime, we find that 54323 divides the number of points in
E ( F p ). But

54323 >p +1+2 √ p,

2 ·

so Hasse's theorem implies that

# E ( F p ) = 54323 .