# RSA algorithm: How to enter the multiplicative inverse to WolframAlpha?

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

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

So presumably you would just enter: `(e (mod φ(n)))^-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
• @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

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
``````
• 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