Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields

DOI10.1137/1.9781611974331.CH64zbMATH Open1409.68121OpenAlexW4250253042MaRDI QIDQ4575643FDOQ4575643

Authors: 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

Recommendations

• Fast quantum algorithms for computing the unit group and class group of a number field
• A quantum algorithm for computing the unit group of an arbitrary degree number field
• Quantum algorithms for number fields
• Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
• Quantum algorithms for a set of group theoretic problems
• Quantum algorithms for solvable groups
• Publication:3470563
• An efficient quantum algorithm for some instances of the group isomorphism problem
• Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups
• Quantum algorithms for fixed points and invariant subgroups

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Class field theory (11R37) Number-theoretic algorithms; complexity (11Y16) Algebraic number theory computations (11Y40)

Cited In (46)

• Norm relations and computational problems in number fields
• Constraint-Hiding Constrained PRFs for NC $$^1$$ from LWE
• Generating subgroups of ray class groups with small prime ideals
• Orientations and the supersingular endomorphism ring problem
• Fast practical lattice reduction through iterated compression
• Quantum computation in algebraic number theory: Hallgren's efficient quantum algorithm for solving Pell's equation.
• On the quantum complexity of the continuous hidden subgroup problem
• Classical and Quantum Algorithms for Exponential Congruences
• Approximate short vectors in ideal lattices of \(\mathbb{Q}(\zeta_{p^e})\) with precomputation of \({\mathrm {Cl}}(\mathcal{O}_K)\)
• Quantum-access-secure message authentication via blind-unforgeability
• Short Generators Without Quantum Computers: The Case of Multiquadratics
• Short Stickelberger Class Relations and Application to Ideal-SVP
• Fast quantum algorithms for computing the unit group and class group of a number field
• Return of GGH15: provable security against zeroizing attacks
• On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in \(\mathbb{Q}(\zeta_{2^s})\)
• A proof of the conjectured run time of the Hafner-McCurley class group algorithm
• Short principal ideal problem in multicubic fields
• Security analysis of cryptosystems using short generators over ideal lattices
• Fast multiquadratic S-unit computation and application to the calculation of class groups
• An algorithm for solving the principal ideal problem with subfields
• Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
• Algorithmic Number Theory
• Log-\(\mathcal{S}\)-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP
• The special case of cyclotomic fields in quantum algorithms for unit groups
• Quantum algorithms for variants of average-case lattice problems via filtering
• On the discrete logarithm problem in the ideal class group of multiquadratic fields
• Application of automorphic forms to lattice problems
• Reductions from module lattices to free module lattices, and application to dequantizing module-LLL
• A Subfield Lattice Attack on Overstretched NTRU Assumptions
• Improved reversible and quantum circuits for Karatsuba-based integer multiplication.
• Subfield algorithms for ideal- and module-SVP based on the decomposition group
• Pourchet’s theorem in action: decomposing univariate nonnegative polynomials as sums of five squares
• Quantum algorithms for number fields
• On the ideal shortest vector problem over random rational primes
• SCALLOP-HD: group action from 2-dimensional isogenies
• Fully homomorphic encryption beyond IND-CCA1 security: integrity through verifiability
• Computation of lattice isomorphisms and the integral matrix similarity problem
• Optimizing Bootstrapping and Evaluating Large FHE Gates in the LWE-Based GSW-FHE
• FuLeakage: breaking FuLeeca by learning attacks
• Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings
• Efficient computations in central simple algebras using Amitsur cohomology
• Twisted-PHS: using the product formula to solve approx-SVP in ideal lattices
• A quantum algorithm for computing the unit group of an arbitrary degree number field
• Cryptanalyses of Candidate Branching Program Obfuscators
• Generic models for group actions
• Computing Generator in Cyclotomic Integer Rings

This page was built for publication: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575643)