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

DOI10.1016/j.jsc.2008.11.001zbMath1222.11148OpenAlexW1985912547MaRDI QIDQ1015166

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

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

Cites Work

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