For a while now, I have been struggling to find a source explaining the complexity of the following 2 elementary operations
- Calculating the $n^\text{th}$ root of an integer $x$, $$ \sqrt[\leftroot{-3}\uproot{3}n]{x} $$
- 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?