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

where the sum is over pairs ( a, τ ( a )). Note that since χ 2 χ 4 = χ − 1 ,wehave

4

χ 2 a
a − 1

χ 4 1 =

a
a − 1

χ 2 ( a )
χ 2 ( a − 1)

χ 4 ( − 1)
χ 4 ( a − 1)

−

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

Therefore, since χ 2 (2) = χ 4 (2) 2 = χ 4 (4),
J ( χ 2 ,χ 4 )= χ 4 ( − 4) + 2
( a,τ ( a ))

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

≡ χ 4 ( − 4) +
( a,τ ( a ))

2 (by (4.3))

≡ χ 4 ( − 4) + ( p − 3) ≡ χ 4 ( − 4) − 2(mod2+ i ) .

Suppose p ≡ 1 (mod 8). Since g ( p− 1) / 2 ≡− 1(mod p ), we have that − 1isa

fourth power. It is well known that 2 is a square mod p if and only if p ≡± 1
(mod 8) (this is one of the supplementary laws for quadratic reciprocity and
is covered in most elementary number theory texts). Therefore 4 is a fourth
power when p ≡ 1 (mod 8). It follows that χ 4 ( − 4) = 1.

g j Now suppose p ≡ 5(mod8). Then2isnotasquaremod p ,so2 ≡

(mod p )with j odd. Therefore

− 4 ≡ g 2 j +( p− 1) / 2 (mod p ) .

Since 2 j ≡ 2(mod4)and( p − 1) / 2 ≡ 2 (mod 4), it follows that − 4isa

fourth power mod p . Therefore, χ 4 ( − 4) = 1.

In both cases, we obtain J ( χ 2 ,χ 4 ) ≡ χ 4 ( − 4) − 2 ≡− 1(mod2+2 i ).

Since we just proved that χ 4 ( − 4) = 1, the lemma implies that

α = −χ 4 ( − 4 /k ) J ( χ 2 ,χ 4 )= −χ 4 (1 /k ) J ( χ 2 ,χ 4 ) ≡ χ 4 ( k ) 3 (mod 2 + 2 i ) .

LEMMA 4.30
Let α = x + yi ∈ Z [ i ] .

1. If α ≡ 1(mod2+2 i ) ,then x is odd and x + y ≡ 1(mod4) .

2. If α ≡− 1(mod2+2 i ) ,then x is odd and x + y ≡ 3(mod4) .

3. If α ≡±i (mod 2 + 2 i ) ,then x is even.

PROOF Suppose α ≡ 1(mod2+2 i ), so α − 1=( u + iv )(2 + 2 i )forsome

u, v .Since(1 − i )(2 + 2 i )=4,wehave

( x + y − 1) + ( y +1 − x ) i =(1 − i )( α − 1) = 4 u +4 vi.