Supersingular $j$-invariants and the Class Number of $\mathbb{Q}(\sqrt{-p})$
Preprint
Abstract
For a prime $p>3$, let $D$ be the discriminant of an imaginary quadratic order with $|D|< \frac{4}{\sqrt{3}}\sqrt{p}$. We research the solutions of the class polynomial $H_D(X)$ mod $p$ in $\mathbb{F}_p$ if $D$ is not a quadratic residue in $\mathbb{F}_p$. We also discuss the common roots of different class polynomials in $\mathbb{F}_p$. As a result, we get a deterministic algorithm (Algorithm 3) for computing the class number of $\mathbb{Q}(\sqrt{-p})$. The time complexity of Algorithm 3 is $O(p^{3/4+\epsilon})$.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- An exponent one-fifth algorithm for deterministic integer factorisationMathematics of Computation, 2021
- A babystep-giantstep method for faster deterministic integer factorizationMathematics of Computation, 2018
- Character sums and deterministic polynomial root finding in finite fieldsMathematics of Computation, 2015
- On Singular Moduli for Arbitrary DiscriminantsInternational Mathematics Research Notices, 2014
- Computation of class numbers of quadratic number fieldsMathematics of Computation, 2001
- Factoring Integers with Elliptic CurvesAnnals of Mathematics, 1987
- On maximal orders of division quaternion algebras over the rational number field with certain optimal embeddingsNagoya Mathematical Journal, 1982