# Modular exponentiation in P

I need to prove that the following language is in $$\mathsf{P}$$: $$L = \{\langle x,y,z,d \rangle : xˆy \equiv z \pmod{d}\}.$$

I'm assuming I just have to prove with an algorithm or negate that it's part of NP. But I don't know how to do it with this mathematical formula.

• No, the question was edited and its more clear now. – Luis Liz Dec 12 '18 at 15:34

First of all, anything in $$P$$ is also in $$NP$$, so proving that it's not in $$NP$$ will be an exercise in futility. I'm also going to change your variable names a bit to make them clearer; the letters I use stand for base, exponent, and modulus.

What you seem to be looking for is a modular exponentiation algorithm. In other words, a way to compute $$b^e \mod m$$ in polynomial time. Several of these exist, but here's the simplest one I know of:

function modular_exponent(b, e, m):
z ← 1
b ← b % m
for i ← 1..e:
z ← (b × z) % m
return z


The number of multiplications and modulus operations we do is linear in $$e$$, and the operands to those operations are never larger than $$m$$. So the runtime is $$O(e (\log{m})^2)$$ (assuming multiplication runs in log-squared and modulus runs in logarithmic time; in practice you can make this even a bit more efficient using something like Karatsuba multiplication, but that doesn't matter for this problem).

This is clearly a polynomial runtime, so the modular exponentiation decision problem ("for given $$b, e, m, z$$, is $$b^e\cong{}z \mod m$$?") is in $$P$$.