RSA encryption algorithm in Java: no BigIntegers

I need to implement RSA algorithm in Java. I've found the best solution using BigIntegers, problem is that I need to work only with ints or longs. The encrypting is done like this: M[i]^e mod n where M[i] is an input char and e is a key value. I tried using the ASCII codes of chars, and with codes 开发者_StackOverflow中文版such as 115 and 116 I quickly get out of range. How can I solve the problem? Thanks in advance.

---

You may have a look at modular exponentiation. This way you overcome most of the overflows in your calculations.

---

To clarify a bit...

(a * b) mod m == ((a mod m) * (b mod m)) mod m

If you recall from basic math,

a ^ 10 = (a ^ 5) * (a ^ 5)

So, you can split your crazy high powers into lower powers and then take the modulo of their value (thereby keeping the value small), and then recombine them afterwards:

Too Big!         = Just Right!
(2 ^ 20) mod 113 = (((2 ^ 10) mod 113) * ((2 ^ 10) mod 113)) mod 113

I don't know if this counts as "giving it away" but my students had trouble with this once and I had no problem showing them this trick. Besides, I presume this is more of an exercise in recursion than anything else.