Title Computing the genus of an algebraic curve. Version française


BP 93, 06902 France


Manuel Bronstein


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.


Unix workstation,  a computer algebra system (Axiom or Maple),  then Aldor programming language.


3 - 4 months, possible prolongation as a doctoral thesis if desired.


October 16, 2001