0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Using Furer's algorithm decreases asymptotic runtime, I guess. $\endgroup$ – rus9384 Mar 2 '18 at 14:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.