1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Mark Bennet Aug 4 '14 at 11:44
  • $\begingroup$ Thanks @MarkBennet Fermat's little theoram did the trick. $\endgroup$ – gmfreak Aug 4 '14 at 15:14
  • $\begingroup$ Relevant $\endgroup$ – MJD Aug 4 '14 at 17:37
  • $\begingroup$ @MJD this link is awesome! Thanks $\endgroup$ – gmfreak Aug 4 '14 at 17:58
  • 1
    $\begingroup$ I'm glad I could help. $\endgroup$ – MJD Aug 4 '14 at 18:20
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.