Programming ECC - Hilbert Class Polynomials

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) + 2 a 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{array}{ll} ∣ a ∣ \sqrt{1 + (b / a)^{2}} & ∣ a ∣ \geq ∣ b ∣ \\ ∣ b ∣ \sqrt{1 + (a / b)^{2}} & ∣ a ∣ < ∣ b ∣ \end{array}

Similarly, division should be implemented as

\frac{a + i b}{c + i d} = {\begin{array}{ll} \frac{(a + b (d / c)) + i (b - a (d / c))}{c + d (d / c)} & ∣ c ∣ \geq ∣ d ∣ \\ \frac{(a (c / d) + b) + i (b (c / d) - a)}{c (c / d) + d} & ∣ c ∣ < ∣ d ∣ \end{array}

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

Δ (τ) = q {(1 + \sum_{n \geq 1} (- 1)^{n} (q^{n (3 n - 2) / 2} + q^{n (3 n + 1) / 2}))}^{24}

Then compute

j (τ) = \frac{(256 f (τ) + 1)^{3}}{f (τ)}

where

f (τ) = \frac{Δ (2 τ)}{Δ (τ)}

The Hilbert class polynomial for the discriminant $- D$ is given by $H_{D} (x) = \prod (x - j (α))$ where $α$ runs over all complex numbers such that

α = \frac{- b + \sqrt{- D}}{2 a}

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} - 4 a c = - D$ , $∣ b ∣ \leq a \leq \sqrt{∣ D ∣ / 3}$ , $a \leq c$ , $\gcd (a, b, c) = 1$ and if $∣ b ∣ = a$ or $a = c$ then $b \geq 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$ .

Set $P = 1, b = D \mod 2, B = ⌊ \sqrt{∣ D ∣ / 3} ⌋$
Set $t = (b^{2} + D) / 4$ and $a = \max (b, 1)$
If $a$ does not divide $t$ go to the next step. Otherwise compute $j = j ((- b + \sqrt{- D}) / (2 a))$ . If $a = b$ or $a^{2} = t$ or $b = 0$ set $P = P (X - j)$ otherwise set $P = P (X^{2} - 2 ℜ (j) X + ∣ j ∣^{2})$ .
Set $a = a + 1$ . If $a^{2} \leq t$ go to the previous step.
Set $b = b + 2$ . If $b \leq B$ go to step 2, otherwise round the coefficients of $P$ to the nearest integer and output $P$ .