What is the big O running time of a mod p, given a and p are n bit numbers?

Question

I am trying to find the running time of an algorithm that includes a computation of a%p. How long should this step take if a and p are n bit numbers?

Answer 1

the modulo operation is on O(1), if you use the hardware implementation. (the reason being, that every operation on a limited set of input values into the same set is in O(1)) Otherwise, any software implementation for arbitrary length integers should have a similar complexity as the division of the same input numbers. I'm not sure what exactly that is.

EDIT: I've got a hunch, it's O(n²) but I don't have a proof ready.

EDIT2: It's really hard to provide a complete and correct answer to this, as the complexity does not depend on the problem but on the implementation and thus, different implementations have different complexities, and the problem can only give a lower bound for the achievable performance of a solving algorithm.

Hoever, there is no such thing as a lower bound for the complexity of multiplication yet. and as the lower bound for modulo actually depends on the lower bound for multiplication (see the link posted in the comments. I've read it, it's good stuff!), there is also no lower bound for the complexity of modulo implementations, and so we can't give an exact estimate of the achievable performance of modulo.

But since we're talking about Big-O notation, I can safely say that any decent modulo implementation in in O(n²), and most are in smaller subsets of O(n²).