Build an RSA encoder

Your task is to build a function in any language that takes a message `m`, an encryption `e`, and a modulus `k` (all positive integers), and takes `m` to the power of `e` modulo `k`. Your solution must not be a theoretical one, but one that would work on a reasonable computer such as your own, for RSA keys of currently used sizes such as 2048 bits.

Shortest code wins.

-
How are you measuring memory usage? Does this implicitly forbid using big integer libraries unless they come with documented guarantees about their memory usage? – Peter Taylor Feb 15 '13 at 18:47
(And if you're going to post a challenge about RSA, why not make it interesting by asking for an implementation of real RSA as opposed to academic useless-for-protecting-secrets RSA?) – Peter Taylor Feb 15 '13 at 18:48
@PeterTaylor: Big-integer libraries are fine. The main point of the limit is to prevent people from trying to store the entire exponentiated number and then evaluating it modulo `m`. – Joe Z. Feb 15 '13 at 18:50
@PeterTaylor: Also, you can pose the question that includes PKCS #1 if you want. – Joe Z. Feb 15 '13 at 18:53

Python – 5

Python 3 built-in function pow have third parameter. So Python 3 already have built-in RSA encoder

``````r=pow
``````
-
Looks like we have a winner. I didn't know that. :\ – Joe Z. Feb 23 '13 at 20:20
In fact, the solution has a length of 0. Just use function `pow` for RSA encoding/decoding – AMK Feb 23 '13 at 20:33
Nope, it's still length 3 because you need to describe it. :P – Joe Z. Feb 23 '13 at 20:34
Imho, this solution has a char count of 5. By just providing `pow`, the criteria 'build a function' is not satisfied. – air_blob Feb 25 '13 at 11:16
Yeah, I suppose that's true. – Joe Z. Feb 27 '13 at 13:38

Here's my first attempt at actually golfing something here:

Python – 6961 55

``````r=lambda m,e,k:1 if e==0 else m**(e%2)*r(m*m%k,e/2,k)%k
``````

This is a simple exponentiation by squaring algorithm.

02/15 13:17 – 61: Used lambda notation.
02/22 15:44 – 55: Removed some brackets as per grc's suggestions.

-
I believe the question specifies that the function should be named `RSA` – Shmiddty Feb 15 '13 at 17:50
Sorry, that was unclear on my part. – Joe Z. Feb 15 '13 at 18:11
You can save a few chars by removing unnecessary spaces and brackets: `r=lambda m,e,k:1if e==0 else m**(e%2)*r(m*m%k,e/2,k)%k`. And you might also be able to do this, but I haven't tested it: `r=lambda m,e,k:e<1or m**(e%2)*r(m*m%k,e/2,k)%k`. It uses `e<1` instead of `e==0` and `or` instead of `if ... else`. – grc Feb 16 '13 at 0:30
Doesn't % have precedence over *? – Joe Z. Feb 22 '13 at 20:43
@Joe Zeng: Yes, but `True` behaves as `1` when it is used with arithmetic operators. – grc Feb 23 '13 at 0:45

java (83 chars)

if input is of BigInteger type:

``````public BigInteger r(BigInteger m,BigInteger e,BigInteger k){return m.modPow(e,k);}
``````
-