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

for some integers t, u, v, w . Dividing the two equations yields
τ = tτ + u

vτ + w .
As in the proof of Theorem 10.2, the two equations in (10.3) yield
( n √ − ( t + w )( n √ − d ) 2 − d )+( tw − uv )=0 .

Therefore, n √ −d is a root of X 2

− ( t + w ) X +( tw − uv )andisalsoarootof
X 2 + n 2 d . If th ese are not the same polynomial, we can subtract them and

find that n √ −d is a root of a polynomial of degree at most 1 with integer
coecients, which is impossible. Therefore the two polynomials are the same,
so

det tu
vw

= tw

uv = n 2 d. −

By Lemma 10.10, there exist M ∈ SL 2 ( Z )and S 1 ∈ S n 2 d such that
tu
vw

= MS 1 .

Then

j ( τ )= j tτ + u
vτ + w

= j ( MS 1 τ )= j ( S 1 τ ) ,

since j ◦ M = j . Therefore,
H n 2 d ( j ( τ )) =
S

( j ( τ ) − j ( Sτ )) = 0 ,

∈ S n 2 d

since j ( τ ) − j ( S 1 τ ) = 0 is one of the factors.
Assume now that d =1. Since n 2 d is not a square, Theorem 10.15 implies
that the highest coe cient of H n 2 d ( X )is ± 1. Changing the sign of H N if
necessary, we find that j ( τ ) is a root of a monic polynomial with integer
coe cients. This means that j ( L )= j ( τ ) is an algebraic integer.

If d =1,then K = Q ( i ). Replace √ − d in the above argument with 1 + i .

The argument works with a minor modification; namely, n (1 + i ) is a root of
X 2

uv =2 n 2 , which is not a square. Therefore,
we can apply Theorem 10.15 to conclude that j ( τ ) is an algebraic integer.
This completes the proof of Theorem 10.9.

2 nX +2 n 2 . This yields tw

− −

10.4 Numerical Examples

Suppose we want to evaluate
x = j 1+ √ − 171
2

.