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

Question

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?

Thanks in advance

Answer 1

I'm copying my answer from Raising to the power over finite fields ?? because OP said in a comment that it was useful.

---

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.

This is not optimal, but it is fast enough that people often don't bother with anything faster.