E007. Modular inverse в кольце по модулю

Источник: e-maxx.ru/algo, страница PDF 23.

Définition

Пусть задан некоторый натуральный модуль

, и рассмотрим кольцо, образуемое этим модулем (т.е. состоящее из

чисел от

до

). Тогда для некоторых elementов этого кольца можно find Modular inverse.

Обратным к числу

по модулю

называется такое number

, что:

и его нередко обозначают через

. Понятно, что для нуля обратного elementа не существует никогда; для остальных же elementов обратный может как существовать, так и нет. Утверждается, что обратный существует только для тех elementов

, которые

взаимно просты с модулем

. Рассмотрим ниже два способа нахождения обратного elementа, работающих при условии, что он существует. В завершение, рассмотрим Algorithme, который позволяет find обратные ко всех числам по некоторому модулю за линейное время.

Нахождение с помощью Расширенного Algorithmeа Евклида

Рассмотрим вспомогательное уравнение (относительно неизвестных

и

): Это линейное диофантово уравнение второго порядка. Как показано в соответствующей статье, из

условия

следует, что это уравнение имеет Solution, которое можно find с помощью Расширенного Algorithmeа Евклида (отсюда же, кстати говоря, следует, что когда

, решения, а потому

и обратного elementа, не существует). С другой стороны, если мы возьмём от обеих частей уравнения остаток по модулю , то получим:

Таким образом, найденное

и будет являться обратным к

.

Implémentation (с учётом того, что найденное

надо взять по модулю

, и

могло быть отрицательным):

int x, y;

int g = gcdex (a, m, x, y);

if (g != 1)

cout << "no solution";

else {

x = (x % m + m) % m;

cout << x;

}

Asymptotic complexity этого решения получается

.

Нахождение с помощью Бинарного возведения в степень

Воспользуемся теоремой Эйлера:

которая верна как раз для случая взаимно простых

и

.

Кстати говоря, в случае простого модуля

мы получаем ещё более простое утверждение — малую теорему Ферма:

Умножим обе части каждого из уравнений на

, получим:

● для любого модуля

:

● для простого модуля

: Таким образом, мы получили формулы для непосредственного вычисления обратного. Для практического Applications обычно используют эффективный Algorithme бинарного возведения в степень, который в нашем

случае позволит произвести возведение в степень за

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

, что иногда может оказаться весьма

сложной задачей. Если же факторизация числа известна, то тогда и этот метод также работает за асимптотику .

Нахождение всех простых по заданному модулю

за линейное время

Пусть дан простой модуль

. it is required для каждого числа в отрезке

find обратное к нему. Применяя описанные выше Algorithmeы, мы получим лишь решения с асимптотикой

. Здесь же

мы приведём простое Solution с асимптотикой

.

Solution это выглядит следующим образом. Обозначим через

искомое обратное к числу

по модулю

.

Тогда для

верно тождество: Implémentation этого удивительно лаконичного решения:

r[1] = 1;

for (int i=2; i<m; ++i)

r[i] = (m - (m/i) * r[m%i] % m) % m;

Preuve этого решения представляет из себя цепочку простых преобразований:

Распишем значение

:

откуда, беря обе части по модулю

, получаем:

Умножая обе части на обратное к

и обратное к

, получаем искомую формулу: что и требовалось доказать.