Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
From MaRDI portal
Publication:4575643
DOI10.1137/1.9781611974331.ch64zbMath1409.68121OpenAlexW4250253042MaRDI QIDQ4575643
Jean-François Biasse, Fang Song
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch64
Number-theoretic algorithms; complexity (11Y16) Algebraic number theory computations (11Y40) Class field theory (11R37) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (32)
Computation of lattice isomorphisms and the integral matrix similarity problem ⋮ Return of GGH15: provable security against zeroizing attacks ⋮ Improved reversible and quantum circuits for Karatsuba-based integer multiplication. ⋮ Application of automorphic forms to lattice problems ⋮ Orientations and the supersingular endomorphism ring problem ⋮ Quantum algorithms for variants of average-case lattice problems via filtering ⋮ A proof of the conjectured run time of the Hafner-McCurley class group algorithm ⋮ Generic models for group actions ⋮ Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings ⋮ Pourchet’s theorem in action: decomposing univariate nonnegative polynomials as sums of five squares ⋮ Log-\(\mathcal{S}\)-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP ⋮ Fast practical lattice reduction through iterated compression ⋮ Fast multiquadratic S-unit computation and application to the calculation of class groups ⋮ Generating subgroups of ray class groups with small prime ideals ⋮ Norm relations and computational problems in number fields ⋮ The special case of cyclotomic fields in quantum algorithms for unit groups ⋮ Reductions from module lattices to free module lattices, and application to dequantizing module-LLL ⋮ Subfield algorithms for ideal- and module-SVP based on the decomposition group ⋮ Twisted-PHS: using the product formula to solve approx-SVP in ideal lattices ⋮ Approximate short vectors in ideal lattices of \(\mathbb{Q}(\zeta_{p^e})\) with precomputation of \({\mathrm {Cl}}(\mathcal{O}_K)\) ⋮ Security analysis of cryptosystems using short generators over ideal lattices ⋮ Short Generators Without Quantum Computers: The Case of Multiquadratics ⋮ Computing Generator in Cyclotomic Integer Rings ⋮ Short Stickelberger Class Relations and Application to Ideal-SVP ⋮ Constraint-Hiding Constrained PRFs for NC $$^1$$ from LWE ⋮ On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in \(\mathbb{Q}(\zeta_{2^s})\) ⋮ Short principal ideal problem in multicubic fields ⋮ Quantum-access-secure message authentication via blind-unforgeability ⋮ On the ideal shortest vector problem over random rational primes ⋮ A Subfield Lattice Attack on Overstretched NTRU Assumptions ⋮ Cryptanalyses of Candidate Branching Program Obfuscators ⋮ On the quantum complexity of the continuous hidden subgroup problem
This page was built for publication: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
