Hyperelliptic Curves - Elliptic Curves: Number Theory and Cryptography - page 424

where D i is the divisor corresponding to ( T i ,W i )andwhere+ c i is chosen
if W i ≡ V (mod T i )and − c i is chosen if − W i ≡ V (mod T i ). Append

the row r =( ± c 1 ,..., ± c s )tothematrix M .

6. If the number r of rows of M is less than s , return to Step 2. If r ≥ s ,

continue to step 7.
7. Let r i denote the i th row of M . Find a relation d i r i ≡ 0(mod N )

among the rows of M ,with d i ∈ Z .

8. Let m i ,n i bethevaluesof m, n from Step 2 that yield the row r i .Let

m 0 = d i m i and n 0 = d i n i .

9. If gcd( m 0 ,N )=1,let k ≡−n 0 m − 1

(mod N ).

0

10. If gcd( m 0 ,N ) = 1, continue to do Steps 2 through 9 and find more rela-
tions among the rows until a relation is found that yields gcd( m 0 ,N )=
1.

11. Output k .

REMARK 13.13 What the algorithm does is compute relations

m 1 D 1 + n 1 D 2 ≡ c 11 D 1 + ··· + c 1 s D s
··· ··· ···

m r D 1 + n r D 2 ≡ c r 1 D 1 + ··· + c rs D s

Adding the appropriate rows corresponding to a relation among the rows
yields

m 0 D 1 + n 0 D 2 ≡ 0 · D 1 + ··· +0 · D s .

Dividing by −m 0 yields D 1 ≡− ( n 0 /m 0 ) D 2 .

REMARK 13.14 The Pollard ρ method (Section 5.2.2) also looks at
sums mD 1 + nD 2 and looks for a match between the divisors obtained for two
different pairs ( m, n ). This corresponds to a relation of two rows being equal
in the present method. The possibility of much more general relations among
the rows makes the present method much faster than the ρ method. In the ρ
method, the random integers m, n are chosen by a type of random walk. This
is also a good way to proceed in the present method.

Example 13.5
Consider the curve C : y 2 = x 5 − 1over F 3 .Let D 1 =( x 2 − 1 ,x− 1) and

D 2 =( x 2 − x − 1 , −x + 1). The problem is to find k such that D 2 = kD 1 .