# 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.

• Repeated squaring would work quite easily here (you'd need to calculate ~8 residues). – apnorton Jan 9 '15 at 17:07

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

• Thank you Modded Bear, this was clear precise and very helpful! I appreciate it – Joe Connell Jan 9 '15 at 18:04
• Also, you may want to write some congruences in negative form instead of positive form to ease calculations. for example $919$ is $-90$, notice when you square the sign becomes positive anyway. – Jorge Fernández Hidalgo Jan 9 '15 at 18:34

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

• what does "e>>=1;" do? – Jorge Fernández Hidalgo Jan 9 '15 at 18:02
• @ModdedBear: As the algorithm description (above) says, it sets $e=\lfloor\frac{e}{2}\rfloor$. – barak manos Jan 9 '15 at 18:03
• Oh, I get it now. – Jorge Fernández Hidalgo Jan 9 '15 at 18:05
• Thank you barak, as a programmer i do appreciate this precise code but it has to be done by hand. I cant upvote as i do not have enough rep but thank you for your help – Joe Connell Jan 9 '15 at 18:05
• @JoeConnell: You're welcome. Don't worry about the up-voting :) As to "be done by hand" - I added the general algorithm above the code, so it might be helpful to you with that task of yours. – barak manos Jan 9 '15 at 18:09

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

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