How to calculate a base to the power an exponent which is extremely large and is already modded with a prime number m and in turn the whole expression is also modded with the same m.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ I'm not sure this can be done without knowing the exact value of $p$. $p$ mod $(m-1)$ would be relevant, but you wouldn't be able to determine this given just $p$ mod $m$. $\endgroup$– MikeCommented Jul 8, 2018 at 4:09
-
$\begingroup$ @Mike,So the answer is (if we we know p mod (m-1) ) , (b^(p mod m-1)) mod m right? Thanks a lot! $\endgroup$– SathyaramCommented Jul 8, 2018 at 6:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I don't know why this question is being down-voted instead of being answered.
The answer is we can't if we only know $(p\ mod\ m)$.
But if we know $p$ we could use the Fermat's Little Theorem, which says that $b^{(m-1)}\ mod\ m = 1$.
We can write $p$ as $p = q.(m-1) + r$ .
Now we can write $b^p\ mod\ m$ as $(b^{(m-1)})^{q}.b^{r}\ mod\ m$ which is nothing but $b^{(p\ mod\ (m-1))}\ mod\ m$ .