| Title Computing the genus of an algebraic curve. | Version
française |
Location
INRIA, Project
CAFÉ
BP 93, 06902 France
Information
Description
The genus of an algebraic curve is a fundamental quantity that several
algorithms in cryptography or computer algebra depend on. Computing it,
which is often a preliminary step for other algorithms, remains difficult
for general curves. Last year, an intern implemented
the new method [3], which is based on Hurwitz' formula and uses an ordinary
linear differential operator associated with the curve. An experimental
method based on a differential system of the form Y' = A(x) Y and
the reduction of [1] to compute its exponents was also implemented [4]
and found to be faster that the method of [3], but still more expensive
than local desingularisation. A new improvement of that method that first
computes a suitable basis of the associated algebraic function field
using the algorithm of [2] and then the corresponding explicitely regular
differential system W' = B(x) W to compute the ramification
indices is to be implemented and compared to the previous work. This method
is expected to be competitive with the fastest known algorithms, and to
be applicable to other computations, such as absolute factorization (decomposition
of the curve) and computation of the Galois group of the polynomial defining
the curve.
It is possible to continue this work towards a doctoral thesis around
the above applications, together with a generalization to hypersurfaces
in higher dimensions using systems of linear partial differential
equations rather than ordinary equations.
[1] S.Abramov and M.Bronstein (2001): On Solutions of Linear Functional Systems, in Proceedings of ISSAC'2001, London (Ontario), ACM Press, pp.1-6.
[2] M.Bronstein (1998): The Lazy Hermite Reduction, INRIA Research Report 3562.
[3] O.Cormier, M.Singer, B.Trager and F.Ulmer (2001): Linear Differential Operators for Polynomial Equations, manuscript submitted to the Journal of Symbolic Computation.
[4] E.Dottax (2001): Calcul du genre d'une courbe algébrique, Rapport de stage INRIA.
Tools
Unix workstation, a computer algebra system (Axiom or Maple), then Aldor programming language.
Duration
3 - 4 months, possible prolongation as a doctoral thesis if desired.