0

I have to perform the computation of $a^{b}\pmod {m}$. However, instead of providing $b$ directly, I instead know the value of $b\mod {m}$. Is it even possible to perform this calculation and if so, how do I go about it?

EDIT: I know that $m$ is a prime number.

xrisk
  • 223
  • 1
    No, it is not possible. Take $m=3$. then $1\equiv 4\pmod 3$ but $2^1\not \equiv 2^4\pmod 3$. For prime $m$ what you need is $b\pmod {m-1}$. – lulu Jul 15 '18 at 11:32
  • @lulu can you expand a little on how I can do the calculation if I know $ b \pmod {m - 1} $? – xrisk Jul 15 '18 at 11:36
  • Assume that $a\not \equiv 0\pmod m$. Then $a^{m-1}\equiv 1 \pmod m$, by Little Fermat. Thus if you replace $b$ with $b+k(m-1)$ we get $a^{b+k(m-1)}=a^b\times \left(a^{m-1}\right)^k\equiv a^b\pmod m$. – lulu Jul 15 '18 at 11:38

1 Answers1

2

As stated, this is not possible. Taking $m=3,\;a=2$ we remark that $$2^1\not \equiv 2^4\pmod 3$$

What you need is $b\pmod {m-1}$:

Assume that $a\not \equiv 0\pmod m$. Then $a^{m-1}\equiv 1 \pmod m$, by Little Fermat. Thus if you replace $b$ with $b+k(m-1)$ we get $a^{b+k(m-1)}=a^b\times \left(a^{m-1}\right)^k\equiv a^b\pmod m$.

lulu
  • 70,402