Encryption with large mods

Question

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.

Answer 1

$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$

Answer 2

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);

Answer 3

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;
}