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

Example 13.3
Let D = gcd(div( U ) , div( y − V )), which corresponds to ( U, V ), and suppose
that deg U =2where U is an irreducible polynomial in F q [ x ]. We can factor
U as ( x − a 1 )( x − a 2 )over F q 2 .Then

D =[( a 1 ,V ( a 1 ))]+[ a 2 ,V ( a 2 ))] − 2[ ∞ ] .

Since a 1 ,a 2 ∈ F q ,thepoints( a i ,V ( a i )) are not defined over F q . H owever, φ
interchanges [( a 1 ,V ( a 1 ))] and [( a 2 ,V ( a 2 ))], hence φ ( D )= D .

Example 13.4
Let's consider the curve C : y 2 = x 5 − 1over F 3 . The points in C ( F 3 )are

{∞, (1 , 0) , ( − 1 , 1) , ( − 1 , − 1) }.

and i = √ − Denote the elements of F 9 as a + bi with a, b ∈{− 1 , 0 , 1 } 1. The

elements of C ( F 9 )are

∞, (1 , 0) , ( − 1 , 1) , ( − 1 , − 1) , (0 ,i ) , (0 , −i ) ,

( − 1+ i, 1+ i ) , ( − 1+ i, − 1 − i ) , ( − 1 − i, 1 − i ) , ( − 1 − i, − 1+ i ) .

The pairs of polynomials ( U, V ) corresponding to reduced divisors are

( x 2 ( x 2 ( x 2 D ≡ − 1 ,x − 1) , 2 D ≡ − x +1 ,x − 1) , 3 D ≡ − x − 1 ,x − 1) ,

4 D ≡ ( x +1 , − 1) , 5 D ≡ ( x − 1 , 0) , 6 D ≡ ( x +1 , 1) ,

7 D ≡ ( x 2 8 D ≡ ( x 2 − x − 1 , −x +1) , − x +1 , −x +1) ,

( x 2 9 D ≡ − 1 , − x +1) , 10 D ≡ (1 , 0)

(where “ ≡ ” denotes congruence modulo principal divisors). These can be
found by exhaustively listing all polynomials U of degree at most 2 with coef-
ficients in F 3 , and finding solutions to V 2 ≡ x 5 − 1(mod U ) when they exist.

The pair ( x +1 , 1) corresponds to the divisor gcd (div( x +1) , div( y − 1)) =
[( − 1 , 1)] − [ ∞ ]. The pair ( x 2 − x − 1 ,x − 1) corresponds to the divisor

[( − 1+ i, 1+ i )] + [( − 1 − i, 1 − i )] − 2[ ∞ ]. This can be seen as follows. The

roots of x 2 − x − 1are x = − 1+ i and x = − 1 − i . The polynomial V = x − 1

tells us that the y -coordinates satisfy y = x − 1, which yields y =1+ i and

y =1 i ) are not defined

over F 3 individually. However, they are interchanged by the Frobenius map,
which maps i → i 3 = −i , so the divisor is left unchanged by Frobenius and
is therefore defined over F 3 . Similarly, the pair ( x 2 +2 x +2 , 2 x + 1) corre-
sponds to the divisor [( − 1+ i, − 1 −i )]+[( − 1 −i, − 1+ i )] − 2[ ∞ ]. The divisor
[(0 ,i )] + [(0 , −i )] − 2[ ∞ ] is also defined over F 3 . What does it correspond to?
Observe that it is not reduced since w (0 ,i )=(0 , −i ). Therefore, it must be
reduced first. Since it is of the form [ P ]+[ w ( P )] − 2[ ∞ ], it is principal, so

− i .Thepoin s( − 1+ i, 1+ i )and( − 1 − i, 1 −