# Calculating mod of n^k mod p in O(log k)

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.

• 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. – D.W. Jan 26 '18 at 23:19

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