Tell me more ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 3 down vote favorite

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.

share|improve this question
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 at 18:47
2  
(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 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 at 18:50
@PeterTaylor: Also, you can pose the question that includes PKCS #1 if you want. – Joe Z. Feb 15 at 18:53

3 Answers

up vote 5 down vote accepted

Python – 5

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

r=pow
share|improve this answer
Looks like we have a winner. I didn't know that. :\ – Joe Z. Feb 23 at 20:20
In fact, the solution has a length of 0. Just use function pow for RSA encoding/decoding – AMK Feb 23 at 20:33
Nope, it's still length 3 because you need to describe it. :P – Joe Z. Feb 23 at 20:34
1  
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 at 11:16
Yeah, I suppose that's true. – Joe Z. Feb 27 at 13:38
up vote 1 down vote

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

Python – 69 61 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.

share|improve this answer
I believe the question specifies that the function should be named RSA – Shmiddty Feb 15 at 17:50
Sorry, that was unclear on my part. – Joe Z. Feb 15 at 18:11
1  
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 at 0:30
Doesn't % have precedence over *? – Joe Z. Feb 22 at 20:43
1  
@Joe Zeng: Yes, but True behaves as 1 when it is used with arithmetic operators. – grc Feb 23 at 0:45
show 4 more comments
up vote 0 down vote

java (83 chars)

if input is of BigInteger type:

public BigInteger r(BigInteger m,BigInteger e,BigInteger k){return m.modPow(e,k);}
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.