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

The above technique can be used to produce an elliptic curve E and a prime
p such that E ( F p ) is a desired group (when such a curve exists). For example,
suppose we want

E ( F p ) Z 2 ⊕ Z 2 ⊕ Z 63 .

We take

N = 252 , p = 271 , p =20 ,

so N = p +1 − a p . We choose

τ = − 1+ √ − 171
2

.

As we'll see below, this choice imposes certain congruence conditions on the
Frobenius map that force E ( F p ) to have the desired form. We computed the
polynomial satisfied by j ( τ ) above. This polynomial has the root 5 mod 271.
Putting this value into the formula (10.4) yields the elliptic curve E given by

y 2 = x 3 +70 x + 137

(mod 271) .

It has 252 points and has complex multiplication by the order
R = Z 1+ √ − 171
2

171 = a p −

of discriminant − 4 p . The characteristic polynomial of the Frobe-

nius endomorphism φ p is

X 2

− 20 X + 271 ,
so φ p corresponds to a root 10 ± √ − 171. The choice of sign is irrelevant
for our purposes (it corresponds to how we choose to identify R with the
endomorphism ring), so we assume
φ p =10+ √ − 171 .

Therefore,

φ p =1+2 4+ 1+ √ −

171

≡ 1(mod R ) .

2

It follows that φ p acts as the identity on points of order 2, so E ( F p )hasa
subgroup isomorphic to Z 2 ⊕ Z 2 .Infact,

E [2] = {∞, (40 , 0) , (56 , 0) , (175 , 0) }⊂E ( F p ) .

Since 252 = 4 × 63,

E ( F p ) Z 2 ⊕ Z 2 ⊕ Z 63 .

If we in stead want the group to be cyclic of order 252, we could use R =

Z [ √ − 171] so that φ p wouldnotbecongruentto1mod2ormod3. Wewould