1
$\begingroup$

What is the running time complexity (average or worst case) of common arithmetic operations in number fields?

In fact, I'm only interested in the integer ring of the quadratic extension $\mathbb{Q}[\sqrt{5}]$, although if there's an answer that quantifies the complexity well and is applicable to a more general class of extensions or integer rings that would be great as well.

In particular, I'd like to know what is the complexity of checking divisibility $\alpha \vert \beta$ for $\alpha, \beta \in \mathbb{Z}[(\sqrt{5}-1)/2]$.

What are some good resources to read up on relevant results?

Answers to this question describe the running time complexity of common arithmetic operations in finite fields. This publication describes the complexity of division in quadratic field extensions. Unfortunately, I wasn't able to access this publication.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.