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

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

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]

Similarly, division should be implemented as

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

Then compute

where

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

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\).