Как найти обратный элемент в поле

Как найти обратный элемент в поле

Часто в задачах требуется посчитать что-то по простому модулю (чаще всего (10^9 + 7) ). Это делают для того, чтобы участникам не приходилось использовать длинную арифметику, и они могли сосредоточиться на самой задаче.

Обычные арифметические операции выполняются не сильно сложнее — просто нужно брать модули и заботиться о переполнении. Например:

Но вот с делением возникают проблемы — мы не можем просто взять и поделить. Пример: (frac<8> <2>= 4) , но (frac<8 \% 5 = 3> <2 \% 5 = 2>
eq 4) .

Способ 1: бинарное возведение в степень

Если модуль (p) простой, то решением будет (a^ <-1>equiv a^) . Это следует из малой теоремы Ферма:

Теорема. (a^p equiv a pmod p) для всех (a) , не делящихся на (p) .

Доказательство. (для понимания несущественно, можно пропустить)

Здесь (P(x_1, x_2, ldots, x_n) = frac<prod (x_i!)>) это мультиномиальный коеффициент — количество раз, которое элемент (a_1^ a_2^ ldots a_n^) появится при раскрытии скобки ((a_1 + a_2 + ldots + a_n)^k) .

Теперь два раза «поделим» наш результат на (a) .

[ a^p equiv a implies a^ equiv 1 implies a^ equiv a^ <-1>]

Получается, что (a^) ведет себя как (a^<-1>) , что нам по сути и нужно. Посчитать (a^) можно за (O(log p)) бинарным возведением в степень.

Приведем код, который позволяет считает (C_n^k) .

Способ 2: диофантово уравнение

Диофантовыми уравнениями называют такие штуки:

Требуется решить их в целых числах, то есть (a) и (b) известны, и нужно найти такие целые (возможно, отрицательные) (x) и (y) , чтобы равенство выполнялось. Решают такие вещи расширенным алгоритмом Евклида. TODO: описать, как он работает.

Подставим в качестве (a) и (b) соответственно (a) и (m)

Одним из решений уравнения и будет (a^<-1>) , потому что если взять уравнение по модулю (m) , то получим

Читайте также:  Как увеличить время работы экрана компьютера

[ ax + by = 1 iff ax equiv 1 iff x equiv a^ <-1>pmod m ]

Преимущества этого метода над возведением в степень:

  • Если обратное существует, то оно найдется даже если модуль не простой. Способ с бинарным возведением тоже можно заставить работать с произвольным модулем, но это будет намного труднее.
  • Алгоритм проще выполнять руками.

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

Почему (10^9+7) ?

  1. Это выражение довольно легко вбивать ( 1e9+7 ).
  2. Простое число.
  3. Достаточно большое.
  4. int не переполняется при сложении.
  5. long long не переполняется при умножении.

Кстати, (10^9 + 9) обладает теми же свойствами. Иногда используют и его.

Предподсчёт обратных факториалов за линейное время

Пусть нам нужно зачем-то посчитать все те же (C_n^k) , но для больших (n) и (k) , поэтому асимптотика (O(n log m)) нас не устроит. Оказывается, мы можем сразу предподсчитать все обратные ко всем факториалам.

Если у нас уже написан inv , то нам не жалко потратить (O(log m)) операций, посчитав (m!^<-1>) .

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

Калькулятор для вычисления обратного элемента по модулю ниже, теория под ним.

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

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

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

Для нахождения обратного элемента по модулю можно использовать Расширенный алгоритм Евклида.

Для того, чтобы показать это, рассмотрим следующее уравнение:

Это линейное диофантово уравнение с двумя переменными, см. Линейные диофантовы уравнения с двумя переменными. Посколько единица может делиться только на единицу, то уравнение имеет решение только если .
Решение можно найти с помощью расширенного алгоритма Евклида. При этом, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим:

Читайте также:  Второй мультиплекс в москве

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

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

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

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

2 Answers

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Как изменить винду с 32 на 64

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

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

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

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

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

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

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

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

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

Ссылка на основную публикацию
Как калибровать батарею андроид
Смартфоны и планшеты работающие на базе ОС Android, имеют одну схожая проблему у многих пользователей. Спустя небольшой промежуток времени после...
Как зарабатывать на прохождении игр
Многие любители пасьянсов и тетрисов даже не подозревают, что их увлечение может стать дополнительным источником дохода, принося реальные деньги. Мир...
Как запустить приложение в окне
Обычная практика работы на компьютере предполагает пользование несколькими программами одновременно. Их открывают в оконном режиме, с одной на другую тогда...
Как картинки перевести в один pdf файл
������ ������������� JPG � PDF? ������-��������� �������� ��������� � �������. ������������� � PDF ����� ����� ����������� (JPG, PNG, GIF ���...
Adblock detector