Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computing Hilbert class polynomials with the Chinese remainder theorem

Author: Andrew V. Sutherland
Journal: Math. Comp. 80 (2011), 501-538
MSC (2010): Primary 11Y16; Secondary 11G15, 11G20, 14H52
Published electronically: May 17, 2010
MathSciNet review: 2728992
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present a space-efficient algorithm to compute the Hilbert class polynomial $ H_D(X)$ modulo a positive integer $ P$, based on an explicit form of the Chinese Remainder Theorem. Under the Generalized Riemann Hypothesis, the algorithm uses $ O(\vert D\vert^{1/2+\epsilon}\log{P})$ space and has an expected running time of $ O(\vert D\vert^{1+\epsilon})$. We describe practical optimizations that allow us to handle larger discriminants than other methods, with $ \vert D\vert$ as large as $ 10^{13}$ and $ h(D)$ up to $ 10^{6}$. We apply these results to construct pairing-friendly elliptic curves of prime order, using the CM method.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 11G15, 11G20, 14H52

Retrieve articles in all journals with MSC (2010): 11Y16, 11G15, 11G20, 14H52

Additional Information

Andrew V. Sutherland
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Received by editor(s): March 3, 2009
Received by editor(s) in revised form: September 10, 2009
Published electronically: May 17, 2010
Article copyright: © Copyright 2010 by the author

American Mathematical Society