number theory
Let the class number $h(d)$ denote the number of distinct binary quadratic forms with discriminant $d < 0$.
Is there a better algorithm for $h$ than brute force?
To be precise, by brute force I meant to generate enough forms to completely cover the space and then reducing them down to see how many equivalence classes there are.
A computer algebra system (CAS) like sage delivers the list of representatives immediately.
https://doc.sagemath.org/html/en/reference/quadratic_forms/sage/quadratic_forms/binary_qf.html
A short answer would be to use this package.
For the reader in hurry, here are the details. For instance, for the mentioned value $-5$ corresponding to the quadratic field $\Bbb Q(\sqrt{-5})$, for the investigations of the structure, we would type in sage:
A, B = BinaryQF_reduced_representatives(-20)
print(f"A = {A}")
print(f"B = {B}")
print("Is A*A == A? {}".format(A*A == A))
print("Is A*B == B? {}".format(B*A == B))
print("Is B*A == B? {}".format(A*B == B))
print("Is B*B == A? {}".format(B*B == A))
BB = B*B
BB_red = BB.reduced_form()
print(f"Which is the reduced form of B*B = {BB}? It is {BB_red}.")
The above code gives as results:
A = x^2 + 5*y^2
B = 2*x^2 + 2*x*y + 3*y^2
Is A*A == A? True
Is A*B == B? True
Is B*A == B? True
Is B*B == A? False
Which is the reduced form of B*B = x^2 + 2*x*y + 6*y^2? It is x^2 + 5*y^2.
At this point a short answer would be to install sage and to ask for the reduced classes in the wanted cases. However, since the code is rather simple, with the risk of filling the whole space of the site...
for D in [1..1000]:
if -D % 4 in [2, 3]:
continue
BQFRR = BinaryQF_reduced_representatives(-D, primitive_only=True)
if len(BQFRR) != 3:
continue
A, B, C = BQFRR
print(f"{-D} & {latex(A)} & {latex(B)} & {latex(C)}\\\\\\hline")
(There is no input of the list from the cited reference. Instead, among all discriminants between $-1000$ and $-3$ there is a computed list of representatives, if there are three quadratic forms in the list, we show them.) The results were copy+pasted inside the following latex array:
$$ \begin{array}{|r||c|c|c|} \hline -D & A & B & C\\\hline\hline -23 & x^{2} + x y + 6 y^{2} & 2 x^{2} - x y + 3 y^{2} & 2 x^{2} + x y + 3 y^{2}\\\hline -31 & x^{2} + x y + 8 y^{2} & 2 x^{2} - x y + 4 y^{2} & 2 x^{2} + x y + 4 y^{2}\\\hline -44 & x^{2} + 11 y^{2} & 3 x^{2} - 2 x y + 4 y^{2} & 3 x^{2} + 2 x y + 4 y^{2}\\\hline -59 & x^{2} + x y + 15 y^{2} & 3 x^{2} - x y + 5 y^{2} & 3 x^{2} + x y + 5 y^{2}\\\hline -76 & x^{2} + 19 y^{2} & 4 x^{2} - 2 x y + 5 y^{2} & 4 x^{2} + 2 x y + 5 y^{2}\\\hline -83 & x^{2} + x y + 21 y^{2} & 3 x^{2} - x y + 7 y^{2} & 3 x^{2} + x y + 7 y^{2}\\\hline -92 & x^{2} + 23 y^{2} & 3 x^{2} - 2 x y + 8 y^{2} & 3 x^{2} + 2 x y + 8 y^{2}\\\hline -107 & x^{2} + x y + 27 y^{2} & 3 x^{2} - x y + 9 y^{2} & 3 x^{2} + x y + 9 y^{2}\\\hline -108 & x^{2} + 27 y^{2} & 4 x^{2} - 2 x y + 7 y^{2} & 4 x^{2} + 2 x y + 7 y^{2}\\\hline -124 & x^{2} + 31 y^{2} & 5 x^{2} - 4 x y + 7 y^{2} & 5 x^{2} + 4 x y + 7 y^{2}\\\hline -139 & x^{2} + x y + 35 y^{2} & 5 x^{2} - x y + 7 y^{2} & 5 x^{2} + x y + 7 y^{2}\\\hline -172 & x^{2} + 43 y^{2} & 4 x^{2} - 2 x y + 11 y^{2} & 4 x^{2} + 2 x y + 11 y^{2}\\\hline -211 & x^{2} + x y + 53 y^{2} & 5 x^{2} - 3 x y + 11 y^{2} & 5 x^{2} + 3 x y + 11 y^{2}\\\hline -243 & x^{2} + x y + 61 y^{2} & 7 x^{2} - 3 x y + 9 y^{2} & 7 x^{2} + 3 x y + 9 y^{2}\\\hline -268 & x^{2} + 67 y^{2} & 4 x^{2} - 2 x y + 17 y^{2} & 4 x^{2} + 2 x y + 17 y^{2}\\\hline -283 & x^{2} + x y + 71 y^{2} & 7 x^{2} - 5 x y + 11 y^{2} & 7 x^{2} + 5 x y + 11 y^{2}\\\hline -307 & x^{2} + x y + 77 y^{2} & 7 x^{2} - x y + 11 y^{2} & 7 x^{2} + x y + 11 y^{2}\\\hline -331 & x^{2} + x y + 83 y^{2} & 5 x^{2} - 3 x y + 17 y^{2} & 5 x^{2} + 3 x y + 17 y^{2}\\\hline -379 & x^{2} + x y + 95 y^{2} & 5 x^{2} - x y + 19 y^{2} & 5 x^{2} + x y + 19 y^{2}\\\hline -499 & x^{2} + x y + 125 y^{2} & 5 x^{2} - x y + 25 y^{2} & 5 x^{2} + x y + 25 y^{2}\\\hline -547 & x^{2} + x y + 137 y^{2} & 11 x^{2} - 5 x y + 13 y^{2} & 11 x^{2} + 5 x y + 13 y^{2}\\\hline -643 & x^{2} + x y + 161 y^{2} & 7 x^{2} - x y + 23 y^{2} & 7 x^{2} + x y + 23 y^{2}\\\hline -652 & x^{2} + 163 y^{2} & 4 x^{2} - 2 x y + 41 y^{2} & 4 x^{2} + 2 x y + 41 y^{2}\\\hline -883 & x^{2} + x y + 221 y^{2} & 13 x^{2} - x y + 17 y^{2} & 13 x^{2} + x y + 17 y^{2}\\\hline -907 & x^{2} + x y + 227 y^{2} & 13 x^{2} - 9 x y + 19 y^{2} & 13 x^{2} + 9 x y + 19 y^{2}\\\hline \end{array} $$
The computations in sage are giving a clear pattern.
In case $-D=-4d$, $d$ positive integer, then $$ \begin{aligned} A &= x^2 + dy^2\ ,\\ B &= ax^2 - 2xy +cy^2\ ,\\ C &= ax^2 + 2xy +cy^2\ ,\\ \end{aligned} $$ for suitable positive integers $a,c$ with $d=ac-1$.
In case $-D=-(4d-3)$, $d$ positive integer, then $$ \begin{aligned} A &= x^2 + xy + dy^2\ ,\\ B &= ax^2 - bxy +cy^2\ ,\\ C &= ax^2 + bxy +cy^2\ ,\\ \end{aligned} $$ for suitable positive integers $a,b,c$ leading to the given discriminant.
Later EDIT: Here i try to answer the questions in the comment below. (Please always ask, do not hesitate.)
In the first part, using the quadratic binary forms (qbf) $A=x^2+5y^2$ and $B=2x^2+2xy+3y^2$ sage computes the composition $B\cdot B=x^2+2xy+6y^2$, which is not exactly $A$, but it is equivalent to $A$. (This is the reason for asking for the reduced representation of $B\cdot B$, which is shown to be $A$.) So as classes we have the expected relation $B\cdot B=A$.
The modulo operation is denoted in python, sage, pari, ... with % - so the in the line with -D % 4 the code computes $-D$ modulo four, else the value is rejected as a discriminant.
Later later EDIT:
The above answers the question of the representative binary quadratic forms (bqf) for the listed discriminant values $-D$. This was the main (and only) question. In the comments there are still some issues related to the primes represented by the principal form $A$. Well, Theorem 1 in loc. cit. already said it all. Here i can only deliver some examples. (Else, theoretically, the book of Cox on the representation of primes by quadratic binary forms would be doubled here.)
So let us consider one of the values in the list, my choice is $-D=-59$. For this number the bqf $A$ is $x^2+xy+15y^2$. Let us see which are the primes represented by $A$ among the first few odd prime values. There will be a table showing the Legendre symbol of $-D$ modulo $p$, the splitting of the polynomial $$f_{-D}=x^3+2x+1$$ considered in $\Bbb F_p[x]$, and the representations of $p$ by $A$, if any. To do the same for some other prime, please use the same code.
D = 59 A = BinaryQF_reduced_representatives(-D, primitive_only=True)[0]
count = 0 count_rep = 0
for p in primes(3, 100): count += 1
F = GF(p) # F is the field with p elements
R.<x> = PolynomialRing(F)
f = x^3 + 2*x + 1
rep = A.solve_integer(p)
if rep:
# we have a representation of p by A
count_rep += 1
else:
rep = '' # so we will not print a None, but an empty string
sign = legendre_symbol(-D, p)
print(f"{p} & {sign} & {p % D} & {rep} & {latex(f.factor())} \\\\\\hline")
print("{} primes have a representation among the first {}" .format(count_rep, count))
This gives a result, that can be inserted into an array latex environment...
$$ \begin{array}{|r||r|c|l|l|} \hline p & \left(\frac{-D}p\right) & p\mod D & \text{rep.} & f_{-D}=x^3+2x+1\in\Bbb F_p[x]\\\hline\hline 3 & 1 & 3 & & (x^{3} + 2 x + 1) \\\hline 5 & 1 & 5 & & (x^{3} + 2 x + 1) \\\hline 7 & 1 & 7 & & (x^{3} + 2 x + 1) \\\hline 11 & -1 & 11 & & (x + 2) \cdot (x^{2} + 9 x + 6) \\\hline 13 & -1 & 13 & & (x + 11) \cdot (x^{2} + 2 x + 6) \\\hline 17 & 1 & 17 & (1, 1) & (x + 8) \cdot (x + 12) \cdot (x + 14) \\\hline 19 & 1 & 19 & & (x^{3} + 2 x + 1) \\\hline 23 & -1 & 23 & & (x + 15) \cdot (x^{2} + 8 x + 20) \\\hline 29 & 1 & 29 & & (x^{3} + 2 x + 1) \\\hline 31 & -1 & 31 & & (x + 8) \cdot (x^{2} + 23 x + 4) \\\hline 37 & -1 & 37 & & (x + 15) \cdot (x^{2} + 22 x + 5) \\\hline 41 & 1 & 41 & & (x^{3} + 2 x + 1) \\\hline 43 & -1 & 43 & & (x + 23) \cdot (x^{2} + 20 x + 15) \\\hline 47 & -1 & 47 & & (x + 33) \cdot (x^{2} + 14 x + 10) \\\hline 53 & 1 & 53 & & (x^{3} + 2 x + 1) \\\hline 59 & 0 & 0 & (-1, 2) & (x + 28) \cdot (x + 45)^{2} \\\hline 61 & -1 & 2 & & (x + 35) \cdot (x^{2} + 26 x + 7) \\\hline 67 & -1 & 8 & & (x + 5) \cdot (x^{2} + 62 x + 27) \\\hline 71 & 1 & 12 & (7, 1) & (x + 4) \cdot (x + 23) \cdot (x + 44) \\\hline 73 & -1 & 14 & & (x + 69) \cdot (x^{2} + 4 x + 18) \\\hline 79 & 1 & 20 & & (x^{3} + 2 x + 1) \\\hline 83 & -1 & 24 & & (x + 47) \cdot (x^{2} + 36 x + 53) \\\hline 89 & -1 & 30 & & (x + 7) \cdot (x^{2} + 82 x + 51) \\\hline 97 & -1 & 38 & & (x + 24) \cdot (x^{2} + 73 x + 93) \\\hline 101 & -1 & 42 & & (x + 13) \cdot (x^{2} + 88 x + 70) \\\hline 103 & -1 & 44 & & (x + 12) \cdot (x^{2} + 91 x + 43) \\\hline 107 & 1 & 48 & & (x^{3} + 2 x + 1) \\\hline 109 & -1 & 50 & & (x + 74) \cdot (x^{2} + 35 x + 28) \\\hline 113 & -1 & 54 & & (x + 49) \cdot (x^{2} + 64 x + 30) \\\hline 127 & 1 & 9 & & (x^{3} + 2 x + 1) \\\hline 131 & -1 & 13 & & (x + 116) \cdot (x^{2} + 15 x + 96) \\\hline 137 & 1 & 19 & & (x^{3} + 2 x + 1) \\\hline 139 & 1 & 21 & (1, 3) & (x + 40) \cdot (x + 112) \cdot (x + 126) \\\hline 149 & -1 & 31 & & (x + 84) \cdot (x^{2} + 65 x + 55) \\\hline 151 & -1 & 33 & & (x + 90) \cdot (x^{2} + 61 x + 99) \\\hline 157 & -1 & 39 & & (x + 81) \cdot (x^{2} + 76 x + 126) \\\hline 163 & 1 & 45 & (4, 3) & (x + 14) \cdot (x + 53) \cdot (x + 96) \\\hline 167 & 1 & 49 & & (x^{3} + 2 x + 1) \\\hline 173 & -1 & 55 & & (x + 84) \cdot (x^{2} + 89 x + 138) \\\hline 179 & -1 & 2 & & (x + 172) \cdot (x^{2} + 7 x + 51) \\\hline 181 & 1 & 4 & & (x^{3} + 2 x + 1) \\\hline 191 & -1 & 14 & & (x + 162) \cdot (x^{2} + 29 x + 79) \\\hline 193 & 1 & 16 & & (x^{3} + 2 x + 1) \\\hline 197 & 1 & 20 & (13, 1) & (x + 58) \cdot (x + 162) \cdot (x + 174) \\\hline 199 & 1 & 22 & & (x^{3} + 2 x + 1) \\\hline \end{array} $$ And we have a representation of the prime $p$ exactly in the cases where the second columns shows the $1$, and the last column shows three factors, so the "degree" type of the decomposition is $1+1+1$. The last column has the "degree type" $1+2$ iff there is a $-1$ in the Legendre symbol column. And the other cases correspond to Legendre symbol $=+1$, and a "degree type" $3$ in the last column. There is no "simple rule" as in the case of class number two, where the corresponding polynomial $f_{-D}$ has degree two, so that the splitting decision is in essence quadratic reciprocity. Above, for instance, there are two primes with the same rest mod $59$, namely $p=79$ and $p=197$, and $-D$ is a square modulo both $p$ values, but the representation problem shows different outcomes.
Cebotarev density arguments show that "statistically":
To conclude, the "open issue" from the comments is covered by Theorem 1 in loc. cit..
Best Answer
Yes, there are algorithms that are much better than brute force. For example, see section 5.4 in Henri Cohen's book "A course in computational algebraic number theory" for Shanks's baby-step giant-step algorithm $O(|D|^{1/4+\epsilon})$ - which is practical for negative discriminants $D$ up to 25 digits or more and, further, McCurley's sub-exponential algorithm (including Atkin's variant) which is $O(L(|D|)^\alpha)$ for $\alpha = \sqrt 2 \;$ or perhaps even $\alpha = \sqrt{9/8},$ where $\; L(x) = e^{\sqrt {\ln x \ln\ln x}}$. This can handle $D$ up to 50 digits or more (nowadays, with various improvements, probably around 80 digits or more - the prior numbers are quoted from the 1993 edition of Cohen's book - currently the bible for computational algebraic number theory).