Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$.

Here's my simple algorithm:

We first check if $k=1$ or $k=2l$ or $k=2l+1$ for some $l \in \mathbb{Z}$

$x^{1} \mod x= x \mod n$

$x^{2l}=(x^{l}) \cdot (x^{l}) \mod n$

$x^{2l+1}=x \cdot (x^{l}) \cdot (x^{l}) \mod n$.

But what's the time complexity of this algorithm? If $k=2^{k}$ then it's painfully obvious, but the other case, whre $k$ is not a power of $2$ I'm having trouble writing down a solution that wouldn't give my professor headaches.

My guess:

Since for every move we divide the problem to a problem $\lfloor \frac{n}{2} \rfloor$ smaller, and a single multiplication takes $c$ than $T(n) \leq 2c + T( \lfloor \frac{n}{2} \rfloor)$, because at each step we would multiply at most two times. In the end $T(n)=O(\log_{2} k)$

  • 1
    $\begingroup$ Looks good to me. May be you shouldn't use $n$ in two roles, and say $T(k)\le 2x+T(\lfloor\frac k2\rfloor)$. After all, $n$ is the modulus. Also $c$ depends on $n$ (but is constant on a processor, if $n$ is within the range of a primitive integer type). $\endgroup$ – Jyrki Lahtonen Oct 19 '13 at 13:35
  • $\begingroup$ Thanks for the answer and the hint :) $\endgroup$ – Arek Krawczyk Oct 19 '13 at 13:38

Your Answer

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

Browse other questions tagged or ask your own question.