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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.