Решение модульного уравнения (Python)

Question

У меня есть проблема, которую легко решить в Python, но поскольку я новичок в python, я не знаю, как это решить.

Все, что я пытаюсь решить это ...

(x * e) mod k = 1 (где e и k известны значения)

Есть ли простой способ сделать это?

Answer 1

Поиск x в основном ищет обратный элемент e мод k, который может быть сделан Extended Euclidean Algorithm, которые хорошо реализован и используются для modular inverse here:

# Iterative Algorithm (xgcd) 
def iterative_egcd(a, b): 
    x,y, u,v = 0,1, 1,0 
    while a != 0: 
     q,r = b//a,b%a; m,n = x-u*q,y-v*q # use x//y for floor "floor division" 
     b,a, x,y, u,v = a,r, u,v, m,n 
    return b, x, y 

def modinv(a, m): 
    g, x, y = iterative_egcd(a, m) 
    if g != 1: 
     return None 
    else: 
     return x % m 

_{Примечания: Я не являюсь владельцем кода}

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

>>> e = 3 
>>> k = 7 
>>> x = modinv(e,k) 
>>> x 
5 
>>> e*x % k 
1 

Answer 2

Если вы предпочитаете использовать популярную математическую библиотеку gmpy вместо того, чтобы кодировать свой собственный алгоритм, тогда функция для решения вашего уравнения (т. Е. Нахождение модульного обратного) называется инвертированием(). После установки текущей версии gmpy (версия 2 с этого письма), вы бы просто сделать это:

>>> import gmpy2 
>>> x = gmpy2.invert(e, k) # (Supply e and k here) 

Примечание: gmpy возвращает значение в (целое многократной точности) формат родной МПЗ, однако вы можно рассматривать значение как обычный междунар в коде Python без проблем, или, если вы предпочитаете, брось к междунар явно:

>>> x = int(gmpy2.invert(3, 7)) 

Вот документация gmpy2.invert():

инвертировать (x, m) -> mpz

Возврат y такой, что x * y == 1 (mod m). Повышает ZeroDivisionError, если нет обратного существует.

Преимущество этого подхода в том, что алгоритм gmpy является быстрым, и вам не нужно вводить дополнительный код. Недостатком является импорт стороннего модуля.