MAXimal

добавлено: 10 Jun 2008 18:03
редактировано: 15 Dec 2011 21:27

Обратный элемент в кольце по модулю

Определение

Пусть задан некоторый натуральный модуль m, и рассмотрим кольцо, образуемое этим модулем (т.е. состоящее из чисел от 0 до m-1). Тогда для некоторых элементов этого кольца можно найти обратный элемент.

Обратным к числу a по модулю m называется такое число b, что:

 a \cdot b \equiv 1 \pmod m,

и его нередко обозначают через a^{-1}.

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

Рассмотрим ниже два способа нахождения обратного элемента, работающих при условии, что он существует.

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

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

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

 a \cdot x + m \cdot y = 1.

Это линейное диофантово уравнение второго порядка. Как показано в соответствующей статье, из условия {\rm gcd}(a,m)=1 следует, что это уравнение имеет решение, которое можно найти с помощью Расширенного алгоритма Евклида (отсюда же, кстати говоря, следует, что когда {\rm gcd}(a,m) \ne 1, решения, а потому и обратного элемента, не существует).

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

 a \cdot x = 1 \pmod m.

Таким образом, найденное x и будет являться обратным к a.

Реализация (с учётом того, что найденное x надо взять по модулю m, и x могло быть отрицательным):

int x, y;
int g = gcdex (a, m, x, y);
if (g != 1)
	cout << "no solution";
else {
	x = (x % m + m) % m;
	cout << x;
}

Асимптотика этого решения получается O (\log m).

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

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

 a ^ {\phi(m)} \equiv 1 \pmod m,

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

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

 a^{m-1} \equiv 1 \pmod m.

Умножим обе части каждого из уравнений на a^{-1}, получим:

  • для любого модуля m:

     a^{\phi(m)-1} \equiv a^{-1} \pmod m,

  • для простого модуля m:

     a^{m-2} \equiv a^{-1} \pmod m.

Таким образом, мы получили формулы для непосредственного вычисления обратного. Для практического применения обычно используют эффективный алгоритм бинарного возведения в степень, который в нашем случае позволит произвести возведение в степень за O (\log m).

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

Если же факторизация числа известна, то тогда и этот метод также работает за асимптотику O (\log m).

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

Пусть дан простой модуль m. Требуется для каждого числа в отрезке [1; m-1] найти обратное к нему.

Применяя описанные выше алгоритмы, мы получим лишь решения с асимптотикой O (m \log m). Здесь же мы приведём простое решение с асимптотикой O (m).

Решение это выглядит следующим образом. Обозначим через r[i] искомое обратное к числу i по модулю m. Тогда для i > 1 верно тождество:

 r[i] = - \left\lfloor \frac{m}{i} \right\rfloor \[...]

Реализация этого удивительно лаконичного решения:

r[1] = 1;
for (int i=2; i<m; ++i)
	r[i] = (m - (m/i) * r[m%i] % m) % m;

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

Распишем значение m {\rm~mod~} i:

 m {\rm~mod~} i = m - \left\lfloor \frac{m}{i} \ri[...]

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

 m {\rm~mod~} i = - \left\lfloor \frac{m}{i} \righ[...]

Умножая обе части на обратное к i и обратное к (m {\rm~mod~} i), получаем искомую формулу:

 r[i] = - \left\lfloor \frac{m}{i} \right\rfloor \[...]

что и требовалось доказать.