Polynomial $m(x,y ) is called the division polynomial of order m. As we
consider the curve reduced modulo p , the coefficients of all polynomials $
are also reduced modulo p . With the aid of the above scheme the division
polynomial of order m can be computed for O(1ogm) steps (the reader not
familiar with polynomial arithmetic may consult [Knuth (1981)l). Notice
that under an odd m, polynomials $m depend on only one variable x since
the other variable y enters only in even powers and y 2 is replaced by the
right side of the curve equation (6.10). Notice also that the polynomials of
the “second layer” ($zm, &,+I) include the products of 4 polynomials of
the “first layer” (from $rn2 to $,+p), therefore, the degree of polynomial
$m grows as O(m2).
A complex point P on curve E is called the torsion point of order m if
=
[m]P 0. Due to (6.25) it is quite obvious that a point P = ( x , y ) is a
torsion point of order m if and only if $m(x,y ) = 0.
The idea of Schoof™s algorithm is to search for solutions of Eq. (6.24)
(with respect to t ) over the sets of torsion points of small orders with
subsequent determination of the general solution. For torsion point of order
Basics of Contemporary Cryptography f o r I T Practitioners
104
m the factors are reduced modulo m and polynomials reduced modulo I),,
so Eq. (6.24) takes the form
+ (6.26)
( ˜ p ˜ , y p ˜ [ P ˜ I ( x ,= [trn1(xp,yp)m
Y)
)m
p mod m, t , = t mod m , ( xk ,y k,) = ( x k mod ,,
$
where p , y k mod
=
+ a x + b.
besides, x and y are linked by the curve equation y 2 = x3
$m),
According to the Hasse theorem
It1 I 2 f i . (6.27)
Let us take for the values of m prime numbers up to mmaxsuch that
n m>4fi. (6.28)
m prime
21mImmax
Then having obtained t , we shall uniquely determine the trace of Frobe
nius t satisfying (6.27) by Chinese Remainder Theorem (see [Knuth (1981);
Menezes et al. (1996)l).
Consider briefly the method of solving Eq. (6.26) for the case m >
2. First compute the polynomial I)m. Since m is odd, I = I),(x). ),
(Further on, all operations with polynomials are carried out modulo ,, the $
power of y is reduced to 1 by the curve equation, coefficients are computed
modulo p.) Compute the polynomials xp, yP, zP2, yP2 using the same
exponentiation algorithm as for integers. By (6.25) compute Q = [p,](x, y)
and using the point addition formulas find in symbolic form the composition
+
2 2
R = ( x p ,yp ,) Q. If R = 0 then t , = 0. Otherwise, in order to
find t , compute the xcoordinates of points P = [7](xP,yP), for all r ,
0 < r < m. For each r we must verify the equality between X R and x p . To
do that we represent the difference of xcoordinates in the form X R  z p =
u ( x ) y v ( x ) = 0. Take from this y = u ( x ) / z ) ( x )substitute it in the curve
,
equation and obtain some polynomial h,(x) = 0. If h, mod I # 0 then ),
X R and x p are different and we must try another value of T. Otherwise,
if X R = x p then compute the ycoordinate of point P and, by similar
techniques, transform the difference y˜  y p in a polynomial h y ( x )= 0. If
hy mod I = 0 then t , = r , otherwise t , = r mod m.
)
,
When m = 2, $2 = y and the difficulty arises with computation of
x p mod y . But here one simple observation helps. Since we exclude singu
lar curves, our curve may have either one or three intersections with the
horizontal axis. All other points appear in pairs ( x ,y ) , ( x ,y) and there
is one point at infinity 0. So the number of points on the curve is even or
Elliptic Curve Cryptosystems 105
+
+
odd depending on whether X3 a X b can be factored modulo p or not.
A simple criterion is known for making such a decision (see, e.g. [Menezes
et al. (1996); Gallager (1968)lj.
Theorem 6.3 A thirddegree polynomial F ( X ) cannot be factored modulo
p if and only if
gcd(F(X), X p  X) = 1 .
+ +
As a result we have t 2 = 1 if gcd(X3 aX b,XP  X) = 1, and t 2 = 0
otherwise.
Let us estimate the complexity of Schoof™s algorithm. First, give
the following wellknown property of prime numbers (see [Rosen (1992);
Menezes et al. (1996)l).
Proposition 6.1 T h e number of primes less than n is approxzmately
n/ Inn.
It follows from Proposition 6.1 that mmax= O(1ogp) and the number
of moduli for which the computations are performed is O(1ogp). The most
timeconsuming step in the algorithm is the computation of z P 2 and the sim
ilar polynomials. If a fast exponentiation method is used, this step requires
O(1ogp) multiplications with polynomials of degree O ( m 2 ) = O(log2 p ) .
Each multiplication requires O(10g4p ) numerical multiplications modulo
p, i.e. there is a total of O(10g5p) multiplications modulo p. One multi
plication modulo p requires O(log2p ) bit operations. So computation of
xP2 requires O(10g7p) bit operations. Taking into account the number of
moduli we obtain the overall complexity O(log8p) bit operations.
Example 6.4 Determine the number of points on the curve used in Ex
ample 6.1 on p. 89:
Y 2= X 3 + 2X + 6 (mod 7) (u = 2, b = 6).
First apply the exponentialtime algorithm: for all values of X from 0
to 6 find corresponding values of Y (if any). We shall need a list of squares
Basics of Contemporary Cryptography f o r I T Practitioners
106
modulo 7:
02 = 0 ,
1,
12=
22=4,
32=9=2,
42 = 2 ,
52 = 4 ,
(mod7)
62 = 1
With the use of this list find the set of points E7(2,6):
does not exist,
= 0 , y2 = 6 ,
x y
++ 6=9=2, y = 3 and y = 3 = 4 ,
= 1 , y2 = 1 2
x
= 2 , y2 = 8 + 4 + 6 = 4 ,
x = 2 and y = 2 = 5 ,
y
+ = 2 and y = 2 = 5 ,
x = 3 , y2 = 27+ 6 6 = 4 , y
++
x = 4 , y2 = 64 8 6 = 1, y = 1 and y = 1 = 6 ,
x = 5 , y2 = 1 2 5 + 1 0 + 6 = 1, y = 1 a n d y = 1 = 6 ,
++
x = 6 , y2 = 216 12 6 = 3 , y does not exist.
Counting the number of points found and adding the point at infinity we
obtain
#E7(2,6) = 11
It is clear that this method cannot be applied if p is large, but we shall use
the result for checking.
Begin the execution of Schoof™s algorithm. Three moduli m = 2,3,5
will suffice since 2 . 3 . 5 = 30 > 4 f i = 10.58 (in fact, two moduli m = 3,5
would be enough but we shall use also m = 2 for the sake of exposition).
For ease of designation, we shall write polynomials as decimal numbers
(the size of the modulus allows us to do that). Thus, for instance,
+ 5x2 + 2 = lx4 + Ox3 + 5x2 + Ox + 2 = 10502,
x4
+ox3 +ox2 + i x + 0 = iooio.
x4 + Z = ix4
All operations with coefficients will be performed modulo 7. Compute the
Elliptic C u r v e Cryptosystems 107
necessary division polynomials:
=0,
$0
1,
$1 =
$2=2y,
$3 = 30523,
= 4y 1031115 = 4054446y,
$4
= 4054446 * 10262  6025554626356
 $$
I:
= $4$:
$5
= 5055036550230.
Now we are to solve Eq. (6.26) for m = 3. Compute modulo $3:
x7 = 1363 ,
y7 = (y2)3y = 10263y = 1360y,
2 4 9 = 10 = 2 ,
y4™ = 102624y= 6y,
p3 = 7 mod 3 = 1.
The left side of (6.26) converts to
Hence, t 3 = 0.
Now solve Eq. (6.26) for m = 5. Compute modulo $5:
= 10000000,
27
,
y7 = 1064524266˜
x4™ = 531353334500,
y4™ = 650465522521y,
p5 = 2 .
Let™s find a point Q = [2](x,y). In general case, it is done by Eq. (6.25):
4Y2XlC13 10314 1031115˜
$4
# x4™, > 0. Find
We can see that so we shall look for r a point
XQ
Basics of Contemporary Cryptography f o r IT Practitioners
108
+ Q by Eqs. (6.5)™ (6.7)™ (6.8):
R = (x4™, y4™)
(1031115  650465522521 . 1045431)4013y


1045431(10314  531353334500 * 4013
541024434205˜


115461562234 ™
5410244342052y2 10314
 531353334500  
XR =
1154615622342 4013
552631612401


533030166456 ™
. 541024434205˜
552631612401) 
533030166456 115461562234