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

The author derives lower bounds for the number of operations required in the (norm-) Euclidean algorithm for imaginary quadratic fields. She discusses the gcd computation in a special ``binary-like'' model. Allowed operations are subtraction, multiplication and division by a small fixed set of algebraic integers, and comparison of norms. She also discusses deciding coprimality of integers in those five fields. The gcd algorithm is shown to have a complexity which is quadratic in the lower bound.