Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.