Модульная мультипликативная обратная функция в Python

Question

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

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

Например, Java BigInteger имеет метод modInverse. У Python что-то похожее?

Answer 1

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

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

Или в Python правильной:

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

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

Пример приведен в командной строке:

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

Answer 2

Возможно, вы также захотите ознакомиться с модулем gmpy. Это интерфейс между Python и библиотекой с высокой точностью GMP. gmpy обеспечивает функцию переворачивания, которая делает именно то, что вам нужно:

>>> import gmpy 
>>> gmpy.invert(1234567, 1000000007) 
mpz(989145189) 

Изменено ответ

Как отметил @hyh, что gmpy.invert() возвращает 0, если обратное не существует. Это соответствует поведению функции GMP mpz_invert(). gmpy.divm(a, b, m) обеспечивает общее решение для a=bx (mod m).

>>> gmpy.divm(1, 1234567, 1000000007) 
mpz(989145189) 
>>> gmpy.divm(1, 0, 5) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
ZeroDivisionError: not invertible 
>>> gmpy.divm(1, 4, 8) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
ZeroDivisionError: not invertible 
>>> gmpy.divm(1, 4, 9) 
mpz(7) 

divm() возвращает решение, когда gcd(b,m) == 1 и вызывает исключение, когда мультипликативный обратный не существует.

Отказ от ответственности: Я являюсь постоянным хранителем библиотеки gmpy.

Обновленный ответ 2

gmpy2 теперь корректно вызывает исключение, если обратное не существует:

>>> import gmpy2 

>>> gmpy2.invert(0,5) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
ZeroDivisionError: invert() no inverse exists 

Answer 3

Чтобы выяснить модульное мультипликативный обратный Я рекомендую использовать расширенный алгоритм Евклида, как это:

def multiplicative_inverse(a, b): 
    origA = a 
    X = 0 
    prevX = 1 
    Y = 1 
    prevY = 0 
    while b != 0: 
     temp = b 
     quotient = a/b 
     b = a%b 
     a = temp 
     temp = X 
     a = prevX - quotient * X 
     prevX = temp 
     temp = Y 
     Y = prevY - quotient * Y 
     prevY = temp 

    return origA + prevY 

Answer 4

Возможно, кому-то это будет удобно (от) 210):

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 

Answer 5

Вот мой код, он может быть неаккуратным, но, похоже, он работает для меня в любом случае.

# a is the number you want the inverse for 
# b is the modulus 

def mod_inverse(a, b): 
    r = -1 
    B = b 
    A = a 
    eq_set = [] 
    full_set = [] 
    mod_set = [] 

    #euclid's algorithm 
    while r!=1 and r!=0: 
     r = b%a 
     q = b//a 
     eq_set = [r, b, a, q*-1] 
     b = a 
     a = r 
     full_set.append(eq_set) 

    for i in range(0, 4): 
     mod_set.append(full_set[-1][i]) 

    mod_set.insert(2, 1) 
    counter = 0 

    #extended euclid's algorithm 
    for i in range(1, len(full_set)): 
     if counter%2 == 0: 
      mod_set[2] = full_set[-1*(i+1)][3]*mod_set[4]+mod_set[2] 
      mod_set[3] = full_set[-1*(i+1)][1] 

     elif counter%2 != 0: 
      mod_set[4] = full_set[-1*(i+1)][3]*mod_set[2]+mod_set[4] 
      mod_set[1] = full_set[-1*(i+1)][1] 

     counter += 1 

    if mod_set[3] == B: 
     return mod_set[2]%B 
    return mod_set[4]%B 

Answer 6

Для одноразового использования CodeFights; это одна из самых коротких решений:

MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1] 

Он вернется -1 если A не имеет мультипликативный обратный в n.

Использование:

MMI(23, 99) # returns 56 
MMI(18, 24) # return -1 

Раствор использует Extended Euclidean Algorithm.

Answer 7

Многие из вышеперечисленных ссылок нарушены как для 1/23/2017. Я нашел эту реализацию: https://courses.csail.mit.edu/6.857/2016/files/ffield.py

Answer 8

Ну, у меня нет функции в Python, но у меня есть функция в C, который можно легко преобразовать в питон, в ниже C Функция расширенной Алгоритм Евклида используются для расчета обратный мод.

int imod(int a,int n){ 
int c,i=1; 
while(1){ 
    c = n * i + 1; 
    if(c%a==0){ 
     c = c/a; 
     break; 
    } 
    i++; 
} 
return c;} 

Python Функция

def imod(a,n): 
    i=1 
    while True: 
    c = n * i + 1; 
    if(c%a==0): 
     c = c/a 
     break; 
    i = i+1 

    return c 

Ссылка на вышеупомянутой функции C берется по следующей ссылке C program to find Modular Multiplicative Inverse of two Relatively Prime Numbers