IEICE TRANS. FUNDAMENTALS, VOL.E82–A, NO.3 MARCH 1999

551

LETTER

Using Cab Curves in the Function Field Sieve
Ryutaroh MATSUMOTO† , Member

SUMMARY
In Adleman’s Function Field Sieve algorithm
solving the discrete logarithm problem in a ﬁnite ﬁeld, it is assumed that a random bivariate polynomial in the certain classis absolutely irreducible with high probability. In this letter wepoint out that if we use Cab type random polynomials then wealways get absolutely irreducible polynomials. We can also simplify the calculation of a product of many rational functions on
a curve that belongs to the ﬁeld of deﬁnition by the use of a Cab
curve.
key words: discrete logarithm problem, function field sieve, Cab
curve

Adleman proposed the Function Field Sieve (FFS)
algorithm [1] solving the discrete logarithm problem inthe multiplicative group of a ﬁnite ﬁeld IFpn with pnelements for a prime p relatively small to the extension degree n. Suppose that IFpn is deﬁned by a irreducible polynomial f (x) ∈ IFp [x] of degree n. In theFFS we ﬁrst choose a random polynomial m(x) ∈ IFp [x]of certain degree, then ﬁnd a bivariate polynomiald d −1
i jH(x, y) =i=0
j=0 hi,j y x ∈ IFp [x, y] satisfying
the following 8 conditions:
1. H is absolutely irreducible.
2. H(x, m) is divisible by f .
3. hd,d −1 = 1.
di4.
i=0 hi,d −1 y ∈ IFp [y] is square-free.
5. h0,d −1 = 0.
d −1j6.
j=0 hd,j x ∈ IFp [x] is square-free.
7. hd,0 = 0.
8. The order of the Jacobian of the curve deﬁned by
H(x, y) is relatively prime to (pn − 1)/(p − 1).
In the running time analysis Adleman assumed that wecan ﬁnd an absolutely irreducible polynomial satisfying
the conditions above with suﬃciently high probability,
and the assumption was not veriﬁed rigorously. Thatassumption is easily satisﬁed if we use a Cab curve.
Proposition-Definition 1: [2, Proposition 12] [3],[4] Let K be a perfect ﬁeld, K̄ the algebraic closureof K, χ ⊂ K̄ 2 be a possibly reducible aﬃne algebraic
set deﬁned over K, x, y be the coordinates of the aﬃnespace, and a, b relatively prime positive integers. Thenthe following conditions are equivalent.
Manuscript received September 30, 1998.
The author is in the Sakaniwa Lab., the Department of Electrical and Electronic Engineering, Tokyo Institute of Technology, Tokyo, 152–8552 Japan. E-mail:ryutaroh@ss.titech.ac.jp†• χ is an absolutely irreducible aﬃne algebraic curvewith exactly one K-rational place Q at inﬁnity,and the pole divisors of x and y are aQ and bQrespectively.
• χ is deﬁned by a bivariate polynomial of form
αi,j xi y j,G(x, y) := αb,0 xb + α0,a y a +ia+jb<ab(1)where αi,j ∈ K for all i, j and αb,0 , α0,a arenonzero.
A plane algebraic curve deﬁned by a bivariate polynomial of form (1) is said to be a Cab curve.
A K-basis of the aﬃne coordinate ring K[x, y]/(G(x, y)) of a Cab curve is{xi y j | 0 ≤ i, 0 ≤ j ≤ a − 1},and elements in the basis have pairwise distinct discrete
valuations at Q.
Any algebraic curve deﬁned over a perfect ﬁeld K
that has at least one K-rational place is birationally✷equivalent to a Cab curve deﬁned over K.
If we use a polynomial of form (1) in the FFS thenthe absolute irreducibility condition is always satisﬁed.
An algebraic curve used in the FFS is assumed to haveat least one IFp -rational place, and using Cab curves in
the FFS does not narrow the class of curves used in theFFS.
Proposition 2: Let z be a nonzero rational function
on an absolutely irreducible algebraic curve deﬁned overa perfect ﬁeld K and Q a place in the curve. Thenz ∈ K iﬀ vP (z) = 0 for all place P = Q in the curve,
where vP (z) denotes the discrete valuation of z at aplace P .
Proof: The assertion follows from [6, Corollary 1.1.19,
Theorem 1.4.11 and Corollary 3.6.7].
✷In the FFS we deal with an absolutely irreducible
curve deﬁned over the ﬁeld IFp and we have to ﬁnd a
product of many rational functions belonging to IFp . To
ﬁnd such a product in Adleman’s original method, wecompute the discrete valuation of each rational function
at all place, including places at inﬁnity, then solve thesystem of linear equations. If we use a Cab curve thenwe do not have to calculate the discrete valuation at

IEICE TRANS. FUNDAMENTALS, VOL.E82–A, NO.3 MARCH 1999

552

inﬁnity, because a Cab curve has exactly one place at
inﬁnity, and we can remove the conditions 3, 4, and 6that simplify calculation of the discrete valuations atinﬁnity. Note that we can easily calculate the discrete
valuation of a rational functions on a Cab curve at theplace at inﬁnity by the division algorithm of a Gröbner
basis [5, Proposition 14], [4, Appendix C].
To ﬁnd a polynomial H(x, y) of form (1) satisfying
the condition 2, let
αi,j xi y j ,H(x, y) := αb,0 xb + α0,a y a +ia+jb<aband g(x) := H(x, m(x)) mod f (x). g(x) = 0 gives thesystem of n linear equations in variables αi,j . Substituting αi,j in H(x, y) with a solution gives a desiredpolynomial.

References[1] L.M. Adleman, “The function ﬁeld sieve,” Proc. Algorithmic Number Theory Symposium, Lect. Notes in Comp. Sci.,
vol.877, pp.108–121. Springer-Verlag, 1995.
[2] T. Høholdt, J.H. van Lint, and R. Pellikaan, “Order functions and evaluation codes,” Proc. AAECC-12, Lect. Notesin Comp. Sci., vol.1255, pp.138–150, 1997.
[3] S. Miura, “Algebraic geometric codes on certain planecurves,” IEICE Trans., vol.J75-A, no.11, pp.1735–1745, Nov.
1992.
[4] S. Miura, “Linear codes on aﬃne algebraic curves,” IEICE
Trans., vol.J81-A, no.10, pp.1398–1421, Oct. 1998.
[5] K. Saints and C. Heegard, “Algebraic-geometric codes andmultidimensional cyclic codes: A uniﬁed theory and algorithms for decoding using gröbner bases,” IEEE Trans. Inf.
Theory, vol.41, no.6, pp.1733–1751, Nov. 1995.
[6] H. Stichtenoth, “Algebraic Function Fields and Codes,”Springer-Verlag, Berlin, 1993.