# Determining the complexity of calculating n-th root of an integer, and performing modulo arithmetic?

For a while now, I have been struggling to find a source explaining the complexity of the following 2 elementary operations

1. Calculating the $n^\text{th}$ root of an integer $x$, $$\sqrt[\leftroot{-3}\uproot{3}n]{x}$$
2. Checking whether $$a \equiv b \mod r$$ for $a,b,r \in \mathbb{N}$

I now think I may have come close to finding an answer to the second of these problems, but I am not certain.

On pages 10-11 of the book Édouard Lucas and Primality Testing (by Hugh C. Williams), the following statement is made:

For any $m$ and $a,b$ with $0 < |a|, |b| < m$ calculating $$r \equiv ab \mod m$$ can be done in $O((\log m)^2)$ operations.

Am I to assume, based on this, that operation 2. has complexity $O((\log m)^2)$?

I also suspect that operation $1$ has complexity $O((\log m)^2)$, but I have no justification for this. Could someone please also tell me whether this is correct?

You can multiply two n-bit numbers trivially in $O(n^2)$, but using FFT (fast fourier transform) you can get the time down to $O (n \log n \log \log n)$. Lets call this time T(n).
Things are even better if you want $z = a^{1/b}$ rounded to an integer, and to check if it is an integer. Again you use Newton iteration, but you only need a result with a bit over n / b bits precision. The result itself is a bit harder to calculate, requiring about log b multiplications, so the time to calculate this is $O (T (n / b) \log b)$. If you can't decide whether z is an integer or not due to precision, you can calculate $round(z)^b$ in T(n).