Нахождение обратного элемента в кольце вычетов

#python #алгоритм #математика

Необходимо найти элемент B, обратный элементу A по модулю C.

Такой, что (A*B)%C = 1.

Как найти B в общем виде?
    

Ответы

Ответ 1

Смотрите.

Для начала, A и C должны быть взаимно просты. Если они не взаимно просты, то любая
линейная комбинация (A * X) % C = A * X + C * Y не будет равна единице, то есть, ответа нет.

Окей, пускай числа A и C взаимно просты. Для установления этого вы должны использовать
алгоритм Евклида для вычисления НОД. Если вы при этом воспользуетесь расширенным алгоритмом
Евклида, вы получите не просто НОД, а и те коэффициенты alpha, beta, при которых

alpha * A + beta * C = НОД(A, C) = 1.


При этом alpha и есть ваш ответ, так как

(alpha * A) % C = (1 - beta * C) % C = 1.


Все остальные значения B получаются из данного прибавлением кратного числу C.


Ответ 2

Есть два пути для решения этой задачи. 

Путь первый - использование расширенного алгоритма Евклида.

Алгоритм Евклида ищет НОД двух чисел. Расширенный алгоритм Евклида одновременно с
этим представляет НОД как целочисленную линейную комбинацию исходных чисел:

Ka∙a + Kb∙b = (a, b)


Как легко заметить, если A и C не являются взаимно простыми, то решения нет, а если
являются - то коэффициент при A и будет искомым обратным элементом (для доказательства
можно заменить в формуле выше b на C и взять обе части равенства по модулю C).

Рекурсивный алгоритм довольно прост. На очередном шаге большее из двух чисел (для
определенности, a) представляется как c + k∙b, после чего алгоритм вызывается рекурсивно
для (b, c):

Ka∙(c + k∙b) + Kb∙b = (a, b)
Ka∙c + (Kb + Ka∙k)∙b = (c + k∙b, b) = (c, b)
Kc1∙c + Kb1∙b = (c, b)


Отсюда имеем Ka = Kc1 и Kb = Kb1 - Kc1∙k

Получаем примерно такой алгоритм:

ФУНКЦИЯ НОД(a, b) -> (d, Ka, Kb):
    ЕСЛИ (b == 0) ВЕРНУТЬ (a, 1, 0)

    (d, Kb1, Kc1) = НОД(b, a % b);
    ВЕРНУТЬ (d, Kc1, Kb1 - ⌊a/b⌋ ∙ Kc1);


Итеративный алгоритм столь же прост в реализации, но сложнее в понимании. Проще всего
использовать матрицы. Для начала, следует записать преобразование коэффициентов в матричном
виде:

                     | 0    1  |
(Ka Kb) = (Kb1, Kc1) |         |
                     | 1 -⌊a/b⌋ |


Эти матричные множители можно будет накопить:

|K11 K12|   | 0     1  | |K11` K12`| 
|       | = |          | |         | 
|K21 K22|   | 1  -⌊a/b⌋ | |K21` K22`| 


Получается следующий алгоритм:

ФУНКЦИЯ НОД(a, b) -> (d, Ka, Kb):
    K = (1, 0)(0, 1) // Начинаем с единичной матрицы

    ПОКА b > 0
       K = (K[1, 0], K[1, 1])(K[0, 0] - ⌊a/b⌋∙K[1, 0], K[0, 1] - ⌊a/b⌋∙K[1, 1])
       (a, b) = (b, a % b)

    ВЕРНУТЬ (a, (K[0, 0], K[0, 1])


Теперь, когда у нас есть НОД, осталось найти НОД(A, C), проверить что он равен 1
и взять (Ka % C) в качестве искомого обратного числа.

Время работы - порядка log A по основанию φ итераций (это связано с тем, что худший
случай для алгоритма Евклида - соседние числа Фибоначчи).

Путь второй - использование формулы Эйлера

Если число C заранее известно, или есть достаточно времени на подготовку, то можно
воспользоваться формулой Эйлера:

A ^ φ(C) = 1 (mod C) для взаимно простых A и C


Поскольку для имеющих нетривиальные общие делители A и C задача решения все равно
не имеет - ограничение нам не помешает.

В соответствии с формулой, ответом будет A ^ (φ(C) - 1) % C. Быстро найти его можно
при помощи алгоритма быстрого возведения в степень:

ФУНКЦИЯ СТЕПЕНЬ (a, x, c):
     b = 1

     ПОКА x > 0:
       ЕСЛИ x - НЕЧЕТНОЕ, ТО 
         x = x - 1
         b = (b * a) % c
       ИНАЧЕ
         x = x / 2
         a = (a * a) % c

     ВЕРНУТЬ b


Корректность этого алгоритма легко доказывается если заметить что a ^ x * b - его
инвариант.

Разумеется, после получения ответа надо будет проверить что он правильный, если он
будет неверным - значит, ответа вовсе не существует (A и C имеют общие делители).

Этот алгоритм будет работать быстрее чем алгоритм Евклида, потому что тут основание
логарифма больше, а сами итерации - проще. Но для применения этого алгоритма требуется
заранее знать φ(C)


Ответ 3

Реализация расширенного алгоритма Евклида на Python.

def M(A,N):
    B = 1
    C = 0
    D = A % N
    E = N
    while D > 1:
        F = E/D
        G = C - B*F
        H = E - D*F
        C = B
        E = D
        B = G
        D = H
    return B % N

X = 7
N = 199

Y = M(X,N)
print Y


Y - искомый обратный элемент для X в кольце вычетов по модулю N.