A Rigorous Subexponential Algorithm For Computation of Class Groups
From MaRDI portal
Publication:3480172
DOI10.2307/1990896zbMath0702.11088OpenAlexW4242957755MaRDI QIDQ3480172
Kevin S. McCurley, James Lee Hafner
Publication date: 1989
Full work available at URL: https://doi.org/10.2307/1990896
Quadratic extensions (11R11) Number-theoretic algorithms; complexity (11Y16) Algebraic number theory computations (11Y40) Class numbers, class groups, discriminants (11R29) Class numbers of quadratic and Hermitian forms (11E41)
Related Items (49)
New quadratic polynomials with high densities of prime values ⋮ Practical isogeny-based key-exchange with optimal tightness ⋮ Constructing irreducible polynomials over finite fields ⋮ Computing points of bounded height in projective space over a number field ⋮ On the hardness of the computational ring-LWR problem and its applications ⋮ An isogeny-based ID protocol using structured public keys ⋮ Algorithms in Algebraic Number Theory ⋮ Calcul du nombre de classes d'un corps quadratique imaginaire ou réel, d'après Shanks, Williams, McCurley, A. K. Lenstra et Schnorr ⋮ Approximating Euler products and class number computation in algebraic function fields ⋮ Breaking the decisional Diffie-Hellman problem for class group actions using genus theory: extended version ⋮ A proof of the conjectured run time of the Hafner-McCurley class group algorithm ⋮ Generic models for group actions ⋮ Computational Number Theory, Past, Present, and Future ⋮ An efficient key recovery attack on SIDH ⋮ A Formal Proof of the Computation of Hermite Normal Form in a General Setting ⋮ I want to ride my \texttt{BICYCL} : \texttt{BICYCL} implements cryptography in class groups ⋮ \( L_1\)-norm ball for CSIDH: optimal strategy for choosing the secret key space ⋮ Fast multiquadratic S-unit computation and application to the calculation of class groups ⋮ Computing the endomorphism ring of an ordinary elliptic curve over a finite field ⋮ CSIDH: an efficient post-quantum commutative group action ⋮ A low-memory algorithm for finding short product representations in finite groups. ⋮ Statistical Evidence for Small Generating Sets ⋮ On the computation of quadratic 2-class groups ⋮ Approximate short vectors in ideal lattices of \(\mathbb{Q}(\zeta_{p^e})\) with precomputation of \({\mathrm {Cl}}(\mathcal{O}_K)\) ⋮ An 𝐿(1/3) algorithm for ideal class group and regulator computation in certain number fields ⋮ Computing Generator in Cyclotomic Integer Rings ⋮ A Subexponential Algorithm for Evaluating Large Degree Isogenies ⋮ Topics in computational algebraic number theory ⋮ A fast, rigorous technique for computing the regulator of a real quadratic field ⋮ Selected Applications of LLL in Number Theory ⋮ A Rigorous Time Bound for Factoring Integers ⋮ Small generators of the ideal class group ⋮ Unconditional class group tabulation of imaginary quadratic fields to $\|\Delta \| < 2^{40}$ ⋮ Computing isogenies between supersingular elliptic curves over \(\mathbb {F}_p\) ⋮ Subexponential time relations in the class group of large degree number fields ⋮ Об использовании групп классов идеалов квадратичных полей для построения криптографических систем с открытым ключом ⋮ Solving Thue equations without the full unit group ⋮ Efficient verifiable delay functions ⋮ Computing Hilbert class polynomials with the Chinese remainder theorem ⋮ On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis ⋮ Quadratic class numbers and character sums ⋮ Cryptographic hash functions from expander graphs ⋮ Decision problems in quadratic function fields of high genus ⋮ Algorithmic approach to logarithmic class groups ⋮ The Pohlig-Hellman method generalized for group structure computation ⋮ Breaking the decisional Diffie-Hellman problem for class group actions using genus theory ⋮ Applying sieving to the computation of quadratic class groups ⋮ Conditional bounds for the least quadratic non-residue and related problems ⋮ Rational isogenies from irrational endomorphisms
Cites Work
- Matrix multiplication via arithmetic progressions
- Fast multiplication of large numbers
- Fast computation of continued fraction expansions.
- Hermite Normal Form Computation Using Modulo Determinant Arithmetic
- Gauss’ class number problem for imaginary quadratic fields
- Solving sparse linear equations over finite fields
- A Probabilistic Factorization Algorithm with Quadratic Forms of Negative Discriminant
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A Rigorous Subexponential Algorithm For Computation of Class Groups
