Computing modular polynomials in quasi-linear time

Andreas Enge 1, 2, 3
1 LFANT - Lithe and fast algorithmic number theory
IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : We analyse and compare the complexity of several algorithms for computing modular polynomials. We show that an algorithm relying on floating point evaluation of modular functions and on interpolation, which has received little attention in the literature, has a complexity that is essentially (up to logarithmic factors) linear in the size of the computed polynomials. In particular, it obtains the classical modular polynomials $\Phi_\ell$ of prime level $\ell$ in time O (\ell^3 \log^4 \ell \log \log \ell). Besides treating modular polynomials for $\Gamma^0 (\ell)$, which are an important ingredient in many algorithms dealing with isogenies of elliptic curves, the algorithm is easily adapted to more general situations. Composite levels are handled just as easily as prime levels, as well as polynomials between a modular function and its transform of prime level, such as the Schläfli polynomials and their generalisations. Our distributed implementation of the algorithm confirms the theoretical analysis by computing modular equations of record level around $10000$ in less than two weeks on ten processors.
Type de document :
Article dans une revue
Mathematics of Computation, American Mathematical Society, 2009, 78 (267), pp.1809-1824
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00143084
Contributeur : Andreas Enge <>
Soumis le : mercredi 23 juillet 2008 - 14:21:55
Dernière modification le : jeudi 11 janvier 2018 - 06:22:36
Document(s) archivé(s) le : mardi 21 septembre 2010 - 17:35:11

Fichiers

modcomp.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00143084, version 2
  • ARXIV : 0704.3177

Collections

Citation

Andreas Enge. Computing modular polynomials in quasi-linear time. Mathematics of Computation, American Mathematical Society, 2009, 78 (267), pp.1809-1824. 〈inria-00143084v2〉

Partager

Métriques

Consultations de la notice

455

Téléchargements de fichiers

275