2
$\begingroup$

Possible Duplicate:
calculating $a^b \!\mod c$

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!

  • 1
    Possible duplicate: [calculating $a^b$ mod $c$](http://math.stackexchange.com/q/26722/3111). Also two more times since then, [Modular exponentiation?](http://math.stackexchange.com/q/119374/3111) and [how to calculate $f^x$ using fast binary exponentiation?](http://math.stackexchange.com/q/91849/3111)2012-10-02

1 Answers 1

2

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.

  • 0
    thank you , i will check it out.2012-10-02