I came across a problem where I need to find $x^y$ mod $p$ where $p$ is prime.It is an easy problem which can be find in $O(\log y)$ complexity but the twist in the problem is that value of $y$ is $n\text{C}r$ where $n$ can go up to 5000 hence $y$ can be very large and cannot be stored (can be of $10^{1500}$).So is there any way to find $x^y$ mod $p$?
I have tried this (x^(y mod p)) mod p but that doesn't give the correct answer.Please help.
The trick here is to calculate $x^{y\mod (p-1)}$ mod $p$.
This works by Fermat's little theorem: $x^{p-1}\equiv 1$ mod $p$, and so if $y\equiv k\mod p-1$ then $y=m(p-1)+k$ for some $m$ and $x^y\equiv x^{m(p-1)}x^k\equiv 1^mx^k$ mod $p$.