RSA算法:如何输入WolframAlpha的乘法逆？

Question

我试图进入步骤5:计算d，e (mod φ(n))的模乘逆。如何在WolframAlpha中输入这个？

http://en.wikipedia.org/wiki/RSA_%28algorithm%29#A_工作中_示例

Answer 1

模逆是扩展gcd的结果，它显示为ExtendedGCD函数：http://www.wolframalpha.com/input/?i=extendedgcd(17,3233)http://www.wolframalpha.com/input/?i=extendedgcd(17,3233)的一部分。你的例子的结果是-1141。

请注意，当您在家工作(或只是摆弄)，您可能想要使用一个更舒适的工具，我会推荐Python。Python中模块化逆的定义非常简单：

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