Programming ECC

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+bi)(c+di)=ac-bd+((a+b)(c+d)-ac-bd)i$$ saves one multiplication. Similarly, for squaring, one should use $$(a+bi{)}^2=(a+b)(a-b)+2abi$$ 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+\mathrm{bi}$ should be computed as [Numerical Recipes, 5.4] $$\mid a+ib\mid =\{\begin{array}{cc}\mid a\mid \sqrt{1+(b/a{)}^2}& \mid a\mid \ge \mid b\mid \\ \mid b\mid \sqrt{1+(a/b{)}^2}& \mid a\mid <\mid b\mid \end{array}$$ Similarly, division should be implemented as $$\frac{a+ib}{c+id}=\{\begin{array}{cc}\frac{(a+b(d/c))+i(b-a(d/c))}{c+d(d/c)}& \mid c\mid \ge \mid d\mid \\ \frac{(a(c/d)+b)+i(b(c/d)-a)}{c(c/d)+d}& \mid c\mid <\mid d\mid \end{array}$$

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+bxy+c{y}^2$ is a primitive reduced positive definite binary quadratic form of discriminant $-D$. In other words, $b^2-4ac=-D$, $\mid b\mid \le a\le \sqrt{\mid D\mid /3}$, $a\le c$, $\gcd (a,b,c)=1$ and if $\mid b\mid =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$ $\mathrm{mod}4$.

1. Set $P=1,b=D\mathrm{mod}2,B=\lfloor \sqrt{\mid D\mid /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+\mid j{\mid }^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$.