Computing Hilbert class polynomials with the Chinese Remainder Theorem

Details Computing Hilbert class polynomials with the Chinese Remainder Theorem Computing Hilbert class polynomials with the Chinese Remainder Theorem

2009-03-16

arxiv.org/abs/0903.2785v3

Math. Comp. 80 (2011), 501-538

Mathematics

Number Theory

37 pages, minor typographical changes, to appear in Mathematics of Computation

Scientific paper

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(|D|^(1/2+o(1))log P) space and has an expected running time of O(|D|^(1+o(1)). We describe practical optimizations that allow us to handle larger discriminants than other methods, with |D| 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.

Affiliated with

Also associated with

No associations

Rating

Computing Hilbert class polynomials with the Chinese Remainder Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing Hilbert class polynomials with the Chinese Remainder Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Hilbert class polynomials with the Chinese Remainder Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-224119