|
Arithmetic on superelliptic curves
Author(s):
S.
D.
Galbraith;
S.
M.
Paulus;
N.
P.
Smart.
Journal:
Math. Comp.
71
(2002),
393-405.
MSC (2000):
Primary 14Q05, 14H40, 11G20, 11Y16
Posted:
October 26, 2000
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
This paper is concerned with algorithms for computing in the divisor class group of a nonsingular plane curve of the form  which has only one point at infinity. Divisors are represented as ideals, and an ideal reduction algorithm based on lattice reduction is given. We obtain a unique representative for each divisor class and the algorithms for addition and reduction of divisors run in polynomial time. An algorithm is also given for solving the discrete logarithm problem when the curve is defined over a finite field.
References:
-
- 1.
- L. Adleman, J. De Marrais, 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.
In ANTS-1 : Algorithmic Number Theory, L. Adleman and M.-D. Huang, editors. Springer-Verlag, LNCS 877, 1994. MR 96b:11078 - 2.
- S. Arita.
Algorithms for computations in Jacobian group of  curve and their application to discrete-log-based public key cryptosystems.
in The mathematics of public key cryptography, Fields Institute A. Odlyzko et al (eds.), 1999. - 3.
- E. R. Barreiro, J.-P. Cherdieu and J. E. Sarlabous.
Efficient reduction on the Jacobian variety of Picard curves.
in Coding theory, cryptography and related areas, J. Buchmann et al (eds.), Springer, 2000. - 4.
- D.G. Cantor.
Computing in the Jacobian of a hyperelliptic curve.
Math. Comp., 48, 95-101, 1987. MR 88f:11118 - 5.
- J. Coates.
Construction of rational functions on a curve.
Proc. Cam. Phil. Soc., 68, 105-123, 1970. MR 41:3477 - 6.
- H. Cohen.
A Course in Computational Algebraic Number Theory.
Springer-Verlag, GTM 138, 1993. MR 94i:11105 - 7.
- R. Flassenberg and S. Paulus.
Sieving in function fields.
Experimental Mathematics, 8, No. 4, 339-349, 1999. CMP 2000:07 - 8.
- W. Fulton.
Algebraic Curves.
Benjamin, 1969. - 9.
- F. Hess.
Zur divisorenklassengruppenberechnung in globalen funktionenkörpern.
Thesis, T-U Berlin 1999. - 10.
- M.-D. Huang and D. Ierardi.
Efficient algorithms for the Riemann-Roch problem and for addition in the jacobian of a curve.
J. Symbolic Comp., 18, 519-539, 1994. MR 96h:14077 - 11.
- A. Lenstra.
Factoring multivariate polynomials over finite fields.
J. Computer and Systems Science, 30, 235-248, 1985. MR 87a:11124 - 12.
- K. Mahler.
An analogue to Minkowski's geometry of numbers in a field of series.
Ann. Math., 42, 488-522, 1941. MR 2:350c - 13.
- J. Neukirch.
Algebraische Zahlentheorie.
Springer, 1990. MR 92a:01057 - 14.
- V. Müller, A. Stein and C. Thiel.
Computing discrete logarithms in real quadratic function fields of large genus.
Math. Comp., 68, 807-822, 1999. MR 99i:11119 - 15.
- S. Paulus.
Lattice basis reduction in function fields.
In ANTS-3 : Algorithmic Number Theory, J. Buhler, editor. Springer-Verlag, LNCS 1423, 567-575, 1998. CMP 2000:05 - 16.
- S. Paulus and H.-G. Rück.
Real and imaginary quadratic representations of hyperelliptic function fields.
Math. Comp., 68, 1233-1241, 1999. MR 99i:11107 - 17.
- M. Pohst and M. Schörnig.
On integral basis reduction in global function fields.
In ANTS-2 : Algorithmic Number Theory, H. Cohen, editor. Springer-Verlag, LNCS 1122, 273-283, 1996. MR 98c:11125 - 18.
- R. Scheidler, A. Stein and H. C. Williams,
Key-exchange in real quadratic congruence function fields.
Designs, Codes and Cryptography., 7, 153-174, 1996. MR 97d:94009 - 19.
- R. Scheidler, A. Stein.
Voronoi's algorithm in purely cubic congruence function fields of unit rank  .
Math. Comp. 69 (2000) 1245-1266. CMP 2000:11 - 20.
- R. Scheidler.
Ideal arithmetic and infrastructure in purely cubic function fields.
Preprint 1999. - 21.
- H. Stichtenoth.
Algebraic function fields and codes.
Springer Universitext, Springer, 1993. MR 94k:14016 - 22.
- E. J. Volcheck.
Computing in the Jacobian of a plane algebraic curve.
In ANTS-1 : Algorithmic Number Theory, L. Adleman and M.-D. Huang, editors. Springer-Verlag, LNCS 877, 221-233, 1994. MR 96a:14033 - 23.
- R. J. Walker.
Algebraic Curves.
New York: Springer 1978. MR 80c:14001
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(2000):
14Q05, 14H40, 11G20, 11Y16
Retrieve articles in all Journals with MSC
(2000):
14Q05, 14H40, 11G20, 11Y16
Additional Information:
S.
D.
Galbraith
Affiliation:
Institute for Experimental Mathematics, Ellernstr. 29, 45326 Essen, Germany
Email:
galbra@exp-math.uni-essen.de
S.
M.
Paulus
Affiliation:
Kopernikusstrasse 15, 69469 Weinheim, Germany
Email:
sachar.paulus@t-online.de
N.
P.
Smart
Affiliation:
Department of Computer Science, University of Bristol, Merchant Venturers Building, Woodland Road, Bristol, BS8 1UB, United Kingdom
Email:
nigel@cs.bris.ac.uk
DOI:
10.1090/S0025-5718-00-01297-7
PII:
S 0025-5718(00)01297-7
Keywords:
Superelliptic curve,
divisor class group,
cryptography,
discrete logarithm problem
Received by editor(s):
April 13, 1999
Received by editor(s) in revised form:
March 17, 2000
Posted:
October 26, 2000
Additional Notes:
The work in this paper was carried out whilst the first author was supported by an EPSRC grant at Royal Holloway University of London, the second author was at Darmstadt University of Technology, and the third author was employed by Hewlett-Packard Laboratories.
Copyright of article:
Copyright
2000,
American Mathematical Society
|
Comments: webmaster@ams.org