pypi.python.org/pypi/pyfinite/1.5

жит ли какой-нибудь стандартный модуль Python функцию для вычислениямодульный мультипликативный обратный числа, то есть числаy = invmod(x, p) такой, чтоx*y == 1 (mod p)? Похоже, Google не дает хороших советов по этому поводу.

Конечно, можно придумать самодельный 10-лайнеррасширенный евклидов алгоритмно зачем изобретать велосипед.

Например, JavaBigInteger имеетmodInverse метод. Разве в Python нет ничего похожего?

Ответы на вопрос(2)

Если ваш модуль прост (вы называете этоp) тогда вы можете просто вычислить:

y = x**(p-2) mod p  # Pseudocode

Или в собственно Python:

y = pow(x, p-2, p)

Вот кто-то, кто реализовал некоторые возможности теории чисел в Python:http://www.math.umbc.edu/~campbell/Computers/Python/numbthy.html

Вот пример, сделанный в приглашении:

m = 1000000007
x = 1234567
y = pow(x,m-2,m)
y
989145189L
x*y
1221166008548163L
x*y % m
1L

Может быть, кто-то найдет это полезным (изВикиучебники):

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 Lynn16 сент. 2016 г., 20:15
Если вы используетеsympy, тогдаx, _, g = sympy.numbers.igcdex(a, m) делает трюк.
 Thomas04 нояб. 2014 г., 14:59
@Qaz Вы также можете просто уменьшить -3 по модулю 11, чтобы сделать его положительным, в этом случае modinv (-3, 11) == modinv (-3 + 11, 11) == modinv (8, 11). Вероятно, именно так и поступает алгоритм в вашем PDF-файле.
 Rewanth Cool27 янв. 2017 г., 11:46
Очень полезное решение. Мне очень помогло. Спасибо :)
 Qaz04 нояб. 2014 г., 00:02
У меня были проблемы с отрицательными числами, используя этот алгоритм. modinv (-3, 11) не работал. Я исправил это, заменив egcd реализацией на второй странице этого pdf:anh.cs.luc.edu/331/notes/xgcd.pdf Надеюсь, это поможет!

Ваш ответ на вопрос