Ищете divm или gmpy эквивалент для Ruby

Question

В модуле расширения gmpy2 для Python есть целочисленный тип с множественной точностью, называемый mpz. Он содержит powmod(x, y, m) функция, и я скучал по этому в Ruby. Недавно я узнал, что Руби на самом деле имеет powmod, Это скрыто в модуле OpenSSL.

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

Другая функция, которая также есть в gmpy2, я пропустил divm(...),

divm (a, b, m) возвращает x такое, что b * x == по модулю m. Вызывает исключение ZeroDivisionError, если такого значения x не существует.

Знаете ли вы, что у модуля OpenSSL есть еще один сюрприз в рукаве или какой-либо драгоценный камень, который имеет такую ​​функцию? Было бы очень полезно, если бы это было быстро.

Answer 1

Быстрое погружение в код в GMP для divm(a, b, m) показывает, что это по существу делает это

б^-1 * а% м

Где b^-1 - модульный мультипликативный обратный. Существует некоторая резервная логика для случая, когда вызов invert завершается неудачно (мне неясно, когда это может произойти), но для большинства целей вы можете сделать это в Ruby примерно так (используя те же имена переменных, что и для divm подпись метода):

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

Answer 2

Я не уверен, насколько они доступны в 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);

---

Вы можете увидеть полные документы в OpenSSL bn (3).