Есть выражение x * 6015 % 26 = 4
. Мне необходимо осуществить обратную операцию, чтобы вычислить число x
. Пока что реализовал только операцию кодирования, а с декодированием мыслей нет.
UPD: Диапазон возможных значений числа x
: от 0 до 25
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуЕсли знаете диапазон, то проще построить карту обратных преобразований и не париться.
numbers_map = {x * 6015 % 26:x for x in range(26)}
# {0: 0, 1: 3, 2: 6, 3: 9, 4: 12, 5: 15, 6: 18, 7: 21, 8: 24, 9: 1, 10: 4, 11: 7, 12: 10, 13: 13, 14: 16, 15: 19, 16: 22, 17: 25, 18: 2, 19: 5, 20: 8, 21: 11, 22: 14, 23: 17, 24: 20, 25: 23}
def get_source_number(num):
return numbers_map[num]
Отсюда вытекает, что искомое число x = 12
.
Если вас интересует общее решение, то полный перебор - это не то, что вам нужно.
Математически ваша задача формулируется так: найти числа x
и y
такие, что 6015*x + 26*y = 4
Это уравнение имеет решение, так как эти два числа взаимно просты: gcd(6015, 26) = 1
. Расширенный алгоритм Евклида gcd_extended(A,B)
возвращает три числа - gcd(A,B)
, u
, v
такие что A*u + B*v = gcd(A,B)
def gcd_extended(A,B):
if A == 0:
return (B, 0, 1)
_gcd, v, u = gcd_extended(B % A, A)
return (_gcd, u - (B // A) * v, v)
В вашем случае
g,u,_ = gcd_extended(6015, 26)
assert(g == 1)
x = 4*u
ответ: x
равно 12.
Нужно решить уравнение (x*A)%B = C
Другими словами, нужно решить диофантово уравнение A*x + B*y = C
Это уравнение имеет решение в том и только том случае, если C
делится на gcd(A,B)
.
Решается так: расширенным алгоритмом Евклида найдем u
, v
такие, что A*u + B*v = gcd(A,B)
Тогда x = u*C/gcd(A,B)
def invert_mod(A,B,C):
"Вернуть x такое, что (A*x)%B = C. Если решения нет, вернуть None."
g, u, _ = gcd_extended(A, B)
if 0 != (C % g):
return None
return (u*C//g)%B
В вашем примере invert_mod(6015, 26, 4)
вернет 4.
{x * 6015 % 26:x for x in range(26)}
->{0: 0, 1: 3, 2: 6, 3: 9, 4: 12, 5: 15, 6: 18, 7: 21, 8: 24, 9: 1, 10: 4, 11: 7, 12: 10, 13: 13, 14: 16, 15: 19, 16: 22, 17: 25, 18: 2, 19: 5, 20: 8, 21: 11, 22: 14, 23: 17, 24: 20, 25: 23}
Отсюда вытекает, что искомое числоx = 12
.