current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
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
1

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 '13 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 '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

3 Answers 3

up vote 6 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 '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
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 '13 at 11:16
    
Yeah, I suppose that's true. –  Joe Z. Feb 27 '13 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 '13 at 17:50
    
Sorry, that was unclear on my part. –  Joe Z. Feb 15 '13 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 '13 at 0:30
    
Doesn't % have precedence over *? –  Joe Z. Feb 22 '13 at 20:43
1  
@Joe Zeng: Yes, but True behaves as 1 when it is used with arithmetic operators. –  grc Feb 23 '13 at 0:45
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.