O32 — Class numbers of imaginary quadratic orders

Definitions and mathematical statement

Let $D=-d<0$ be a quadratic-order discriminant: $d$ is a positive integer and $D\equiv0$ or $1\pmod4$. Consider the primitive positive definite integral binary quadratic forms \[ Q(X,Y)=aX^2+bXY+cY^2,\qquad b^2-4ac=D, \] where $a,b,c\in\mathbb Z$, $a>0$, and $\gcd(a,b,c)=1$. Two forms are properly equivalent when one is obtained from the other by an integral change of variables with determinant one, that is, by an element of $\mathrm{SL}_2(\mathbb Z)$.

The class number $h(D)$ is the number of these proper equivalence classes. This is finite; equivalently it is the cardinality of the group of invertible ideal classes of the imaginary quadratic order of discriminant $D$. Nonfundamental discriminants are allowed, so the order need not be the full ring of integers of its field.

Given $d$ in binary, can $h(-d)$ be computed exactly by a deterministic classical algorithm whose running time is bounded by a fixed polynomial in $\log(2d)$? The input is promised to give a valid negative discriminant. The output is the class number in binary, not a complete enumeration of form classes.

No factorization of $d$, presentation of a class group, or list of reduced forms is supplied. Enumerating classes is a possible finite approach, but a positive answer must establish the requested bit-complexity bound uniformly as the discriminant grows.

Short English statement

Can imaginary quadratic order class numbers be computed exactly and deterministically in time polynomial in the discriminant’s binary length?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 8400036 (AMR-083-0036), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Adleman & McCurley - Open Problems in Number Theory Complexity II (1994), O32, p21 / LNCS p311. Original source indexed by AMR-083-0036. https://mccurley.org/papers/open.ps.gz.