• 検索結果がありません。

Addition of normal divisors

ドキュメント内 PDF www.math.tohoku.ac.jp (ページ 44-76)

for q2,1(X, Y), q2,2(X, Y) K[X, Y] with LM(q2,1(X, Y)) X3, LM(q2,2(X, Y)) X.

Thus, ifa1 = 0, then

A2 = −a2+b1, B2 = a21−a3−a1s2,

C2 = −a21a2+a2a3−a21b1−a3b1+a1b3−a1s1+a1a2s2+a21t3

(3.4)

by (3.1) and (3.2). And, if a1 = 0, then A2 = −a2+b1, B2 =−a3, C2 = a2a3−a3b1 by (3.1), (3.2) and (3.3). These values are the same as those in (3.4) with a1 = 0.

For h3(X, Y)∈G,

h3(X, Y)g2(X, Y) = q3,1(X, Y)g1(X, Y) +q3,2(X, Y)F(X, Y) (3.5) forq3,1(X, Y), q3,2(X, Y)∈K[X, Y] with LM(q3,1(X, Y))≤X3, LM(q3,2(X, Y))≤X, and h3(X, Y)g3(X, Y) = q4,1(X, Y)g1(X, Y) +q4,2(X, Y)F(X, Y) (3.6) for q4,1(X, Y), q4,2(X, Y) K[X, Y] with LM(q4,1(X, Y)) X2Y, LM(q4,2(X, Y)) Y. Thus, ifa1 = 0, then

A3 = a12−b2−a1s2,

B3 = 2a1b1−b3+s1−b1s2−a1t3,

C3 = 2a1a22 + 2a21a3 + 2a1a2b1−a1b213a21b2+b22+a2b3−b1b3 +s0+a22s2−a1a3s2−a2b1s2 + 2a1b2s2−a1t2+a1b1t3

(3.7)

by (3.1) and (3.5). And, if a1 = 0, then A3 = −b2, B3 = −b3 +s1 −b1s2 and C3 = b22+a2b3−b1b3+s0+a22s2−a2b1s2 by (3.1), (3.5) and (3.6). These values are the same as those in (3.7) with a1 = 0.

Hence, we completely proved it. 2

From now on, we use the following notation: For i= 1,2, Ii : a normal ideal ϕ1(L(∞ · ∞ −Ei)),

I : a normal ideal ϕ1(L(∞ · ∞ −E)), I : a normal ideal ϕ1(L(∞ · ∞ −E)), Gi : a reduced Groebner basis for Ii,

Gg : a set {fi(X, Y)gj(X, Y), F(X, Y)|fi(X, Y)∈G1, gj(X, Y)∈G2}, G : a reduced Groebner basis for I,

H : a reduced Groebner basis for ϕ1(ID1+D2) =ϕ1(L(∞ · ∞ −(E1+E2))), h1(X, Y) : a polynomial with the smallest leading monomial in H,

v1(X, Y) : a monic polynomial with the smallest leading monomial in I. The final purpose of this section is to find Gfor the given G1 and G2.

We first study a way of finding the reduced Groebner basisHforϕ1(ID1+D2) by using the fact that Gg is a generating set of ϕ1(ID1+D2). We have δ(H) = n1+n2. Thus, if δ(Gg) > n1 +n2, then Gg is not a Groebner basis and it is necessary to do division of S-polynomials by the algorithm due to Buchberger. It is possible to omit the following S-polynomials in Gg:

(a) S(figj, figj) forfi, fi ∈G1, gj, gj ∈G2 with i=i or j =j; (b) S(f, g) forf, g ∈Gg with lcm(LM(f),LM(g)) = LM(f)LM(g);

(c) S(f, g) for f, g∈Gg with h=f, ginGg such thatS(f, h) and S(g, h) are divisible byGg, and LT(h) divides lcm(LT(f),LT(g)).

Let S = {S1, . . . , Sm} be the set of S-polynomials in Gg except those S-polynomials.

For i = 1, . . . , m, let ri be the remainder of Si on division by Gg ∪ {r1, . . . , ri1}. Let Gg,1 =Gg ∪ {r1, . . . , rm}. Then

n1+n2 ≤δ(Gg,1)< δ(Gg).

Ifn1+n2 < δ(Gg,1), it is needed to consider S-polynomials inGg,1. For everyri = 0, it is enough to consider the S-polynomials S(ri, f) andS(ri, g), wheref (resp. g) is a nearest element to ri in the lower right-hand (resp. in the upper left-hand) as considering the leading monomials by the above (c). By iterating this work until the value of δ decreases ton1+n2, we get a Groebner basis. Thus the number of divisions to be done for getting a Groebner basis for ϕ1(ID1+D2) is m+ 2(δ(Gg)(n1+n2)1) at most.

Since we have δ(H) = n1 +n2 6, H contains an element whose leading monomial is smaller than Y3. Thus, D =(D1+D2) + (h1) for the polynomial h1(X, Y) with the smallest leading monomial inH by Proposition 3.3.1. Furthermore, we have

I ={v(X, Y)|v(X, Y)hi(X, Y)∈ h1(X, Y), F(X, Y) for all hi(X, Y)∈H} as shown in Section 3.3. Since D is a normal divisor,D=−D+ (v1) and v1(X, Y)∈G.

It follows that

D=D1+D2(h1) + (v1).

Thus

E =E1+E2 (h1)++ (v1)+

because the divisors D, D1+D2, (h1) and (v1) have no pole point but at infinity. Since D = (D1 +D2) + (h1), we have n = deg(h1)+(n1 +n2). Thus LM(v1(X, Y)) is determined if deg(h1)+ = n1 +n2 + 2. If deg(h1)+ = n1 +n2 + 2, then LM(v1(X, Y)) is either X or Y. Further, LM(v1(X, Y)) is determined by LM(v1(X, Y)hi(X, Y)) LM(h1(X, Y), F(X, Y)) for allhi(X, Y)∈H. LetH ={h1(X, Y), . . . , ht(X, Y)}. Then LM(G) is determined by LM(H) and G is obtained by a generating set for I, which is given as follows.

Let qi,1(X, Y), qi,2(X, Y)∈K[X, Y] satisfy

v1(X, Y)hi(X, Y) =qi,1(X, Y)h1(X, Y) +qi,2(X, Y)F(X, Y).

Then

(v1) + (hi) = (qi,1) + (h1).

It follows that

(v1)++ (hi)+= (qi,1)++ (h1)+. Thus

(qi,1)+= (v1)++ (hi)+(h1)+.

Since (hi)+≥E1+E2, we have qi,1 ∈L(∞ · ∞ −E). Thus qi,1(X, Y)∈I.

If f(X, Y)∈I, then (f)+ ≥E. It follows that (f)+ E1+E2(h1)++ (v1)+

= min{(hi)+(h1)++ (v1)+ |i= 1, . . . , t}

= min{(qi,1)+ |i= 1, . . . , t}.

It implies that f ∈ q1,1, . . . , qt,1. Thus

f(X, Y) ϕ1(q1,1, . . . , qt,1)

= q1,1(X, Y), . . . , qt,1(X, Y), F(X, Y). Hence I =q1,1(X, Y), . . . , qt,1(X, Y), F(X, Y).

Now, we study the sum D1 +D2. We assume that coefficients Ai, Bi, Ci, ai, bi, ci of polynomials are elements ofK and we assume thatSi, ri are polynomials inK[X, Y]. For a polynomialf(X, Y), we write f instead of f(X, Y).

I.n1 =1,n2 =1

Since deg (D1+D2)+ = 2, D1 +D2 is a normal divisor by Theorem 4.1.2. Thus D=D1+D2, and Gis equal to H. If the reduced Groebner bases are

G1 = {f1(X, Y) = X+C1, f2(X, Y) = Y +C2}, G2 = {g1(X, Y) =X+c1, g2(X, Y) =Y +c2},

we have the following diagram on LM(Gg). The point of vacant circle denotes an element in ∆(Gg), and ‘MD = (i, j) : f(X, Y)’ means LM(f(X, Y)) = XiYj for a polynomial f(X, Y)∈Gg.

e e u u

e u u u

u u u u

u u u u

0 1 2 3 i

1 2 3 j

(i, j)↔XiYj

LM(Gg) = {X2, XY, Y2, Y3}

MD =

(2,0) :f1g1 (1,1) :f1g2, f2g1 (0,2) :f2g2 (0,3) :F

It follows thatS ={S1 =S(f1g2, f2g1), S2 =S(F, f2g2)}with deg(Gg) =n1+n2+ 1. For a nonzero ri in{r1, r2}, LM(ri) is either X orY. The remainder of S1 on division byGg is

r1 = (C1−c1)Y + (−C2+c2)X+C1c2−C2c1.

Further, if r1 = 0, i.e. G1 =G2, the remainder ofS2 on division by Gg is r2 =FY(−C1,−C2)(Y +C2) +FX(−C1,−C2)(X+C1),

where FX (resp. FY) denotes the partial derivative of F(X, Y) with respect to X (resp.

Y).

Since δ(H) = 2, we have the following diagrams on LM(H) = LM(G).

b r r r b r r r r r r r r r r r

i j

(1)

LM(H) = LM(G)

={X, Y2}

b b r r r r r r r r r r r r r r

i j

(2)

LM(H) = LM(G)

={Y, X2} As a result, we have the following:

(i) If G1 =G2 with C1 =c1, thenH =G={(C1−c1)1r1, f1g1}. (ii) If G1 =G2 with C1 =c1, thenH =G={f1, f2g2}.

(iii) If G1 =G2 and FY(−C1,−C2)= 0, then H =G={FY(−C1,−C2)1r2, f1g1}. (iv) If G1 =G2 and FY(−C1,−C2) = 0, then H =G={f1, f2g2}.

II.n1 =1,n2 =2

For a normal divisor D2 of pole degree 2, LM(G2) is either {X, Y2} or {Y, X2}.

1. LM(G2) ={X,Y2}

If the reduced Groebner bases are

G1 = {f1(X, Y) =X+C1, f2(X, Y) =Y +C2}, G2 = {g1(X, Y) =X+c1, g2(X, Y) =Y2+a2Y +c2},

we have the following diagram on LM(Gg).

e e u u

e u u u

e u u u

u u u u

0 1 2 3 i

1 2 3 j

LM(Gg) = {X2, XY, XY2, Y3}

(i, j)↔XiYj

MD = (0,3) :f2g2, F (1,2) :f1g2 (1,1) :f2g1 (2,0) :f1g1

It follows thatS ={S1 =S(f1g2, f2g1), S2 =S(F, f2g2)}with δ(Gg) =n1+n2+ 1. Thus, for ri = 0 in {r1, r2}, LM(ri) is either X or Y2. The coefficient of Y2 in r1 is C1 −c1. Further, if r1 = 0, the coefficient of Y2 in r2 is −C2−a2. It follows that H contains an element whose leading monomial is X if and only if C1 =c1 and C2 =−a2.

Sinceδ(H) = 3 with ∆(H)⊂ {1, X, Y, Y2}, we have the following diagrams on LM(H), which are followed by LM(G).

b r r r b r r r b r r r r r r r

i j

(1)

LM(H)

={X, Y3}

LM(G)

={1}

b b r r b r r r r r r r r r r r

i j

(2)

LM(H) = LM(G)

={X2, XY, Y2}

As a result, H and Gare as follows:

(i) If C1 =c1 and C2 =−a2, then H={f1, f2g2} and G={1}.

(ii) If C1 =c1 and C2 =−a2, thenH =G={f1g1, f2g1,−(C2+a2)1r2}. (iii) If C1 =c1, then H =G={f1g1, f2g1,(C1−c1)1r1}.

2. LM(G2) ={Y,X2}

If the reduced Groebner bases are

G1 = {f1(X, Y) =X+C1, f2(X, Y) =Y +C2},

G2 = {g1(X, Y) =Y +b1X+c1, g2(X, Y) =X2+b2X+c2},

we have the following diagram on LM(Gg).

e e e u

e u u u

u u u u

u u u u

0 1 2 3 i

1 2 3 j

LM(Gg) = {XY, Y2, X3, X2Y, Y3} (i, j)↔XiYj

MD = (0,3) :F (0,2) :f2g1

(1,1) :f1g1 (2,1) :f2g2 (3,0) :f1g2

It follows that S ={S1 =S(f1g1, f2g2), S2 = S(F, f2g1)} with δ(Gg) = n1+n2+ 1. For ri = 0 in{r1, r2}, LM(ri) is eitherY orX2. The coefficient ofX2 inr1 is−g1(−C1,−C2).

Further, if r1 = 0, the coefficient of X2 inr2 is the remainder on division of the quotient F(X,−b1X−c1)/g2 byf1.

Sinceδ(H) = 3 with ∆(H)⊂ {1, X, Y, X2}, we have the following diagrams on LM(H), which are followed by LM(G).

b b b r r r r r r r r r r r r r

i j

(1)

LM(H)

={Y, X3}

LM(G)

={X, Y2}

b b r r b r r r r r r r r r r r

i j

(2)

LM(H) = LM(G)

={X2, XY, Y2}

As a result, we have H and G as follows:

(i) If g1(−C1,−C2) = 0 and F(X,−b1X−c1) is divisible by f1g2, then H = {h1 = g1, h2 =f1g2}and LM(G) ={X, Y2}. For the polynomial v1, we have

v1h2 =q2,1h1+q2,2(F −Y2h1)

for q2,1, q2,2 K[X, Y] with LT(v1) = X,LM(q2,1) XY, q2,2 = 1 since {h1, F −Y2h1} is a Groebner basis for h1, F and v1h2 ∈ h1, F. It follows that {v1, Y2 −q2,1} is a Groebner basis, whose elements are monic polynomials, for I. Thus G={v1, v2} for the remainder v2 of Y2 −q2,1 on division by v1.

(ii) If g1(−C1,−C2) = 0 and F(X,−b1X−c1) is not divisible by f1g2, thenH =G= {r2,m, f1g1−b1r2,m, f2g1−b1f1g1+b21r2,m}.

(iii) If g1(−C1,−C2)= 0, then H =G={r1,m, f1g1−b1r1,m, f2g1−b1f1g1+b21r1,m}.

III.n1 =1,n2 =3

If the reduced Groebner bases are

G1 = {f1(X, Y) = X+C1, f2(X, Y) = Y +C2},

G2 = {g1(X, Y) = X2+a1Y +b1X+c1, g2(X, Y) = XY +a2Y +b2X+c2, g3(X, Y) =Y2+a3Y +b3X+c3},

we have the following diagram on LM(Gg).

e e e u

e e u u

e u u u

u u u u

0 1 2 3 i

1 2 3 j

LM(Gg) = {X3, X2Y, XY2, Y3}

(i, j)↔XiYj

MD = (0,3) :f2g3, F (1,2) :f1g3, f2g2 (2,1) :f1g2, f2g1 (3,0) :f1g1

It follows thatS ={S1 =S(f1g2, f2g1), S2 =S(f1g3, f2g2), S3 =S(F, f2g3)}with δ(Gg) = n1 +n2 + 2. For Gg,1 = Gg ∪ {r1, r2, r3}, δ(Gg,1) is either 4 or 5. If δ(Gg,1) = 4, then Gg,1 is a Groebner basis. If δ(Gg,1) = 5, then there is exactly one nonzero polynomial in {r1, r2, r3}. Forri = 0, LM(ri) isX2,XY orY2 and it is enough to consider the following S-polynomials in Gg,1:

(i) S(ri, f1g1) andS(ri, f1g2) if LM(ri) =X2; (ii) S(ri, f1g2) and S(ri, f1g3) if LM(ri) =XY; (iii) S(ri, f1g3) and S(ri, f2g3) if LM(ri) =Y2.

For a nonzero remainder r of these S-polynomials on division by Gg,1, Gg,1 ∪ {r} is a Groebner basis forϕ1(ID1+D2) sinceδ(Gg,1) =n1+n2+ 1. Thus, the number of divisions to be done for getting a Groebner basis for ϕ1(ID1+D2) is 5 at most.

Since δ(H) = 4 with ∆(H) ⊂ {1, X, Y, X2, XY, Y2}, we have the following diagrams on LM(H), which are followed by LM(G).

b b r r b r r r b r r r r r r r

i j

(1)

LM(H)

={X2, XY, Y3}

LM(G)

={X, Y}

b b r r b b r r r r r r r r r r

i j

(2)

LM(H)

={X2, Y2}

LM(G)

={Y, X2}

b b b r b r r r r r r r r r r r

i j

(3)

LM(H)

={XY, Y2, X3}

LM(G)

={X2, XY, Y2} In the case of (1), n = deg (h1)+(n1 +n2) = 2. It follows that LM(v1) is either X or Y. Let H = {h1, h2, h3} with LM(h1) = X2,LM(h2) = XY,LM(h3) = Y3. Then {h1, F}is a Groebner basis forh1, Fsince lcm(LM(h1),LM(F)) = LM(h1)LM(F). Thus LM(v1hi) ∈ X2, Y3 for all hi H. It follows that LM(v1) = X. Further, n = 1 and LM(G) ={X, Y}. Since v1h2 ∈ h1, F, we have

v1h2 =q2,1h1+q2,2F

for q2,1, q2,2 K[X, Y] with LT(q2,1) =Y, q2,2 = 0. It follows that {v1, q2,1} is a Groebner basis for I. Thus G={v1, v2} for the remainder v2 of q2,1 on division byv1.

In the case of (2), n = deg (h1)+(n1+n2) = 2. Let H ={h1, h2} with LM(h1) = X2,LM(h2) = Y2. Then {h1, F} is a Groebner basis for h1, F. Thus LM(v1hi) X2, Y3 for all hi H. It follows that LM(v1) = Y. Further, n = 2 and LM(G) = {Y, X2}. Since v1h2 ∈ h1, F, we have

v1h2 =q2,1h1+q2,2F

for q2,1, q2,2 K[X, Y] with LT(q2,1) = −X2, q2,2 = 1. It follows that {v1,−q2,1} is a Groebner basis for I. Thus G={v1, v2} for the remainder v2 of −q2,1 on division by v1.

In the case of (3), n = deg (h1)+(n1+n2) = 3. Thus LM(v1) =X2 and LM(G) = {X2, XY, Y2}. Let H = {h1, h2, h3} with LM(h1) = XY,LM(h2) = Y2,LM(h3) = X3. Then {h1, F, XF −Y2h1} is a Groebner basis for h1, F. Since v1hi ∈ h1, F for all hi ∈H, we have

v1h2 =q2,1h1+q2,2F +q2,3(XF −Y2h1)

for q2,1, q2,2, q2,3 ∈K[X, Y] with LT(q2,1) = XY,LM(q2,2)1, q2,3 = 0, and v1h3 =q3,1h1+q3,2F +q3,3(XF −Y2h1)

for q3,1, q3,2, q3,3 K[X, Y] with LM(q3,1) XY,LM(q3,2) 1, q3,3 = 1. It follows that {v1, q2,1, Y2−q3,1} is a Groebner basis forI. Thus G ={v1, v2, v3} for the remainder v2 of q2,1 on division byv1 and the remainderv3 of Y2−q3,1 on division by {v1, v2}.

Remark. We have another way to find H according to the relation between G1 and G2. We give it in Appendix.

IV. n1 =2,n2 =2

1. LM(G1) ={X,Y2},LM(G2) = {X,Y2}

If the reduced Groebner bases are

G1 = {f1(X, Y) =X+C1, f2(X, Y) =Y2 +A2Y +C2}, G2 = {g1(X, Y) =X+c1, g2(X, Y) = Y2+a2Y +c2}, we have the following diagram on LM(Gg).

e e u u

e e u u

e u u u

u u u u

u u u u

0 1 2 3 i

1 2 3 4 j

LM(Gg) = {X2, XY2, Y3, Y4}

(i, j)↔XiYj

MD = (0,4) :f2g2 (0,3) :F

(1,2) :f1g2, f2g1

(2,0) :f1g1

It follows that S = {S1 = S(f1g2, f2g1), S2 = S(F, f1g2), S3 =S(F, f2g2)} with δ(Gg) = n1+n2+ 1. For a nonzerori in{r1, r2, r3},Gg∪ {ri}is a Groebner basis for ϕ1(ID1+D2) with LM(ri) =XY or Y2 since δ(Gg) =n1+n2+ 1.

Since δ(H) = 4 with ∆(H) ⊂ {1, X, Y, XY, Y2}, we have the following diagrams on LM(H) with the same result on G corresponding to H as that ofIII. n1 =1,n2 =3.

b b r r b r r r b r r r r r r r

i j

(1)

LM(H)

={X2, XY, Y3}

LM(G)

={X, Y}

b b r r b b r r r r r r r r r r

i j

(2)

LM(H)

={X2, Y2}

LM(G)

={Y, X2}

2. LM(G1) ={X,Y2},LM(G2) = {Y,X2}

If the reduced Groebner bases are

G1 = {f1(X, Y) =X+C1, f2(X, Y) =Y2+A2Y +C2}, G2 = {g1(X, Y) =Y +b1X+c1, g2(X, Y) =X2+b2X+c2}, we have the following diagram on LM(Gg).

e e e u

e u u u

e u u u

u u u u

0 1 2 3 i

1 2 3 j

LM(Gg) = {XY, X3, Y3, X2Y2}

(i, j)↔XiYj

MD = (0,3) :f2g1, F (2,2) :f2g2 (1,1) :f1g1 (3,0) :f1g2

It follows that S ={S1 =S(F, f2g1), S2 =S(f2g2, f1g1)}with δ(Gg) = n1+n2+ 1. For a nonzerori in {r1, r2},Gg∪ {ri} is a Groebner basis for ϕ1(ID1+D2).

Since δ(H) = 4 with ∆(H) ⊂ {1, X, Y, X2, Y2}, we have the following diagrams on

LM(H) with the same result on G corresponding to H as that ofIII. n1 =1,n2 =3.

b b r r b r r r b r r r r r r r

i j

(1)

LM(H)

={X2, XY, Y3}

LM(G)

={X, Y}

b b b r b r r r r r r r r r r r

i j

(2)

LM(H)

={XY, Y2, X3}

LM(G)

={X2, XY, Y2}

3. LM(G1) ={Y,X2},LM(G2) = {Y,X2} If the reduced Groebner bases are

G1 = {f1(X, Y) =Y +B1X+C1, f2(X, Y) =X2+B2X+C2}, G2 = {g1(X, Y) = Y +b1X+c1, g2(X, Y) =X2+b2X+c2}, we have the following diagram on LM(Gg).

e e e e u

e e u u u

u u u u u

u u u u u

0 1 2 3 4 i

1 2 3 j

LM(Gg) = {Y2, X2Y, X4, Y3}

(i, j)↔XiYj

MD = (0,3) :F (0,2) :f1g1 (2,1) :f1g2, f2g1 (4,0) :f2g2

It follows thatS ={S1 =S(F, f1g3), S2 =S(f2g2, f1g1), S3 =S(f2g3, f1g2)}with δ(Gg) = n1+n2+ 2. ForGg,1 =Gg∪ {r1, r2, r3},δ(Gg,1) is either 5 or 6. If δ(Gg,1) = 5, thenGg,1

is a Groebner basis for ϕ1(ID1+D2). If δ(Gg,1) = 6, then there is exactly one nonzero polynomial in {r1, r2, r3}. For ri = 0, LM(ri) =XY or X3, and it is enough to consider the following S-polynomials:

(i) S(f1g1, ri) andS(f1g2, ri) if LM(ri) =XY; (ii) S(f2g1, ri) and S(f2g2, ri) if LM(ri) =X3.

Then, for a nonzero remainder r of these S-polynomials on division by Gg,1, Gg,1∪ {r}

is a Groebner basis for ϕ1(ID1+D2) since δ(Gg,1) = n1 +n2 + 1. Thus, the number of divisions to be done for getting a Groebner basis for ϕ1(ID1+D2) is 5 at most.

Since δ(H) = 4 with ∆(H) ⊂ {1, X, Y, X2, XY, X3}, we have the following diagrams on LM(H) with the same result on G corresponding to H as that of III. n1 =1,n2 =3.

b b b b r r r r r r r r r r r r r r r r

i j

(1)

LM(H)

={Y, X4}

LM(G)

={1}

b b r r r b b r r r r r r r r r r r r r

i j

(2)

LM(H)

={X2, Y2}

LM(G)

={Y, X2}

b b b r r b r r r r r r r r r r r r r r

i j

(3)

LM(H)

={XY, Y2, X3}

LM(G)

={X2, XY, Y2}

V. n1 =2,n2 =3

1. LM(G1) ={X,Y2}

If the reduced Groebner bases are

G1 = {f1(X, Y) = X+C1, f2(X, Y) = Y2+A2Y +C2},

G2 = {g1(X, Y) = X2+a1Y +b1X+c1, g2(X, Y) = XY +a2Y +b2X+c2, g3(X, Y) =Y2+a3Y +b3X+c3},

we have the following diagram on LM(Gg).

e e e u

e e u u

e u u u

u u u u

u u u u

0 1 2 3 i

1 2 3 4 j

LM(Gg) = {X3, X2Y, XY2, Y3, X2Y2, XY3, Y4} (i, j)↔XiYj

MD = (0,4) :f2g3

(0,3) :F (1,3) : f2g2 (1,2) :f1g3 (2,2) : f2g1 (2,1) :f1g2

(3,0) :f1g1

It follows that S = {S1 = S(f2g1, f1g3), S2 = S(f2g2, f1g3), S3 = S(f2g2, F), S4 = S(f2g3, F)} with δ(Gg) = n1 + n2 + 1. For ri = 0 in {r1, r2, r3, r4}, Gg ∪ {ri} is a Groebner basis for ϕ1(ID1+D2).

Since δ(H) = 5 with ∆(H) ⊂ {1, X, Y, X2, XY, Y2}, we have the following diagrams on LM(H), which are followed by LM(G).

b b r r b b r r b r r r r r r r r r r r

i j

(1)

LM(H)

={X2, XY2, Y3}

LM(G)

={X, Y2}

b b b r b r r r b r r r r r r r r r r r

i j

(2)

LM(H)

={XY, X3, Y3}

LM(G)

={Y, X2}

b b b r b b r r r r r r r r r r r r r r

i j

(3)

LM(H)

={Y2, X3, X2Y}

LM(G)

={X2, XY, Y2} In the case of (1), n = 1 and LM(v1) = X. Further, n = 2 and LM(G) ={X, Y2}. Let H ={h1, h2, h3} with LM(h1) =X2,LM(h2) =XY2,LM(h3) =Y3. Then {h1, F} is a Groebner basis for h1, F. Since v1h2 ∈ h1, F, we have

v1h2 =q2,1h1+q2,2F

for q2,1, q2,2 K[X, Y] with LT(q2,1) = Y2,LM(q2,2) 1. It follows that {v1, q2,1} is a Groebner basis for I. Thus G={v1, v2} for the remainder v2 of q2,1 on division by v1.

In the case of (2), n = 2. It follows that LM(v1) is eitherX orY. LetH={h1, h2, h3} with LM(h1) =XY,LM(h2) = X3,LM(h3) =Y3. Then{h1, F, XF−Y2h1}is a Groebner basis forh1, F. Since LM(v1hi)∈ XY, X3, Y3 for allhi ∈H, we have LM(v1) =Y. It follows that n= 2 and LM(G) ={Y, X2}. Sincev1h2 ∈ h1, F, we have

v1h2 =q2,1h1+q2,2F +q2,3(XF −Y2h1)

for q2,1, q2,2, q2,3 K[X, Y] with LT(q2,1) = X2,LM(q2,2) 1, q2,3 = 0. It follows that {v1, q2,1} is a Groebner basis for I. Thus G = {v1, v2} for the remainder v2 of q2,1 on division byv1.

In the case of (3), n = 3 and LM(v1) =X2. Further, LM(G) = {X2, XY, Y2}. Let H ={h1, h2, h3} with LM(h1) =Y2,LM(h2) = X3,LM(h3) =X2Y. Then {h1, F −Y h1}

is a Groebner basis for h1, F. Sincev1h2 ∈ h1, F, we have v1h2 =q2,1h1+q2,2(F −Y h1) for q2,1, q2,2 ∈K[X, Y] with LM(q2,1)≤X2,LT(q2,2) = X, and

v1h3 =q3,1h1+q3,2(F −Y h1)

for q3,1, q3,2 K[X, Y] with LM(q3,1) XY,LT(q3,2) = Y. It follows that {v1, q2,2Y q2,1, q3,2Y −q3,1} is a Groebner basis for I. ThusG={v1, v2, v3}for the remainder v2 of q2,2Y −q2,1 on division byv1 and the remainder v3 of q3,2Y −q3,1 on division by {v1, v2}.

2. LM(G1) ={Y,X2}

If the reduced Groebner bases are

G1 = {f1(X, Y) = Y +B1X+C1, f2(X, Y) =X2+B2X+C2},

G2 = {g1(X, Y) = X2+a1Y +b1X+c1, g2(X, Y) = XY +a2Y +b2X+c2, g3(X, Y) =Y2+a3Y +b3X+c3},

we have the following diagram on LM(Gg).

e e e e u

e e u u u

e u u u u

u u u u u

0 1 2 3 4 i

1 2 3 j

LM(Gg) = {X2Y, XY2, X4, Y3, X3Y, X2Y2} (i, j)↔XiYj

MD = (0,3) : f1g3, F

(1,2) : f1g2 (2,2) :f2g3 (2,1) : f1g1 (3,1) :f2g2 (4,0) : f2g1

It follows thatS ={S1 =S(F, f1g3), S2 =S(f2g2, f1g1), S3 =S(f2g3, f1g2)}with δ(Gg) = n1 +n2 + 2. For Gg,1 = Gg ∪ {r1, r2, r3}, δ(Gg,1) is either 5 or 6. If δ(Gg,1) = 5, then Gg,1 is a Groebner basis. If δ(Gg,1) = 6, then there is exactly one nonzero polynomial in {r1, r2, r3}. For ri = 0, LM(ri) is XY, Y2 or X3 and it is enough to consider of the following S-polynomials:

(i) S(f1g1, ri) andS(f1g2, ri) if LM(ri) =XY;

(ii) S(f1g2, ri) and S(f1g3, ri) if LM(ri) =Y2; (iii) S(f2g1, ri) and S(f2g2, ri) if LM(ri) =X3.

For a nonzero remainder r of these S-polynomials on division by Gg,1, Gg,1 ∪ {r} is a Groebner basis forϕ1(ID1+D2) sinceδ(Gg,1) =n1+n2+ 1. Thus, the number of divisions to be done for getting a Groebner basis is 5 at most.

Since δ(H) = 5 with ∆(H) ⊂ {1, X, Y, X2, XY, Y2, X3}, we have the following di- agrams on LM(H) with the same result on G as that of 1. LM(G1) ={X,Y2} in V. n1 =2,n2 =3 except (2).

b b r r r b b r r r b r r r r r r r r r

i j

(1)

LM(H)

={X2, XY2, Y3}

LM(G)

={X, Y2}

b b b b r b r r r r r r r r r r r r r r

i j

(2)

LM(H)

={XY, Y2, X4}

LM(G)

={X, Y}

b b b r r b r r r r b r r r r r r r r r

i j

(3)

LM(H)

={XY, X3, Y3}

LM(G)

={Y, X2}

b b b r r b b r r r r r r r r r r r r r

i j

(4)

LM(H)

={Y2, X3, X2Y}

LM(G)

={X2, XY, Y2} In the case of (2), n = 2. Thus LM(v1) is either X or Y. Let H = {h1, h2, h3} with LM(h1) = XY,LM(h2) = Y2,LM(h3) = X4. Then {h1, F, XF −Y2h1} is a Groebner basis for h1, F.

Now, consider on LM(v1). Suppose that LM(v1) = Y. Then LM(G) ={Y, X2}. Since v1h2 ∈ h1, F,

v1h2 =q2,1h1+q2,2F +q2,3(XF −Y2h1)

for q2,1, q2,2, q2,3 K[X, Y] with LM(q2,1) Y, q2,2 = 1, q2,3 = 0. Then q2,1 = kv1 for k K since q2,1 I with LM(q2,1) Y. It follows that v1(h2 −kh1) = F . It is a contradiction since F is irreducible. Hence we have LM(v1) =X and LM(G) ={X, Y}.

Since v1h2 ∈ h1, F, we have

v1h2 =q2,1h1+q2,2F +q2,3(XF −Y2h1)

for q2,1, q2,2, q2,3 ∈K[X, Y] with LT(q2,1) =Y, q2,2 =q2,3 = 0. It follows that {v1, q2,1}is a Groebner basis for I. Thus G={v1, v2} for the remainder v2 of q2,1 on division by v1.

VI. n1 =3,n2 =3

If the reduced Groebner bases are

G1 = {f1(X, Y) = X2+A1Y +B1X+C1, f2(X, Y) = XY +A2Y +B2X+C2, f3(X, Y) = Y2+A3Y +B3X+C3},

G2 = {g1(X, Y) =X2 +a1Y +b1X+c1, g2(X, Y) = XY +a2Y +b2X+c2, g3(X, Y) =Y2+a3Y +b3X+c3},

we have the following diagram on LM(Gg).

e e e e u

e e e u u

e e u u u

u u u u u

u u u u u

0 1 2 3 4 i

1 2 3 4 j

LM(Gg) ={X4, Y3, X3Y, X2Y2, XY3, Y4} (i, j)↔XiYj

MD = (0,4) : f3g3

(0,3) : F (1,3) :f2g3, f3g2 (2,2) : f1g3, f2g2, f3g1

(3,1) : f1g2, f2g1 (4,0) : f1g1

It follows that S = {S1 = S(f1g2, f2g1), S2 = S(f1g3, f2g2), S3 = S(f1g3, f3g1), S4 = S(f2g3, f3g2), S5 = S(f2g3, F), S6 = S(f3g3, F)} with δ(Gg) = n1 +n2 + 3. For Gg,1 = Gg∪{r1, r2, r3, r4, r5, r6},δ(Gg,1) is 6, 7 or 8. Ifδ(Gg,1) = 6, thenGg,1 is a Groebner basis.

Ifδ(Gg,1) = 7, then there are one or two nonzero polynomials in {r1, r2, r3, r4, r5, r6}. For all ri = 0 in {r1, r2, r3, r4, r5, r6}, we compute the remainders of S-polynomials S(ri, f) and S(ri, g) for a nearest polynomial f to ri in the lower right-hand and a nearest polynomial g to ri in the upper left-hand of Gg,1 as considering the leading monomi- als. Then, for a nonzero remainder r of S-polynomials, Gg,1 ∪ {r} is a Groebner basis since δ(Gg,1) = n1 +n2 + 1. If δ(Gg,1) = 8, then there is exactly one nonzero poly- nomial in {r1, r2, r3, r4, r5, r6}. For a nonzero ri in {r1, r2, r3, r4, r5, r6}, it is enough to consider the S-polynomials S(ri, f) and S(ri, g) for a nearest polynomial f to ri in the lower right-hand and a nearest polynomial g tori in the upper left-hand ofGg,1. Let ri,1 be the remainder of S(ri, f) on division by Gg,1 and let ri,2 be the remainder of S(ri, g) on division by Gg,1 ∪ {ri,1}. For Gg,2 = Gg,1∪ {ri,1, ri,2}, deg(Gg,2) is either 6 or 7. If δ(Gg,2) = 6, then Gg,2 is a Groebner basis. If δ(Gg,2) = 7, then there is only one nonzero polynomial in {ri,1, ri,2}. For a nonzero ri,j in {ri,1, ri,2}, it is enough to consider the

S-polynomials S(ri,j, f) andS(ri,j, g) for a nearest polynomial f tori,j in the lower right- hand and a nearest polynomial g to ri,j in the upper left-hand of Gg,2. For a nonzero remainder r of those S-polynomials on division by Gg,2, Gg,2 ∪ {r} is a Groebner basis since δ(Gg,2) = n1 +n2 + 1. Thus, the number of divisions to be done for getting a Groebner basis is 10 at most. In particular, if G1 = G2, the number of divisions to be done is 7 at most.

Since δ(H) = 6 with ∆(H) ⊂ {1, X, Y, X2, XY, Y2, X3, X2Y, XY2}, we have the fol- lowing diagrams on LM(H), which are followed by LM(G).

b b r r r b b r r r b b r r r r r r r r r r r r r

i j

(1)

LM(H)

={X2,Y3}

LM(G)

={1}

b b b b r b r r r r b r r r r r r r r r r r r r r

i j

(2)

LM(H)

={XY,X4,Y3}

LM(G)

={X,Y2}

b b b r r b b b r r r r r r r r r r r r r r r r r

i j

(3)

LM(H)

={Y2,X3}

LM(G)

={X,Y}

b b b b r b b r r r r r r r r r r r r r r r r r r

i j

(4)

LM(H)

={Y2,X2Y,X4}

LM(G)

={Y,X2}

b b b r r b b r r r b r r r r r r r r r r r r r r

i j

(5)

LM(H)

={X3,X2Y,XY2,Y3}

LM(G)

={X2,XY,Y2}

In the case of (1), n = 0. Thusn = 0 andG={1}.

In the case of (2), n = 1. Thus LM(v1) = X and LM(G) = {X, Y2}. Let H = {h1, h2, h3} with LM(h1) = XY,LM(h2) =X4,LM(h3) = Y3. Then {h1, F, XF −Y2h1} is a Groebner basis for h1, F. Sincev1h2 ∈ h1, F, we have

v1h2 =q2,1h1+q2,2F +q2,3(XF −Y2h1)

for q2,1, q2,2, q2,3 K[X, Y] with LM(q2,1) XY,LM(q2,2) 1, q2,3 = 1. It follows that {v1, Y2−q2,1}is a Groebner basis forI. ThusG={v1, v2}for the remainderv2 ofY2−q2,1 on division by v1.

In the case of (3), n = 2. Thus LM(v1) is either X or Y. Let H = {h1, h2} with LM(h1) =Y2,LM(h2) =X3. Then {h1, F −Y h1} is a Groebner basis for h1, F. Since LM(v1hi) ∈ Y2, X4 for all hi H, we have LM(v1) = X. It follows that LM(G) = {X, Y}. Sincev1h2 ∈ h1, F, we have

v1h2 =q2,1h1+q2,2(F −Y h1)

for q2,1, q2,2 K[X, Y] with LM(q2,1) X, q2,2 = 1. It follows that {v1, Y −q2,1} is a Groebner basis for I. Thus G = {v1, v2} for the remainder v2 of Y −q2,1 on division by v1.

In the case of (4), n = 2. Thus LM(v1) is either X or Y. Let H = {h1, h2, h3} with LM(h1) = Y2,LM(h2) = X2Y,LM(h3) = X4. Then {h1, F −Y h1} is a Groebner basis for h1, F. Since LM(v1h2) ∈ Y2, X4, we have LM(v1) = Y. It follows that LM(G) ={Y, X2}. Since v1h2 ∈ h1, F, we have

v1h2 =q2,1h1+q2,2(F −Y h1)

for q2,1, q2,2 ∈K[X, Y] with LT(q2,1) =X2,LM(q2,2)1. It follows that{v1, q2,1−Y q2,2} is a Groebner basis forI. ThusG={v1, v2}for the remainderv2 ofq2,1−Y q2,2 on division byv1.

In the case of (5), n = 3 and LM(v1) =X2. Further, LM(G) = {X2, XY, Y2}. Let H = {h1, h2, h3, h4} with LM(h1) = X3,LM(h2) = X2Y,LM(h3) = XY2,LM(h4) = Y3. Then{h1, F} is a Groebner basis forh1, F. Sincev1hi ∈ h1, F for allhi ∈H, we have

v1h2 =q2,1h1+q2,2F

for q2,1, q2,2 ∈K[X, Y] with LT(q2,1) =XY,LM(q2,2)≤X, and v1h3 =q3,1h1+q3,2F

for q3,1, q3,2 ∈K[X, Y] with LT(q3,1) = Y2,LM(q3,2) Y. It follows that {v1, q2,1, q3,1} is a Groebner basis for I. Thus G= {v1, v2, v3} for the remainder v2 of q2,1 on division by v1 and the remainder v3 of q3,1 on division by {v1, v2}.

Chapter 5 Appendix

In this appendix, we consider on the sum of normal divisorsD1 andD2 of aC34curve by using the relation between the reduced Groebner basis for ϕ1(ID1) and the reduced Groebner basis for ϕ1(ID2). In particular, we consider on the reduced Groebner basis H for ϕ1(ID1+D2). Let D be the normal divisor such that D ∼D1+D2. For the given H, the computation of the reduced Groebner basis Gfor ϕ1(ID) is presented in Section 4.4. Now that the reduced Groebner basis is easily computed by a Groebner basis ([5]), we compute a Groebner basis. Here, we use the notation in Chapter 4. Sometimes we represent a polynomial f(X, Y)∈K[X, Y] as f.

For the sum D1+D2 with n1 = 1 and n2 = 1 or 2, the result onGis given in Section 4.4.

Now, we consider the sum D1 +D2 with n1 = 1 and n2 = 3. Let D1 = P − ∞ and D2 =E23· ∞ be normal divisors ofC with

G1 ={f1(X, Y) =X+C1, f2(X, Y) =Y +C2}

and G2 ={g1(X, Y), g2(X, Y), g3(X, Y)}, where

g1(X, Y) = X2 +a1Y +b1X +c1, g2(X, Y) = XY +a2Y +b2X +c2, g3(X, Y) = Y2 +a3Y +b3X +c3.

Let

g2(X, Y) = XY + (−a2+b1)Y + (a21−a3 −a1s2)X

−a21a2+a2a3−a21b1−a3b1+a1b3−a1s1+a1a2s2+a21t3, g3(X, Y) = Y2+ (a21 −b2−a1s2)Y + (2a1b1−b3+s1−b1s2−a1t3)X

2a1a22+ 2a21a3+ 2a1a2b1−a1b213a21b2+b22+a2b3−b1b3+s0+a22s2

−a1a3s2−a2b1s2+ 2a1b2s2 −a1t2+a1b1t3.

Then {g1(X, Y), g2(X, Y), g3(X, Y)} is the reduced Groebner basis for the normal ideal ϕ1(ID

2), where D2 is the normal divisor such that D2 ∼ −D2.

For S ={S1 =S(f1g2, f2g1), S2 =S(f1g3, f2g2), S3 = (F, f2g3)} and the remainder r3 of S3 on division by Gg ={figj |fi ∈G1, gj ∈G2} ∪ {F}, we have

S1 = −a1Y2+ (a2−b1+C1)XY +· · ·,

S2 = (−a2+C1)Y2+ (a3−b2−C2)XY +· · ·,

r3 = (a3+C2)Y2+ (a1a2+a1b1−b3+a1C1+s1−a2s2−C1s2−a1t3)XY +· · ·. Here,

g1(−C1,−C2) = (a2−b1 +C1)(−a2+C1) +a1(a3−b2−C2),

g2(−C1,−C2) = −a1(a1a2+a1b1−b3+a1C1+s1−a2s2−C1s2−a1t3) +(a2−b1+C1)(a3+C2)

by Theorem 4.2.2. It follows that:

(a) Y2, XY LM(S1, S2) if g1(−C1,−C2)= 0;

(b) Y2, XY LM(S1, r3) if g2(−C1,−C2)= 0.

Since δ(H) = 4 with ∆(H) ⊂ {1, X, Y, X2, XY, Y2}, LM(H) is one of the following:

{X2, XY, Y3}; {X2, Y2}; and {XY, Y2, X3}. For every h(X, Y) H, h(X, Y) is divis- ible by G2 since ϕ1(ID1+D2) ϕ1(ID2). It implies that X2 LM(H) if and only if g1(X, Y)∈H. In other words,X2 LM(H) if and only if (D2)+≥P = (−C1,−C2), i.e.

g1(−C1,−C2) =g2(−C1,−C2) = g3(−C1,−C2) = 0.

As a result, we have the following on the ideal ϕ1(ID1+D2)⊂K[X, Y].

(i) If g1(−C1,−C2)= 0, then we have a Groebner basis

{g2+k1g1, g3+k2g1, f1g1}with LM(H) = {XY, Y2, X3},

where k1 =−g1(−C1,−C2)1g2(−C1,−C2), k2 =−g1(−C1,−C2)1g3(−C1,−C2)∈K.

(ii) If g1(−C1,−C2) = 0 and g2(−C1,−C2)= 0, then we have a Groebner basis {S1, r3, S(S1, r3), f1g1} with LM(H) ={XY, Y2, X3}.

(iii) If g1(−C1,−C2) =g2(−C1,−C2) = 0 andg3(−C1,−C2)= 0, then a1 = 0 and we have a Groebner basis

{S2, r3, g2+FY(−C1,−C2)1FX(−C1,−C2)g1, f1g1}with LM(H) ={XY, Y2, X3}. (iv) If g1(−C1,−C2) = g2(−C1,−C2) = g3(−C1,−C2) = 0, then we have a Groebner basis

{g1, g2, f2g3}with LM(H) = {X2, XY, Y3} in the case of a1 =−a2+C1 =a3+C2 = 0, and

{S1, S2, r3, g1} with LM(H) ={X2, Y2} in the other cases.

Hence we have G whenn1 = 1.

In the case of n1 = 2 and n2 = 2 or 3, the zero divisor E1 = P1 +P2 is obtained by the equations f1(X, Y) = 0 and f2(X, Y) = 0. Thus G can be obtained by the sum of P1− ∞ and (P2− ∞) +D2.

Now, we consider the last case n1 =n2 = 3. Let E1 =P1+P2+P3 withPi = (xi, yi).

Then

(X+A2)f2(X, Y)−A1f1(X, Y) =

3 i=1

(X−xi). (1)

At first, we compute the reduced Groebner basis Gc for f1, f2, f3, f1−g1, f2−g2, f3−g3. Then LM(Gc) ={1},{X, Y},{X, Y2},{Y, X2}or {X2, XY, Y2}.

If LM(Gc) = {1}, thenh(X, Y)∈ϕ1(L(∞ · ∞ −(E1+E2))) if and only if h(X, Y) is divisible by G1 and by G2. Thus the reduced Groebner basis H is easily computed. For example, if f1(X, Y) = g1(X, Y), then h1(X, Y) =f1(X, Y)∈H.

If LM(Gc) = {X, Y},{X, Y2} or {Y, X2}, then E1 =P1+P2+P3 is obtained by Gc and (1). Thus G can be obtained by (P1− ∞) + ((P2− ∞) + ((P3− ∞) +D2)).

If LM(Gc) = {X2, XY, Y2}, then D1 = D2. In the case of A1 = 0, E1 = (A2 B1,−B2) + (−A2, β1) + (−A2, β2) for the roots β1, β2 ofY2+A3Y −B3A2+C3 = 0. Thus Gcan be obtained by (A2−B1,−B2)− ∞+ ((−A2, β1)− ∞+ ((−A2, β2)− ∞+D2)).In the case of A1 = 0, to avoid using a cubic equation, we use the method given in Section 4.4 with the S-polynomials whose number is 7 at most.

From now on, we consider the general case f1, f2, f3, f1 −g1, f2 −g2, f3−g3 = 1. Let

M(G1, G2) =

A1−a1 A2−a2 A3−a3 B1−b1 B2−b2 B3−b3 C1−c1 C2−c2 C3−c3

.

Assume that detM(G1, G2)= 0. Then the elements of H are h1(X, Y) = (X+k1)f1+k2f2+k3f3, h2(X, Y) = k4f1+ (X+k5)f2+k6f3, h3(X, Y) = k7f1+k8f2+ (X+k9)f3

and the remainder of F(X, Y) on division by {h1(X, Y), h2(X, Y), h3(X, Y)} for ki K such that

k1 k2 k3

= M(G1, G2)1

a2(A1−a1) +a1(B1−b1)

b2(A1−a1) +b1(B1−b1)(C1−c1) c2(A1−a1) +c1(B1 −b1)

,

k4 k5 k6

= M(G1, G2)1

a2(A2−a2) +a1(B2−b2)

b2(A2−a2) +b1(B2−b2)(C2−c2) c2(A2−a2) +c1(B2 −b2)

,

k7 k8 k9

= M(G1, G2)1

a2(A3−a3) +a1(B3−b3)

b2(A3−a3) +b1(B3−b3)(C3−c3) c2(A3−a3) +c1(B3 −b3)

.

SinceD = (h1)(D1+D2) is a normal divisor with the pole degree 3, we have a unique polynomial v1 K[X, Y] with LT(v1) = X2 such that v1hi ∈ h1, F for all hi H.

{h1, F} is a Groebner basis for h1, Fsince lcm(LM(h1),LM(F)) = LM(h1)LM(F). For the polynomials v1, q2,1, q2,2, q3,1, q3,2 ∈K[X, Y] such that

v1h2 = q2,1h1+q2,2F, v1h3 = q3,1h1+q3,2F

with LT(v1) = X2,LT(q2,1) = XY,LM(q2,2) X,LT(q3,1) =Y2,LM(q3,2) Y, we have G={v1, v2 =q2,1−c2,1v1, v3 =q3,1−c3,2v2−c3,1v1}, where c2,1 is the coefficient of X2 in q2,1 and c3,1, c3,2 are the coefficients ofX2, XY inq3,1, respectively.

Example

Let C be aC34 curve defined over F11 =Z/11Z by F(X, Y) = Y3+X4 + 1.

LetD1, D2be the normal divisors with the reduced Groebner basesG1, G2for their normal ideals, respectively:

G1 ={f1 =X2+ 8Y + 9X+ 9, f2 =XY + 4Y + 9X+ 8, f3 =Y2+ 9Y + 9X+ 1}, G2 ={g1 =X2+ 10Y + 7X+ 7, g2 =XY + 2Y + 4X+ 6, g3 =Y2+ 7Y + 9X+ 2}. Then f1, f2, f3, f1 −g1, f2 −g2, f3 −g3=1. For G1 and G2, we have

M(G1, G2) =

9 2 2 2 5 0 2 2 10

with detM(G1, G2)= 0.

Thus the elements of H are

h1(X, Y) = (X+k1)f1+k2f2+k3f3, h2(X, Y) = k4f1+ (X+k5)f2+k6f3, h3(X, Y) = k7f1+k8f2+ (X+k9)f3

and the remainder ofF(X, Y) on division by{h1(X, Y), h2(X, Y), h3(X, Y)}for

k1 k2 k3

=

6 5 9

,

k4 k5 k6

=

6 8 3

,

k7 k8 k9

=

1 8 6

.

It follows that

h1 = X3+ 9Y2+ 2XY + 4X2+ 6Y + 2X+ 4, h2 = X2Y + 3Y2 +XY + 4X2+ 8Y + 7X, h3 = XY2+ 6Y2 + 6XY + 10X2+ 6Y + 4X+ 2.

From

v1h2 = q2,1h1+q2,2F, v1h3 = q3,1h1+q3,2F

with LM(v1) =X2,LT(q2,1) =XY,LM(q2,2)≤X,LT(q3,1) = Y2,LM(q3,2)≤X, we have v1 = X2+ 3Y + 10X+ 10,

q2,1 = XY + 9X2+ 3X+ 6, q2,2 = 2X+ 9,

q3,1 = Y2+ 9XY + 3X2+ 8Y + 3X+ 9, q3,2 = 2Y + 8X+ 6.

It follows that

G={v1 =X2+ 3Y + 10X+ 10, v2 =XY + 6Y +X+ 4, v3 =Y2 + 8X+ 9}.

Bibliography

[1] L. M. Adleman, J. DeMarrais and M. D. Huang, A subexponential Algorithm for Discrete Logarithms over the Rational Subgroup of the Jacobians of Large Genus Hyperelliptic Curves over Finite Fields, Algorithmic Number Theory, 28–40, Lecture Notes in Comput. Sci. 877, Springer-Verlag, Berlin, 1994.

[2] S. Arita, Algorithms for computation in Jacobian group of Cab curve and their ap- plication to discrete-log-based public key cryptosystems, The mathematics of public key cryptography, Fields Institute A. Odlyzko et al (eds.), 1999.

[3] D. G. Cantor, Computing in the Jacobian of a hyperelliptic curve, Math. Comp. 48 (1987), 95–101.

[4] D. G. Cantor, On the analogue of the division polynomials for hyperelliptic curves, J. Reine Angew. Math. 447 (1994), 91–145.

[5] D. Cox, J. Little and D. O’shea, Ideals, Varieties, and Algorithms, Springer-Verlag, Berlin, 1997.

[6] W. Fulton, Algebraic Curves, Benjamin, New York, 1969.

[7] S. D. Galbraith, S. M. Paulus and N. P. Smart, Arithmetic on Superelliptic Curves, Math. Comp. 71 (2002), 393–405.

[8] V. D. Goppa,Geometry and Codes, Kluwer Academic Publishers, 1988.

[9] R. Harley,adding.text, http://cristal.inria.fr/˜harley/hyper/, 2000.

[10] R. Harley,doubling.c, http://cristal.inria.fr/˜harley/hyper/, 2000.

[11] R. Hartshorne, Algebraic Geometry, Springer-Verlag, 1977.

[12] M. -D. Huang and D. Ierardi, Efficient algorithms for the effective Riemann-Roch problem and for addition in the Jacobian of a curve, J. Symbolic Comp. 18 (1994), 519–539.

[13] H. Kim, J. Cheon and S. Hahn, Elliptic curve lifting problem and its applications, Proc. Japan Acad. 75 Ser. A (1999), 166–168.

[14] N. Koblitz, Elliptic Curve Cryptosystems, Math. Comp. 48 (1987), 203–209.

[15] N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), 139–150.

[16] N. Koblitz, A course in number theory and cryptography, 2nd ed., Grad. Texts in Math. 114, Springer-Verlag, New York, 1994.

[17] N. Koblitz, Algebraic Aspects of Cryptograph, Springer-Verlag, 1998.

[18] R. Matsumoto, The Cab curve - a generalization of the Weierstrass form to arbitrary plane curves, http://www.rmatsumoto.org/cab/html.

[19] K. McCurley, The Discrete Logarithm Problem (Boulder, CO, 1989), 49–74, Proc.

Sympos. Appl. Math. 42, Amer. Math. Soc., Proridence, RI, 1990.

[20] A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Acad. Publ., 1993.

[21] A. Menezes, T. Okamoto and S. A. Vanstone, Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field, IEEE Trans. Inform. Theory 39 (1993), 1639–1646.

[22] V. Miller, Uses of elliptic curves in cryptography, Advances in Cryptology-Proc.

Crypto ’85 (Santa Barbara, Calif., 1985), 417–426, Lecture Notes in Comput. Sci.

218, Springer-Verlag, New York, 1986.

[23] S. Miura, Algebraic geometric codes on certain plane curves, Trans. IEICE J75-A (1992), 1735–1745 (Japanese).

[24] S. Miura, Linear codes on affine algebraic curves, Trans. IEICE J81-A (1998), 1398–1421 (Japanese).

[25] Y. Morita, Seisuron, Tokyo Univ. Press, 1999 (Japanese).

ドキュメント内 PDF www.math.tohoku.ac.jp (ページ 44-76)

関連したドキュメント