Sur le calcul efficace des polynômes de Cantor de division

par Dr Elie Eid (Univ. Rennes 1)

jeudi 17 mars 2022, 10:30 → 11:30 Europe/Paris

https://bbb.unilim.fr/b/vac-m6r-7dv

Le calcul des polynômes (de Cantor) de division est une étape essentielle dans les algorithmes de Schoof et de Pila pour le comptage de points sur les courbes (hyper)elliptiques définies sur des corps finis et leurs Jacobiennes.
Les algorithmes classiques pour calculer ces polynômes sont généralement basés sur les formules récursives de Cantor ou un algorithme plus directe qui applique les opérations d’addition de la Jacobienne sur un point générique. Bien qu'ils présentent un temps d'exécution acceptable en pratique, leur complexité théorique n'a pas encore été bien étudiée et les expériences montrent qu'ils deviennent beaucoup plus lents lorsque leurs degrés ou le genre de la courbe deviennent plus élevés.
Dans cet exposé, je présenterai une méthode efficace pour les calculer, basée sur la résolution d’équations différentielles non linéaires.