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 that you have read and understand our privacy policy and code of conduct.