2

I'm trying to enter step 5: Compute d, the modular multiplicative inverse of e (mod φ(n)). How do I enter this in WolframAlpha?

http://en.wikipedia.org/wiki/RSA_%28algorithm%29#A_working_example

migrated from security.stackexchange.com Jun 21 '13 at 15:35

This question came from our site for information security professionals.

1

Technically the multiplicative inverse is equal to (function)^-1 (1/x) || x^-1

So presumably you would just enter: (e (mod φ(n)))^-1

Which for me yielded:

  • 1
    Check the example. e=17. n=3233. (17 (mod φ(3233)))^-1 is not 2753. – user27296 Jun 19 '13 at 20:37
  • Hrm. Then I'm honestly not sure. I tried modular inverse of 17 (mod(3120(3233))) and (17 (mod φ(3233))) as input seeing as it accepts it in word form as well. Both yielded 1/17 rather than 2753. – Justice Cassel Jun 19 '13 at 20:46
  • 1
    @JusticeCassel almost, try modular inverse of 17 mod 3120 and if you have a copy of Mathematica instead, Solve[17 d == 1, d, Modulus -> 3120] works. – Antony Vennard Jun 19 '13 at 22:46
0

The modular inverse is a result of the extended gcd, it's shown as part of the ExtendedGCD function: http://www.wolframalpha.com/input/?i=extendedgcd(17,3233). The result of your example is -1141.

Note, when you're doing homeworks (or just fiddle around), you might want to use a more comfortable tool, I'd recommend Python. The definition of the modular inverse in Python is very simple:

def inverse(x, p):
    inv1 = 1
    inv2 = 0
    while p != 1:
        inv1, inv2 = inv2, inv1 - inv2 * (x / p)
        x, p = p, x % p

    return inv2
  • 1
    Heads up: I think you meant extendedgcd(17,3120) as you've worked out the extended gcd for e,n not e,phi(n). This then lets you show that -367 and 2753 are congruent mod 3120: 3120-367=2753. – Antony Vennard Jun 19 '13 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy