i was wondering if there is a way to use the prime factorization of the discriminant $d$ when computing the class number $h(d)$. E.g., assume you have an integer $n = pq$ with $p \equiv 1\pmod{4}$ and $q \equiv 3\pmod{4}$, with known primes $p$ and $q$ and the imaginary quadratic field $\mathbb{Q}(\sqrt{-n})$. Then $d = -n = -pq$ and you want to compute $h(d)$. Do there exists an algorithm the uses the knowledge of $p$ and $q$ or the class numbers $\mathbb{Q}(\sqrt{-p})$ and $\mathbb{Q}(\sqrt{-q})$ to compute the class number $h(d)$?

There is an answer to a complexity question on mathoverflow from 2013, which at least indicates that the best known algorithm ($\mathcal{O}(D^{1/4+\epsilon})$ with GRH or $\mathcal{O}(D^{1/2+\epsilon})$ without GRH) does not utilize this.

Regards, Etsch



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.