# 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

## 1 Answer

You should familiarize yourself with the square and multiply algorithm. That way you never need to multiply together numbers larger than the modulus (here 2923).

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

The usual description of square and multiply organizes the calculations a bit more efficiently (so that you don't have to store so many intermediate results), but the general idea is as above.

-