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

Question

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?

Answer 1

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).

For the modulo, you would calculate ab, then z = floor (ab / m), then r = ab - mz. If mz> ab then z was too large, so decrease z by 1 and subtract m from mz.

To find ab / r, you can use Newton iteration. There is a clever way to arrange this without any divisions, just multiplications. This is an iterative method with about log n iterations, but only the last iteration needs the full precision, so the total time is O (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).

• rus9384: Using Furer's algorithm decreases asymptotic runtime, I guess.