# Digit wise modulo for calculating power function for very very large positive integers

I am writing a code to calculate $P^Q$ where $P$, $Q$ are positive integers which can have number of digits up to $100000$.

I want the result as $r = P^Q \pmod{10^9+7}$, where $10^9+7$ is a prime number.

Example:

\begin{align} P &= 34534985349875439875439875349875\\ Q &= 93475349759384754395743975349573495 \\\quad\\ r &= 735851262 \end{align}

I tried using the trick:

\begin{align} P^Q \pmod{10^9+7} &= \underbrace{P \times P \times \ldots \times P}_{Q \text{ times}} \pmod{10^9+7} = \\ &= \Big(\underbrace{P \pmod{10^9+7} \times \ldots \times P \pmod{10^9+7}}_{Q \text{ times}}\Big) \pmod{10^9+7} \end{align}

Since both $P$ and $Q$ are very large, I should store them in an array and do modulo digit by digit.

Is there any efficient way of doing this or some number theory algorithm which I am missing?

• Do you know Fermat's little theorem (this will enable you to reduce Q)? And repeated squaring can be a better way of computing powers (you can reduce modulo your prime at any stage) – Mark Bennet Aug 4 '14 at 11:44
• Thanks @MarkBennet Fermat's little theoram did the trick. – gmfreak Aug 4 '14 at 15:14
• Relevant – MJD Aug 4 '14 at 17:37
• @MJD this link is awesome! Thanks – gmfreak Aug 4 '14 at 17:58
• I'm glad I could help. – MJD Aug 4 '14 at 18:20

One common trick, which requires $O(\log_2 m)$ multiplications, is to use the following algorithm:
1. If $m$ is even, calculate $b=a^{m/2}$ and then use one additional multiplication to find $a^m = b^2$.
2. If $m$ is odd, calculate $b=a^{(m-1)/2}$ and then use two additional multiplications to find $a^m = ab^2$.
For example, to calculate $a^{1000}$, you calculate the following, using one multiplication each: $a^2, a^3, a^6, a^7, a^{14}, a^{15}, a^{30}, a^{31}, a^{62}, a^{124}, a^{125}, a^{250}, a^{500}, a^{1000}$, for a total of 14 multiplications. To calculate $a^{1000000}$ would require only about twice as many multiplications.