MAXimal

добавлено: 10 Jun 2008 18:03
редактировано: 28 Dec 2021 5:53

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

Определение

Пусть задан некоторый натуральный модуль $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 \[...]$

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