Given $n>0$, $k>0$, and a prime number $p$, compute: $$n^k\mod p$$ in $O(\log k)$ time. Here $x \mod y$ means the remainder for $x$ being divided by $y$. For example, $2^3\mod 7 = 1$. You assume that all of $n$, $k$, and $p$ can fit in a single word in your computer. Moreover, if $x$ and $y$ are numbers with sizes bounded by $O(1)$ words, then the computer can carry out each arithmetic operation ($+$, $-$, $\times$, $/$, $\mathrm{mod}$) on $x$ and $y$ in $O(1)$ time.

We want to achieve $T(k) = 2T(k/2) + O(1)$ since by the master theorem, this will give me $O(\log k)$. Now I'm assuming that I have to do $k/2$ every step with divide and conquer. If the number is even, it'll eventually get to $k=1$. Then how do I turn this to the correct number?

I know that $(n^k/2 \mod p \cdot 2) \mod p$ will give the same answer.

  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Jan 26 '18 at 23:19

Forget the master theorem. Your formula T(k) = 2T(k/2) + O(1) is total nonsense, it would give you O(k), not O(log k). And (n^k/2 mod p * 2) mod p makes no sense.

To calculate $n^k$ for k ≥ 2, you check if k is even or odd, that is either k = 2m or k = 2m + 1. You calculate $n^m$ recursively, multiply by itself, and if k is odd then you multiply by n once more. And what if k = 1? I hope you know how to calculate n^1?

That's for powers. Powers modulo p work exactly the same, except you do every multiplication involved modulo p.

Why your formula T(k) = 2T(k/2) + O(1) was totally wrong: Because you don't calculate $2^m$ twice. You calculate it once, then square it. So the formula is T(k) = T(k/2) + O(1).


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.