как получить переменную из уравнения модуля

Question

как получить значение 'x' из этого уравнения, используя python?

 5443984100737085739 * x mod 10512797518085747507 = 7873334411288369657

Я пробовал обратную функцию

x=inverse((7873334411288369657/5443984100737085739),10512797518085747507)

но это дает мне х = 0

Answer 1

Ваша inverse попытка с использованием Crypto.Util.number не удалась, поскольку она решает немного другую проблему. Решает уравнение

u * x % v = 1

Обратите внимание, что правая часть равна 1, и вы не можете изменить это, если попытались разделить в качестве параметра.

Вот моя подпрограмма Python, которая использует расширенный евклидов алгоритм для решения такого рода проблемы, где правая часть не обязательно равна единице:

def divideresidues(dividend, divisor, modulus):
    """Divide the dividend by the divisor mod modulus. I.e., return the
    smallest positive integer solution to the equation
    x * divisor % modulus = dividend, assuming dividend and divisor
    are positive and less than modulus.
    """
    r, newr = modulus, divisor
    t, newt = 0, 1
    while newr != 0:
        quotient, remainder = divmod(r, newr)
        r, newr = newr, remainder
        t, newt = newt, t - quotient * newt
    if t < 0:
        t = t + modulus
    quotient, remainder = divmod(dividend, r)
    if remainder:
        raise ValueError('Bad division in divideresidues()')
    return t * quotient % modulus

Код, который печатает желаемое значение x:

print(divideresidues(7873334411288369657, 5443984100737085739, 10512797518085747507))

который дает распечатку

845290633298

и это можно проверить с помощью

x=845290633298
print(5443984100737085739 * x % 10512797518085747507)

, что дает желаемое число

7873334411288369657