I have a number of form: $p^n + p$, where $p$ is a prime number and $n$ can be any large number, for example, say $10^{12}$.
What is the generic algorithm to compute $(p^n + p) \pmod k$, where $k$ is a huge number say $k=1000000007$.
Thanks!
Answer
As you already know (a+b)mod n = ((a mod n) + (b mod n)) mod n .
So I guess addition here is not a problem.
The real question seems to be on $p^n$ mod k where n is large. For that, have a look at Modular Exponentiation on wikipedia.
No comments:
Post a Comment