Methods to compute the class number

The class number is an important term from algebraic number theory. It specifies the order of the class group of an algebraic number field $K$ and can be interpreted as the number of different ways to factorize an element of $K$ into prime elements. If the class number is equal to $1$, the $K$ is called a unique factorization domain, e.g. the integers $\mathbb{Z}$. It is long known that for imaginary quadratic fields the class number is $1$ only for the values: $$K = \mathbf{Q}(\sqrt{d}), d \in \{-1,-2,-3,-7,-11,-19,-43,-67,-163\}$$ There are a surprisingly large number of ways to compute the class number of a quadratic field, which i want to show you next.

Different ways to compute the class number.

1 - Order of the class group

As already written above, the class number is the order of the ideal class group of an algebraic field $Q(\sqrt{d})$, for a squarefree integer $d$, with discriminant $\Delta$. It is $\Delta = d$ if $d \equiv 2,3 \pmod{4}$ or $\Delta = 4d$ if $d \equiv \pmod{4}$. The class group is isomorphic to the class group $cl_q$ of integral binary quadratic f orms with discriminant $\Delta$.

2 - Dirichlet's class number formula

If $\Delta > 4$ one could use Dirichlet's class number formula.

$$ h(-\Delta) = \frac{\sqrt{\Delta}}{\pi} \prod_{p \in \mathbb{P}} \left(1 - \binom{-\Delta}{p}p^{-1}\right)^{-1}$$

It contains an infinite product, which depends on the legendre symbol values $\binom{-\Delta}{p}$. Unfortunately, the approximation by computing partial products is very slow.

There is another way to write Dirichlet's class number formula for $\Delta > 4$: $$ h(-\Delta) = -\frac{1}{\Delta}\sum^{\Delta-1}_{k=1}\binom{-\Delta}{k}k $$ where $\binom{-\Delta}{k}$ is the Kronecker symbol. If $\Delta$ is a prime number of the form $\Delta \equiv 3\pmod{4}$ and $g$ is a primitive root in $\mathbb{F}^*_\Delta$ then this could also be written as: $$ h(-\Delta) = \frac{1}{\Delta}\left(\sum^{(\Delta-1)/2}_{k=1} (g^{2k} \pmod{\Delta}) - \sum^{(\Delta-1)/2}_{k=1} (g^{2k-1} \pmod{\Delta})\right) $$ It is the sum between the group elements with even exponent and those with odd exponents, For primitive roots this is simply the difference between the sum of quadratic residues and non-residues. Similar formula can be derived for $\Delta \equiv 1\pmod{4}$.

If $\Delta$ is a prime number of the form $\Delta \equiv 3\pmod{4}$ $$ h(-\Delta) =\sum^{(\Delta-1)/2}_{k=1} \binom{k}{\Delta} $$ A similar formula can be derived for $\Delta \equiv 1\pmod{4}$: If $g$ is a generator of a subgroup of size $\Delta-1$ in $\mathbb{F}^*_{4\Delta}$ and $g$ is also primitive in $\mathbb{F}^*_\Delta$ then: \begin{equation} h(-\Delta) = \frac{1}{2\Delta}\sum^{\Delta-1}_{j=1}(-1)^j\left(g^j \pmod{4\Delta}\right) \pmod{4\Delta}
\end{equation}

3 - Base b representation

$\Delta$ is a prime number of the form $\Delta \equiv 3\pmod{4}$, then the next way to compute the class number is to use the coefficients $c_i$ of the base-$b$ representation of the integer $$(b^{(\Delta-1)/2}-1)/\Delta = \sum^{(\Delta-3)/2}_{i=0} c_ib^i$$ , whereof $b$ has order $(\Delta-1)/2$ in $\mathbb{F}^*_\Delta$. Then it is: $$ h(-\Delta) = \frac{\Delta-1}{2} - 2\frac{\sum^{(\Delta-3)/2}_{i=0}c_i}{b-1} $$

4 - Continued Fractions

You can use Continued Fractions. It is assumed that around $80$% (i think due to Shanks, but i am not sure) of all class numbers of real quadratic fields are equal to $1$. If this is the case, e.g. $h(\Delta) = 1$, then if $$ \sqrt{\Delta} = \left[b_0;\overline{b_1,b_2,\ldots,b_m}\right]$$ whereof the overlined part is the period, then $$ h(-\Delta) = \frac{1}{3}\sum^m_{k=1}(b_k - 3)$$

5 - Sum of three squares

Let $L(n)$ be the following set $$L(n) = \{(a,b,c) \in \mathbb{Z}^3 | a^2+b^2+c^2 = n\}$$ then if $n$ is a squarefree integer $> 3$

1. If $n \equiv 1,2 \pmod{4}$ then $|L(n)| = 12H(-n)$
2. If $n \equiv 3 \pmod{8}$ then $|L(n)| = 24H(-n)$
3. If $n \equiv 7 \pmod{8}$ then $|L(n)| = 0$

Where $H(-n)$ is the Hurwitz-Kronecker class number, which is closely related to the class number.

6 - Orderings of three consecutive quadratic residues

Coming soon ...

7 - Number of Elliptic curves with $p+1$ points

Coming soon ...

Complexity and Factoring.

The complexity to compute the class number is exponential and it is assumed that the problem is $\mathsf{NP}$-complete, since you could verify in polynomial time if the answer is correct (simply check if it is the order of the class group). Computing the class number is also related to computing the factorization of an integer. Just assume you have an oracle, that computes for any given integer $n$ the class number $h(-n)$ in $\mathcal{O}(1)$. Then one could find two non-trivial factors of $n$ via the work of Lenstra [1]. He utilizes that by knowing $h(-n)$ you can find a binary quadratic form with discriminant $n$ that is of order $2$. E.g. just compute for a generator $g$ the value $g^{h/2}$. It is known that forms of order $2$, called ambiguous forms, have the the form $$ ((p+q)/4,(p-q)/2,(p+q)/4)\text{ if }3p \leq q$$ or $$ (p,p,(p+q)/4)\text{ if } p < q \leq 3p$$ and hence could be used to factor $n$.

What about the other direction? So the computation of the class number yields an method to factorize integers. But what if the factorization of the discriminante is known, does this lead to a more efficient why to compute the class number? As far as i can see, this would not contradict any known obstacles or solve some major open problems. I also asked this question on StackExchange but didn't got an answer yet.

For example, for $n=pq$ and $p,q$ primes of the form $7 + 8k$, then you could establish the equation: For any integers $u,v,x,y \in \mathbb{Z}$ it holds:

\begin{align*} & uv \frac{n-(q+p)+5}{4} + uyh(-q)\left(1-\binom{p}{q}\right) + vxh(-p)\left(1-\binom{q}{p}\right) + xy\frac{h(-pq)}{2} \\ & = (u+x)\left((v+y)S^{++}_{\frac{n-1}{4}}+(v-y)S^{+-}_{\frac{n-1}{4}}\right)+(u-x)\left((v-y)S^{--}_{\frac{n-1}{4}}+(v+y)S^{-+}_{\frac{n-1}{4}}\right) \end{align*}

whereof e.g. $S^{s_1s_2}_{\frac{n-1}{4}}$ denotes the number of integers $m_i$ in the intervall $[1,(n-1)/4]$ that have $\binom{m_i}{p} = s_1$ and $\binom{m_i}{q} = s_2$.

[1] A.K. Lenstra, Fast and rigorous factorization under the generalized Riemann hypothesis, Indagationes Mathematicae (Proceedings), Volume 91, Issue 4, 19 December 1988, Pages 443-454
[2] Quadratic fields and factorization, H.W. Lenstra jr. and R. Tijdeman (eds.): “Computational Methods in Number Theory,”, MC-Tracts 154/155, Amsterdam 1982, pp. 235-286