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

V 0 vanishing of U at each point ( a, V 0 ( a )). By Proposition 13.4, f − is a

V 2 multiple of U .Since V ≡ V 0 (mod U ), f − is also a multiple of U ,as

required.
Steps (4) through (7) are the reduction algorithm. Theorem 13.9 says that
this process yields the desired reduced divisor.

Example 13.1
Consider the curve C : y 2 = x 5 − 1over F 3 . Let's compute

x 2

− x +1 , −x +1 +( x − 1 , 0) .

We have U 1 = x 2 − x +1 ,U 2 = x − 1 ,V 1 + V 2 = − x + 1. The gcd of these is

1, and

( x 2 − x +1) · 1+( x − 1) · ( − x )+( − x +1) · 0=1 ,

so we may take h 1 =1 ,h 2 = −x, h 3 =0. Weobtain

U =( x 2 1) = x 3 + x 2 1 ,

V ≡ 0+( x − 1)( −x +1)( −x )+0= x 3 + x 2 + x ≡−x +1 (mod U ) .

− x +1)( x − − x −

The reduction procedure yields

U = ( x 5

x +1) 2

− 1) − ( −

= x 2 − x − 1

U

V = x − 1. Therefore,
x 2

and

x +1 +( x 1 , 0) = x 2 1 . − x +1 , − − − x − 1 ,x −

13.4 The Discrete Logarithm Problem

Up to now, we have been working over an algebraically closed field. But now
we consider a curve and divisors defined over a finite field F q .Wecontinue
to assume that q is not a power of 2, so we can use (13.2) instead of (13.1).
We take f ( x ) in (13. 2) to be a polynomial with coe cients in F q and with
no multiple roots in F q .Let φ be the q -th power Frobenius map. A divisor
D is said to be defined over F q if φ ( D )= D (where φ ([ P ]) is defined to be
[ φ ( P )] and φ ([ ∞ ]) = [ ∞ ]). This means that φ can permute the summands of
D as long as it leaves the overall sum unchanged. A divisor class is said to
be defined over F q if φ ( D ) − D is a principal divisor for some (equivalently,