Python 取模结果与 wolfram alpha 不同？

Question

当我运行我的 python 3 程序：

exp = 211
p = 199
q = 337

d = (exp ** (-1)) % ((p - 1)*(q - 1))

结果为 211^(-1)。

但是当我运行 calculation in wolfram alpha 我得到了我期待的结果。

我做了一些测试输出，程序中的变量exp、p和q都是我在wolfram alpha中使用的整数值。

我的目标是从（弱）加密的整数中导出私钥。如果我测试我的 wolfram alpha 结果，我可以正确解密加密的消息。

Answer 1

Wolfram Alpha 正在计算 modular inverse。也就是说，它正在寻找满足

的整数 x

exp*x == 1 mod (p - 1)*(q - 1)

这与模运算符 % 不同。在这里，Python 只是在给定问题中的表达式时计算 1/exp 除以 (p - 1)*(q - 1) 的余数。

从 this answer 复制 Python 代码，您也可以使用 Python 计算所需的值：

>>> modinv(exp, (p - 1)*(q - 1))
45403

Answer 2

我认为这里的想法是 wolfram alpha 和 python 根据您处理的是整数还是实数这一事实，以不同方式定义模运算。在这种情况下，Wolfram Alpha 使用模逆，因为它检测到第一个数字是 0 < x < 1

更多关于实数定义的信息here

Answer 3

Wolfram Alpha 没有明确定义的语法。它接受你提供的任意文本，并试图弄清楚你输入的意思。在这种情况下，它确定您可能正在寻找模逆，它给了您一个。

Python 具有明确定义的语法。在 Python 中，解析器不会将 ** 和 % 放在一起，并猜测该组合使这两个运算符具有不同于它们通常含义的含义。 ** 以通常的方式计算，然后 % 是模运算符。如果你想要模逆，你必须自己写一个。

Answer 4

Python 立即计算（211^(-1) 计算为 0.004739... 而不是 ekpt 为 1/211）和 x[=24= 的模欧几里得余数] 并且 y 通常定义为 x-floor(x/y)*y 如果 x,y 中的任何一个是有理数。如果您使用一些专用的数论程序进行计算，例如：GP/Pari

ep = 211;p = 199;q = 337;(ep ^ (-1)) % ((p - 1)*(q - 1))

你会得到你期望得到的结果，因为 a) 它尽可能长时间地保持分数为分数 b) 了解模块化算法。

你喜欢 Python 你可以看看 SciPy. SymPy 提供的程序和图书馆可能就是你要找的。

Python 取模结果与 wolfram alpha 不同？

Python modulo result differs from wolfram alpha?

python

cryptography

rsa

modulo

wolframalpha