Introduction to Cryptography with Open-Source Software

Elliptic curves and cryptosystems 305

There are many families of curves for which the orders can be determined

precisely. One simple family is given by curves of the form

y

2

= x

3

+ kx (mod p)

where p = 3 mod 4 and k 6= 0 mod p. The number of points is easily shown

to be p + 1. To show this, write p = 4n + 3, so that (p −1)/2 = 2 n + 1. Then



−1

p



= (−1)

2n+1

= −1 (mod p)

and so −1 is not a quadratic residue modulo p. For the same reason, if x is

a quadratic residue then −x is not, and vice-versa. This means we can list

all the p oints of the curve starting with O and (0, 1). For every other value

x mod p, since (−x)

3

+ k(−x) = −(x

3

+ kx); this means that if ...