Treffer: Computing modular polynomials in quasi-linear time

Title:
Computing modular polynomials in quasi-linear time
Authors:
Enge, Andreas
Contributors:
Lithe and fast algorithmic number theory (LFANT), Institut de Mathématiques de Bordeaux (IMB), Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Centre Inria de l'Université de Bordeaux, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Algorithmic number theory for cryptology (TANC), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X), Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre National de la Recherche Scientifique (CNRS)-Centre Inria de Saclay, Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)
Source:
Mathematics of Computation. 78(267):1809-1824
Publisher Information:
CCSD; American Mathematical Society, 2009.
Publication Year:
2009
Collection:
collection:X
collection:CNRS
collection:INRIA
collection:IMB
collection:LIX
collection:INRIA-BORDEAUX
collection:INRIA-SACLAY
collection:X-LIX
collection:X-DEP
collection:X-DEP-INFO
collection:INRIA_TEST
collection:TESTALAIN1
collection:INRIA2
collection:UNIVERSITE-BORDEAUX
collection:DEPARTEMENT-DE-MATHEMATIQUES
Subject Terms:
ACM: G.: Mathematics of Computing, G.4: MATHEMATICAL SOFTWARE, G.4.0: Algorithm design and analysis, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.1: Numerical Algorithms and Problems, F.2.1.4: Number-theoretic computations (e.g., factoring, primality testing), [MATH.MATH-NT]Mathematics [math], Number Theory [math.NT], [INFO.INFO-CC]Computer Science [cs], Computational Complexity [cs.CC]
Original Identifier:
ARXIV: 0704.3177
HAL:
Document Type:
Zeitschrift article<br />Journal articles
Language:
English
ISSN:
0025-5718
1088-6842
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/0704.3177
Access URL:
https://inria.hal.science/inria-00143084
https://inria.hal.science/inria-00143084v2/document
https://inria.hal.science/inria-00143084v2/file/modcomp.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00143084v2
Database:
HAL

Weitere Informationen

To appear in Mathematics of Computation.
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.