3
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.
Joe Z.
Posted 2013-02-15T17:21:34.150
Reputation: 30 589
6
Python 3 built-in function pow have third parameter. So Python 3 already have built-in RSA encoder
r=pow
AMK
Posted 2013-02-15T17:21:34.150
Reputation: 506
Looks like we have a winner. I didn't know that. :\ – Joe Z. – 2013-02-23T20:20:22.947
In fact, the solution has a length of 0. Just use function pow for RSA encoding/decoding – AMK – 2013-02-23T20:33:45.230
Nope, it's still length 3 because you need to describe it. :P – Joe Z. – 2013-02-23T20:34:43.737
1Imho, this solution has a char count of 5. By just providing pow, the criteria 'build a function' is not satisfied. – codeporn – 2013-02-25T11:16:08.123
Yeah, I suppose that's true. – Joe Z. – 2013-02-27T13:38:08.623
1
Here's my first attempt at actually golfing something here:
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.
Joe Z.
Posted 2013-02-15T17:21:34.150
Reputation: 30 589
I believe the question specifies that the function should be named RSA – Shmiddty – 2013-02-15T17:50:56.023
Sorry, that was unclear on my part. – Joe Z. – 2013-02-15T18:11:17.200
1You 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 – 2013-02-16T00:30:42.030
Doesn't % have precedence over *? – Joe Z. – 2013-02-22T20:43:47.577
1In most C-derived languages, */% have equal precedence and are evaluated left-to-right. – Peter Taylor – 2013-02-22T20:59:23.883
Huh. I seem to have forgotten that. I generally use brackets where it might be ambiguous anyway, as I've been burned too many times by strict left-to-right evaluation to forget. – Joe Z. – 2013-02-22T21:00:28.423
@grc: I'm pretty sure e<1 will return True, not 1. – Joe Z. – 2013-02-22T21:20:51.543
1@Joe Zeng: Yes, but True behaves as 1 when it is used with arithmetic operators. – grc – 2013-02-23T00:45:06.863
Well, I learned something new. Will "or" also default to bitwise or when working with numbers? – Joe Z. – 2013-02-23T00:51:31.000
0
if input is of BigInteger type:
public BigInteger r(BigInteger m,BigInteger e,BigInteger k){return m.modPow(e,k);}
ratchet freak
Posted 2013-02-15T17:21:34.150
Reputation: 1 334
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 – 2013-02-15T18:47:53.857
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 – 2013-02-15T18:48:47.227
@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. – 2013-02-15T18:50:47.863@PeterTaylor: Also, you can pose the question that includes PKCS #1 if you want. – Joe Z. – 2013-02-15T18:53:41.637