python - 为 Ruby 寻找 divm 或 gmpy 等价物

Question

在 Python 的 gmpy2 扩展模块中，有一个称为mpz的多精度整数类型。它包含一个powmod(x, y, m)函数，而我在 Ruby 中一直缺少该函数。我最近得知 Ruby 实际上有一个powmod. 它隐藏在 OpenSSL 模块中。

require 'openssl'
result = a_big_int.to_bn.mod_exp(exponent, modulo)

另一个功能，也在 gmpy2 中，我一直缺少的是divm(...).

divm(a, b, m) 返回 x 使得 b * x == a 模 m。如果不存在这样的值 x，则引发 ZeroDivisionError 异常。

你知道 OpenSSL 模块是否还有另一个惊喜，或者任何具有这种功能的宝石？如果它是一个快速的，那将非常有帮助。

score 1 · Accepted Answer

快速深入了解 GMP 中的代码，divm(a, b, m)表明它本质上是这样做的

b ^-1 * a % m

其中 b ^-1是模乘逆。当 invert 调用失败时有一些备用逻辑（我不清楚何时会发生这种情况），但对于大多数目的，您可以在 Ruby 中这样做（使用与divm方法签名相同的变量名）：

b.to_bn.mod_inverse(m).mod_mul(a, m).to_i

score 0 · Accepted Answer

我不确定这些在 Ruby 或 Python 中的可访问性。

它包含一个powmod(x, y, m)...

int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p,
    const BIGNUM *m, BN_CTX *ctx);

divm(a, b, m)...

int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *a,
    const BIGNUM *d, BN_CTX *ctx);

2 回答 2