Computing Hilbert Class Polynomials

Juliana Belding, Reinier Bröker, Andreas Enge, Kristin E. Lauter

TL;DR

This paper introduces and analyzes two new algorithms for computing Hilbert class polynomials, which are fundamental objects in number theory with applications in cryptography. The key innovation is an efficient p-adic lifting algorithm for "inert" primes, which are typically harder to work with than "split" primes, and an improved Chinese Remainder Theorem approach that unifies these cases.

What Problem Does This Paper Address?

The Hilbert class polynomial $H_D$ is the minimal polynomial of the $j$-invariant of complex elliptic curves associated with a specific imaginary quadratic order of discriminant $D$. Computing $H_D$ is crucial for explicit class field theory and has direct applications in areas like elliptic curve primality proving and cryptography, particularly in pairing-based cryptography. While algorithms exist, they often struggle with "inert" primes (primes that don't split nicely in the number field associated with the order), which are often smaller and more numerous than "split" primes. This paper aims to provide efficient algorithms that handle both inert and split primes, offering tighter complexity bounds and a unified approach.

Methods

The paper presents two main algorithmic approaches:

  • p-adic Lifting Algorithm for Inert Primes: This is the core novelty. Instead of relying on primes that split completely in the ring class field (which are typically larger), this algorithm works with inert primes. It leverages the fact that for inert primes, the roots of $H_D$ modulo $p$ correspond to $j$-invariants of supersingular elliptic curves. The algorithm involves computing a canonical lift of a supersingular elliptic curve from characteristic $p$ to the $p$-adic numbers and then using a modified Newton's method to converge to the $j$-invariant.
  • Improved Chinese Remainder Theorem (CRT) Approach: This algorithm combines computations modulo several primes (both inert and split) to reconstruct the full Hilbert class polynomial. The improvement lies in incorporating the new algorithm for inert primes and using the class group action on complex multiplication (CM) curves over finite fields to speed up computations for split primes.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and their complexity analysis, with examples provided to illustrate the algorithms rather than using large-scale datasets.

Key Insights and Ideas

  • Unified Treatment of Primes: The paper successfully bridges the gap between algorithms for split primes and the more challenging case of inert primes, offering a more comprehensive computational tool.
  • Supersingular Curves for Inert Primes: The insight that inert primes relate to supersingular elliptic curves is key. This connection allows for the use of $p$-adic lifting techniques, which are typically applied to ordinary elliptic curves.
  • Class Group Action as a Tool: The paper effectively uses the action of the class group on sets of elliptic curves (both over finite fields and in the $p$-adic setting) to generate all necessary $j$-invariants, rather than relying on exhaustive searches.
  • Tighter Complexity Bounds: The analysis provides improved, and in some cases heuristic, complexity bounds for computing Hilbert class polynomials, offering a clearer picture of the efficiency of different methods.

Key Results

  • Algorithm 1: A multi-prime CRT algorithm that computes $H_D$ for a discriminant $D < 0$. Under GRH, it achieves an expected run time of $O(|D|(\log |D|)^{7+o(1)})$, with a heuristic complexity of $O(|D|(\log |D|)^{3+o(1)})$.
  • Algorithm 2 (Split Primes): An algorithm for computing $H_D \pmod p$ when $p$ splits completely in the ring class field.
  • Algorithm 3 (Inert Primes): A novel $p$-adic lifting algorithm for computing $H_D \pmod p$ when $p$ is inert.
  • Theoretical Bounds: The paper provides new bounds on the size of coefficients of $H_D$ and the primes needed for the CRT approach, depending on the discriminant $D$, class number $h(D)$, and logarithmic height $n$.

Limitations and Future Work

  • Heuristic Assumptions: The tighter complexity bounds rely on heuristic assumptions (e.g., about the distribution of primes and the behavior of algorithms) and the Generalized Riemann Hypothesis (GRH).
  • Practical Constants: While theoretical complexity is improved, the paper notes that the implicit constants in the $O$-notation might be larger for the CRT approach compared to the complex analytic method, as observed in an example.
  • Specific Cases: The $p$-adic lifting algorithm has a technical condition ($p \equiv 1 \pmod{12}$) for simplicity, with the cases where $j$-values 0 or 1728 are roots of $H_D \pmod p$ requiring more detailed treatment (deferred to the first author's PhD thesis).
  • Future Work: The paper suggests exploring the use of "class invariants" (smaller functions than $j$-invariants) to potentially improve efficiency, though theoretical obstructions exist for incorporating them into the CRT approach. Further practical implementation and comparison of the algorithms would be valuable.

Summary updated

BibTeX
@article{belding2008computing,
  author = {Juliana Belding and Reinier Bröker and Andreas Enge and Kristin E. Lauter},
  title = {{Computing Hilbert Class Polynomials}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2008},
}
Figure