# RSA encryption theory - modulo theory

I'm a bit mathematically challenged and have been working on the RSA cipher (good start). I can find the public and private keys and know how to work do modulo operations on a calculator. The problem is that I can't do them when the numbers get to high. For example say I have:

$$10^{541} \bmod{2923} = C$$ The numbers involved here become very large and don't display fully on a calculator, if it can even handle the numbers (mine is crap). What I am wondering is if there is a better method to work out the ciphertext or plaintext that will work for largish numbers.

N.B. I'm not a mathematician, I'm in computing but was told my question would be better posed here.

-
You don't really do this kind of calculation by hand. If you do, I still think this is algorithmic question more than a mathematical one and belongs in cs.se or stackoverflow. –  tomasz May 22 '13 at 20:34
You should not compute $10^{541}$ ever. One simple way to keep numbers small is to multiply by $10$ each time, and reduce by $2923$ after each multiplication. More advanced techniques include square-and-multiply. –  TMM May 22 '13 at 20:36

The ideas is crudely that you first calculate remainders $x_k$ of $10^{2^k}$ modulo $2923$ for as high $k$ as needede by repeated squaring: $$10^2\equiv 100\pmod{2923},$$ $$10^4=(10^2)^2=10000\equiv1231\pmod{2923},$$ (because $10000=8769+1231=3\cdot2923+1231)$, $$10^8=(10^4)^2\equiv1231^2\equiv x_3 \pmod{2923},$$ (can't be bothered to compute $x_3$ now, sorry) $$10^{16}=(10^8)^2\equiv x_3^2\equiv x_4\pmod{2923},$$ and so on all the way up to $$10^{512}=(10^{256})^2\equiv x_8^2\equiv x_9\pmod{2923}.$$ At this point you know integers $x_k,k=0,1,2,\ldots,9$ such that $0\le x_k<2923$ and $10^{2^k}\equiv x_k\pmod{2923}$. You had to calculate the squares of nine integers (all smaller than $2923$) and the remainders of those squares. Then you can finish off by multiplying a chosen selection of those numbers and the remainde of that product: $$10^{541}=10^{512+16+8+4+1}=10^{512}\cdot10^{16}\cdot10^8\cdot10^4\cdot10 \equiv x_9x_4x_3x_2x_0.$$