| Titre Calcul du genre d'une courbe algébrique. | English
version |
Lieu
INRIA, Projet
CAFÉ
BP 93, 06902 France
Information
Description
Le genre d'une courbe algébrique est une quantité fondamentale
dont dépendent beaucoup d'algorithmes en cryptographie et en calcul
formel. Son calcul, qui est souvent une étape préalable pour
d'autres algorithmes, reste difficile en général. L'objet
d'un stage de l'année dernière a été d'implanter
une nouvelle méthode [3], basée sur la formule de Hurwitz
et qui utilise un opérateur différentiel linéaire
associé à la courbe. De plus, une méthode expérimentale
basée sur un système différentiel de la forme Y'
= A(x) Y et l'algorithme de [1] pour calculer ses exposants a aussi
été implantée [4] et montrée plus rapide que
celle de [3], mais encore plus chère que la désingularisation
locale. L'objet de ce stage est d'implémenter une amélioration
de cette méthode, qui calcule d'abord une base appropriée
(suitable basis) du corps de fonctions algébriques avec l'algorithme
de [2], puis le système différentiel explicitement régulier
W' = B(x) W afin de déterminer les indices de ramification,
et de comparer cette méthode aux précédentes. On s'attend
à ce que cette méthode soit compétitive avec les plus
rapides connues, mais aussi qu'elle puisse s'appliquer à d'autres
calculs tels que la factorisation absolue et la détermination du
groupe de Galois du polynôme définissant la courbe.
Une continuation en thèse est possible autour de ces applications,
ainsi que de leur extensions aux hypersurfaces en utilisant des systèmes
d'équations différentielles linéaires partielles
plutôt qu'ordinaires.
[1] S.Abramov et 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, Rapport de Recherche INRIA 3562.
[3] O.Cormier, M.Singer, B.Trager et 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.
Outils
Station de travail Unix, système de calcul formel (Axiom ou Maple) et langage de programmation Aldor.
Durée
3-4 mois, niveau DEA, continuation possible en thèse d'informatique ou de mathématiques.