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

We can now form the polynomial

( X − j ( τ 1 ))( X − j ( τ 2 ))( X − j ( τ 3 ))( X − j ( τ 4 ))
= X 4 + 694282057876537344 X 3 + 472103267541360574464 X 2
+8391550371275812148084736 X − 1311901521779155773721411584 .

Since we are working with decimals, the numerical coe cients we obtain are
not exact integers. But, since the roots j ( τ k ) are a complete set of Galois
conjugate algebraic integers, it follows that the coe cients are true integers.
Therefore, if the computations are done with enough accuracy, we can round
off to obtain the above polynomial.
We now describe the general situation.

x + y √ − d

If we start with τ 0 = ,

z

then we can use a matrix in SL 2 ( Z )tomove τ 0 to τ 1 ∈F , and we have

j ( τ 0 )= j ( τ 1 ). Therefore, let's assume τ 0 ∈F . Find integers a, b, c such that

aτ 0 + bτ 0 + c =0

and a> 0, gcd( a, b, c ) = 1. Let b 2 − 4 ac = −D . Now repeat the procedure used

above, with D in place of 171, and obtain values τ 1 ,...,τ h . The polynomial
satisfied by j ( τ 0 )= j ( τ 1 )is

r

( X − j ( τ k )) ∈ Z [ X ] .

k =1

The above techniques can be used to find elliptic curves over finite fields
with given orders. For example, suppose we want an elliptic curve E over F p ,
for some prime p , such that

N =# E ( F p ) = 54323

( N is a prime). Because of Hasse's theorem, we must have p fairly close to N .
Thestrategyistochooseaprime p ,thenlet a p = p +1 D = a p − 4 p .

We then find the polynomial P ( X ) whose roots are the j -invariants of elliptic
curves with complex multiplication by the order R of discriminant

− N and −

D .Find
arootof P ( X )mod p . Such a root will be the j -invariant of an elliptic curve
E mod p that has complex multiplication by R .
The roots of

−

X 2 − a p X + p =0

lie in R (since a p − 4 p = −D ) and therefore correspond to endomorphisms of
E . It can be shown that one of these endomorphisms is the Frobenius map (up
to sign; see below). Therefore, we have found the characteristic polynomial
of the Frobenius map. It follows that

# E ( F p )= p +1 − a p = N,