Encryption with large mods I am studying for a cryptography final and I have come across something I can just not figure out. My math background is rather weak. 
This is related to RSA and concerns itself with raising numbers to large powers. The question is:

Compute $10^{237}\mod 1009$. 

I am aware the answer is $852$, but I am unable to calculate it.
I have tried using multiple of powers and looked at Euler's theorem and also Fermat's theorem, but at this point I'm so confused!
Any help would be appreciated.
 A: The Algorithm:


*

*Input: $x=10,e=237,n=1009$

*Output: $y=1$

*Repeat until $e=0$:


*

*If $e\equiv1\pmod2$ then set $y=yx\bmod{n}$

*Set $x=x^2\bmod{n}$

*Set $e=\lfloor\frac{e}{2}\rfloor$
C Implementation:
int PowMod(int x,int e,int n)
{
    int y = 1;
    while (e > 0)
    {
        if (e & 1)
            y = (y*x)%n;
        x = (x*x)%n;
        e >>= 1;
    }
    return y;
}

int result = PowMod(10,237,1009);

A: $1009$ is a prime number and multiplicative groups modulo prime numbers are cyclic, so some numbers have order $1008$, so you won't be able to apply euler fermat or any result relying on the order of the elements.
Here is how exponentiation by squaring works: write the exponent in binary.
$237=11101101$
Proceed to calculate $10,10^2,10^4,10^8,10^{16},10^{32},10^{64},10^{128}$ in base $1009$ by squaring the previous term.
You should get $10,100,919,28,784,175,355,909$.
Since $10^{237}=10^{128}*10^{64}*10^{32}*10^{8}*10^{4}*10$ you want 
$909\cdot355\cdot175\cdot28\cdot919\cdot 10 \bmod 1009$ to calculate this simplify mod $1009$ after each multiplication.
Your final result should be $852$
A: Some useful theorems about modular arithmetic.  I'm using $\%$ as a modulo operator here, since I think you're working in a computational context.
$$(ab) \% m = ((a \% m)(b \% m)) \% m$$
This leads to:
$$(a^{2n}) \% m = (((a^2)\% m)^n) \% m$$
and
$$(a^{2n+1}) \% m = (a (((((a^2)\% m)^n) \% m)\%m$$
Which leads to the fast modular exponentiation algorithm, which requires $O(\log n)$ operations.
// calculates (b * a^n) mod m, with no intermediates 
// getting larger than m^2

powmod2(a,b,n,m) =
    if (n = 0) then return (a % m)
    if (n is odd) then return powmod2(a,(b*a)%m,n-1,m)
                  else return powmod2((a*a)%m,b,n/2,m)

Which is more commonly implemented like this:
// calculates a^n mod m with no intermediates
// larger than m^2
int powmod(a,n,m) {
    int accum = 1;
    a = a % m;
    while (n > 0) {
        if (n % 2 == 1) { // n is odd
            accum = (accum * a)%m;
            n = n - 1;
        } else { // n is even and greater than 0
            a = (a*a)%m;
            n = n / 2;
        }
    }
    return accum;
}

