0

Есть выражение x * 6015 % 26 = 4. Мне необходимо осуществить обратную операцию, чтобы вычислить число x. Пока что реализовал только операцию кодирования, а с декодированием мыслей нет.

UPD: Диапазон возможных значений числа x: от 0 до 25

10
  • 3
    14%3 = 2. 47%3 = 2. 2%3 = 2. Это намек: однозначное декодирование не получится...
    – Harry
    7 дек 2021 в 10:54
  • по остатку -никак 7 дек 2021 в 10:54
  • @Harry, а если я еще знаю возможный диапазон числа x ? К примеру от 0 до 25
    – Effex
    7 дек 2021 в 10:56
  • 3
    Если знаете диапазон, то проще построить карту обратных преобразований и не париться. {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.
    – GrAnd
    7 дек 2021 в 10:59
  • 1

2 ответа 2

5

Если знаете диапазон, то проще построить карту обратных преобразований и не париться.

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.

2

Если вас интересует общее решение, то полный перебор - это не то, что вам нужно.

Математически ваша задача формулируется так: найти числа 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.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.