A quasi-linear time algorithm for computing modular polynomials in dimension 2

Enea Milio 1, 2
1 LFANT - Lithe and fast algorithmic number theory
IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : We propose to generalize the work of Régis Dupont for computing modular polynomials in dimension 2 to new invariants. We describe an algorithm to compute modular polynomials for invariants derived from theta constants and prove under some heuristics that this algorithm is quasi-linear in its output size. Some properties of the modular polynomials defined from quotients of theta constants are analyzed. We report on experiments with our implementation.
Type de document :
Article dans une revue
LMS Journal of Computation and Mathematics, London Mathematical Society, 2015, 18, pp.603-632


https://hal.archives-ouvertes.fr/hal-01080462
Contributeur : Enea Milio <>
Soumis le : jeudi 2 juillet 2015 - 15:03:18
Dernière modification le : mardi 13 décembre 2016 - 15:41:38

Fichier

QuasiLinAlgModPol-Version 2.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Copyright (Tous droits réservés)

Identifiants

  • HAL Id : hal-01080462, version 3

Collections

Citation

Enea Milio. A quasi-linear time algorithm for computing modular polynomials in dimension 2. LMS Journal of Computation and Mathematics, London Mathematical Society, 2015, 18, pp.603-632. <hal-01080462v3>

Partager

Métriques

Consultations de
la notice

125

Téléchargements du document

68