Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings

DOI10.1016/J.JSC.2008.11.001MaRDI QIDQ1015166zbMATHOpenAlexFDO

Authors J. Martínez

Publication date 7 May 2009

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2008.11.001

zbMATH Keywords

computational complexityimaginary quadratic fieldsnorm Euclidean algorithm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quadratic extensions (11R11) Number-theoretic algorithms; complexity (11Y16) Algebraic number theory computations (11Y40)

Recommendations

• On the minimal algorithm in rings of imaginary quadratic integers
• Lower bounds on solutions of quadratic polynomials defined over finite rings
• On the size of Diophantine \(m\)-tuples in imaginary quadratic number rings
• On a lower bound for the class number of an imaginary quadratic field
• Norms of indecomposable integers in real quadratic fields
• Euclidean ideals in quadratic imaginary fields
• scientific article; zbMATH DE number 3051062
• scientific article; zbMATH DE number 740356
• otally real Thue inequalities over imaginary quadratic fields: an improvement
• scientific article; zbMATH DE number 3578945

Cites work

• scientific article; zbMATH DE number 4083758 (Why is no real title available?)
• A lower bound for integer greatest common divisor computations
• Algorithmic Number Theory
• Arithmetic complexity
• Computation of discrete logarithms in prime fields
• Computational problems associated with Racah algebra
• Discrete logarithms in \(\mathrm{GF}(p)\)
• Efficient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers
• Is the Euclidean Algorithm Optimal Among its Peers?
• Lower Bounds for Computations with the Floor Operation
• Lower bounds for arithmetic problems
• New Computational Paradigms
• On the optimality of the binary algorithm for the Jacobi symbol
• \((1+i)\)-ary GCD computation in \(\mathbb Z[i]\) as an analogue to the binary GCD algorithm.

This page was built for publication: Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings

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