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

1. Choose a se t of primes S = { 2 , 3 , 5 ,...,L } (with p ∈ S ) such that

∈S > 4 √ q .

2. If =2,wehave a ≡ 0 (mod 2) if and only if gcd( x 3 + Ax + B, x q

−x ) =

1.

3. For each odd prime ∈ S , do the following.

(a) Let q ≡ q (mod )with |q | </ 2.
(b) Compute the x -coordinate x of
( x ,y )= x q 2 ,y q 2 + q ( x, y )mod ψ .

(c) For j =1 , 2 ,..., ( − 1) / 2, do the following.
i. Compute the x -coordinate x j of ( x j ,y j )= j ( x, y ).
ii. If x − x j ≡ 0(mod ψ ), go to step (iii). If not, try the next
value of j (in step (c)). If all values 1 ≤ j ≤ ( − 1) / 2have
been tried, go to step (d).
iii. Compute y and y j .If( y − y j ) /y ≡ 0(mod ψ ), then a ≡ j
(mod ). If not, then a ≡−j (mod ).
(d) If all values 1 ≤ j ≤ ( − 1) / 2 have been tried without success, let
w 2 ≡ q (mod ). If w does not exist, then a ≡ 0(mod ).

(e) If gcd(numerator( x q − x w ) ,ψ )=1,then a ≡ 0(mod ). Other-

wise, compute

gcd(numerator(( y q − y w ) /y ) ,ψ ) .

If this gcd is not 1, then a ≡ 2 w (mod ). Otherwise, a ≡− 2 w

(mod ).
4. Use the knowledge of a (mod )foreach ∈ S to compute a (mod ).
Ch o ose the value of a that satisfies this congruence and such that |a|≤

2 √ q . The number of points in E ( F q )is q +1 − a .

Example 4.13
Let E be the elliptic curve y 2 = x 3 +2 x + 1 mod 19. Then

# E ( F 19 )=19+1 − a.

We want to determine a . We'll show that

⎧
⎨

1(mod )
2(mod )
3(mod .

a ≡

⎩