Elliptic Curves over Finite Fields - Elliptic Curves: Number Theory and Cryptography - page 120

hence 1 + χ 2 ( − 4 /k )= δ . Therefore,

# E ( F p )=# { ( u, v ) ∈ F p × F p | v 2 =( k/ 4) u 4 +1 } + δ
= p +1 − α − α,

where

α = −χ 4 ( − 4 /k ) J ( χ 2 ,χ 4 ) ∈ Z [ i ] .
If we write α = a + bi ,then α + α =2 a . Proposition 4.27 implies that
a 2 + b 2 = p , so we have almost proved Theorem 4.23. It remains to evaluate
a mod 4.
Let x 1 + y 1 i, x 2 + y 2 i ∈ Z [ i ]. We say that

x 1 + y 1 i ≡ x 2 + y 2 i (mod 2 + 2 i )

if

( x 1 − x 2 )+( y 1 − y 2 ) i =( x 3 + y 3 i )(2 + 2 i )
for some x 3 + y 3 i ∈ Z [ i ]. Clearly − 2 i ≡ 2(mod2+2 i ). Since 2 i− 2= i (2+2 i )
and − 2=2+( − 1+ i )(2 + 2 i ), we have

2 i ≡ 2 ≡− 2 ≡− 2 i (mod 2 + 2 i ) .

It follows easily that

2 χ 4 ( a ) ≡ 2(mod2+ i ) (4.3)

for all a .Since p − 1 is a multiple of 4 = (1 − i )(2 + 2 i ), we have p ≡ 1
(mod 2 + 2 i ).

LEMMA 4.29
Let p ≡ 1(mod4) be prime.Then

J ( χ 2 ,χ 4 ) ≡− 1(mod2+ i ) .

Let S = {x ∈ F p

PROOF | x =1 } .Let

x
x − 1 .
It is easy to check that τ ( τ ( x )) = x for all x

τ : S → S, x →

S and that x =2istheonly
value of x such that τ ( x )= x . Put the elements of S , other than 2, into
pairs ( x, τ ( x )). Note that if x is paired with y = τ ( x ), then y is paired with
τ ( y )= τ ( τ ( x )) = x . This divides S into ( p

∈

− 3) / 2 pairs plus the element 2,

which is not in a pair. We have
J ( χ 2 ,χ 4 )=
a

χ 2 ( a ) χ 4 (1 − a )=

=0 , 1

χ 2 ( a ) χ 4 (1

a )+ χ 2 a
a − 1

χ 4 1 ,

2) +
( a,τ ( a ))

a
a − 1

χ 2 (2) χ 4 (1 − − −