How do you calculate the modulo of a high-raised number? I need some help with this problem:
$$439^{233} \mod 713$$
I can't calculate $439^{223}$ since it's a very big number, there must be a way to do this.
Thanks. 
 A: Here`s the algorithm,basically it is Modular exponentiation.
function modular_pow(base, exponent, modulus)
  result := 1      
  while exponent > 0
      if (exponent mod 2 == 1):
         result := (result * base) mod modulus
      exponent := exponent >> 1
      base = (base * base) mod modulus
  return result

Also here is the working code in c++ which can work for upto 10^4 test cases,in 0.7 seconds
Also the ideone link http://ideone.com/eyLiOP
#include <iostream>
using namespace std;
#define mod 1000000007


long long int modfun(long long int a,long long int b)
{
     long long int result = 1;
    while (b > 0)
       {
           if (b & 1)
           {
               a=a%mod;
               result = (result * a)%mod;
               result=result%mod;
           }
        b=b>>1;
        a=a%mod;
        a = (a*a)%mod;
        a=a%mod;
       }
    return result;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
        {
           long long int a,b;
           cin>>a>>b;
           if(a==0)
            cout<<0<<"\n";
           else if(b==0)
            cout<<1<<"\n";
           else if(b==1)
            cout<<a%mod<<"\n";
           else
           {
               cout<<(modfun(a,b))%mod<<"\n";
           }

        }
    return 0;
}

A: You can go fast if you incrementally square:
$439^2=211 \pmod{713}$;
$211^2=315 \pmod{713}$;
$315^2=118 \pmod{713}$;
$118^2=377 \pmod{713}$;
$377^2=242 \pmod{713}$;
$242^2=98 \pmod{713}$; etc.
The last one means $439^{64}=98 \pmod{713}$;
In this way you can combine and reach 233 fast.
Ultimately  $439^{233}=211 \pmod{713}$;
A: You can do this step by step by first computing $439^2\equiv 211 {\ \rm mod\ }713$. Then you compute $439^4\equiv 211^2 \equiv 315 {\ \rm mod\ }713$. Continue to square and reduce mod $713$ and build up a list of powers $$439^1, \qquad 439^2, \qquad 439^4 \qquad \dots \qquad 439^{128}\qquad \qquad ({\rm mod\ }713)$$
Finally, write $233$ as a sum of powers of $2$, and compute
$$439^{233}=439^{1+8+32+64+128}=439\cdot 439^8\cdot 439^{32}\cdot439^{64}\cdot 439^{128} \qquad ({\rm mod\ }713)$$
Just remember to reduce mod $713$ each time you get a product which is larger than $713$.
A: There are often tricks to this if the numbers are nice enough, but even if they're not, here's a way that's not entirely horrible.
You already know what 439 is mod 713. What is $439^2 \mod 713$? What about $439^4$? (Hint: take your answer for $439^2$ after reducing it mod 713, and then square it again.) In the same way, calculate $439^8, 439^{16}, \dots, 439^{128} \mod 713$. Now just note that 233 = 128 + 64 + 32 + 8 + 1. So multiply the appropriate powers of 439 together - again, one calculation at a time, reducing mod 713 each time.
Now you should only have to do 11 calculations, and now all your numbers are 6 digits or less. Rather than impossible, it's now simply tedious. :)
By the way, one thing to notice: 713 = 23 * 31. Perhaps your calculations will be easier if you do them mod 23 and 31, then apply the Chinese remainder theorem?
