Hilbert Class Polynomials

These require floating point arithmetic to compute [Cohen p415, BSS p151]. Routines for complex numbers need to be written. For multiplication, using a trick similar to Karatsuba multiplication

\[ (a+b i)(c+d i) = a c - b d + ((a+b)(c+d)-a c-b d)i \]

saves one multiplication. Similarly, for squaring, one should use

\[ (a+b i)^2 = (a+b)(a-b) + 2a b i \]

if multiplication is sufficiently less efficient than addition or subtraction.

To minimize the possbility of underflow, overflow or precision loss, the complex modulus of \(a+bi\) should be computed as [Numerical Recipes, 5.4]

\[ |a+i b|= \begin{cases} |a|\sqrt{1 + (b/a)^2} & |a| \ge |b| \\ |b|\sqrt{1 + (a/b)^2} & |a| < |b| \end{cases} \]

Similarly, division should be implemented as

\[ \frac{a+i b}{c + i d} = \begin{cases} \frac{(a + b(d/c)) + i(b - a(d/c))}{c+d(d/c)} & |c| \ge |d| \\ \frac{(a(c/d) + b) + i(b(c/d) - a)}{c(c/d)+d} & |c| < |d| \end{cases} \]

We will need to compute the function \(j(\tau)\) for \(\tau\) in the upper complex plane. Set \(q = e^{2i \pi \tau}\). Define

\[ \Delta(\tau)=q{({ 1 + \sum_{n\ge 1} (-1)^n {({ q^{n(3n-2)/2} + q^{n(3n+1)/2} })} })}^{24} \]

Then compute

\[ j(\tau) = \frac{(256f(\tau)+1)^3}{f(\tau)} \]

where

\[ f(\tau)=\frac{\Delta(2\tau)}{\Delta(\tau)} \]

The Hilbert class polynomial for the discriminant \(-D\) is given by \(H_D(x) = \prod (x-j(\alpha))\) where \(\alpha\) runs over all complex numbers such that

\[ \alpha = \frac{-b+\sqrt{-D}}{2a} \]

where \(a x^2 + b x y + c y^2\) is a primitive reduced positive definite binary quadratic form of discriminant \(-D\). In other words, \(b^2 - 4a c = -D\), \(|b|\le a\le \sqrt{|D|/3}\), \(a\le c\), \(\gcd(a,b,c)=1\) and if \(|b|=a\) or \(a=c\) then \(b\ge 0\).

Thus \(H_D(x)\) can be computed by the following procedure. Let \(P\) be a polynomial variable. Assume \(D\) is \(0\) or \(-1\) \(mod 4\).

  1. Set \(P = 1, b = D mod 2, B = {\lfloor \sqrt{|D| / 3} \rfloor}\)

  2. Set \(t = (b^2 + D)/4\) and \(a = max(b, 1)\)

  3. If \(a\) does not divide \(t\) go to the next step. Otherwise compute \(j = j((-b+\sqrt{-D})/(2a))\). If \(a = b\) or \(a^2 = t\) or \(b = 0\) set \(P = P(X-j)\) otherwise set \(P = P(X^2 - 2 \Re (j) X + |j|^2)\).

  4. Set \(a = a + 1\). If \(a^2 \le t\) go to the previous step.

  5. Set \(b = b + 2\). If \(b \le B\) go to step 2, otherwise round the coefficients of \(P\) to the nearest integer and output \(P\).


Ben Lynn blynn@cs.stanford.edu 💡