1
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$

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.