Обратное по модулю целого a — это такое целое число x, что произведение ax сравнимо с 1 по модулю m[1]. В стандартных обозначениях модульной арифметики эта эквивалентность записывается как:
что является сокращённым способом записи утверждения, что m делит (без остатка) величину ax − 1, или, выражаясь другим способом, остаток от деления ax на целое m равен 1. Если a имеет обратный по модулю m, то имеется бесконечное количество решений этой эквивалентности, которые образуют класс вычетов для этого модуля. Более того, любое целое, которое эквивалентно a (то есть из класса эквивалентности a) будет иметь любой элемент класса эквивалентности x в качестве обратного элемента. Используя обозначения для класса эквивалентности, содержащего
, утверждение выше может быть записано следующим образом: обратный элемент по модулю класса эквивалентности
есть класс эквивалентности
, такой что
где символ означает умножение классов эквивалентности по модулю m[2]. Такой вид записи представляет аналог обычной концепции обратного числа в множестве рациональных или вещественных чисел, если заменить числа классами эквивалентности и должным образом определения бинарных операций.
Фундаментальное использование этой операции — решение линейной эквивалентности вида:
Нахождение модульного обратного имеет практическое приложение в области криптографии, например, криптосистема с открытым ключом и алгоритм RSA [3][4][5]. Преимущество для реализации этих приложений в том, что существует очень быстрый алгоритм (расширенный алгоритм Евклида), который может быть использован для вычисления модульных обратных.
Модульная арифметика[править | править код]
Говорят, что для данного положительного числа m два целых числа a и b сравнимы по модулю m, если m делит их разность. Это бинарное отношение обозначается как
Это является отношением эквивалентности на множестве целых чисел , и классы эквивалентности называются классами вычетов по модулю m. Пусть
означает класс эквивалентности, содержащий целое число a[6], тогда
Линейное сравнение — это сравнение по модулю вида
В отличие от линейных уравнений в целых числах, линейное сравнение может иметь ноль, одно или несколько решений. Если x является решением линейного сравнения, то любой элемент из также является решением, так что, если говорится о количестве решений линейного сравнения, подразумевается количество различных классов эквивалентности, которые содержат эти решения.
Если d является наибольшим общим делителем чисел a и m, то линейное сравнение имеет решения тогда и только тогда, когда d делит b. Если d делит b, то существует ровно d решений[7].
Модульное обратное целого числа a по модулю m — это решение линейного сравнения
Ранее говорилось, что решение существует тогда и только тогда, когда наибольший общий делитель a и m равен 1, то есть a и m должны быть взаимно простыми числами. Более того, если это условие выполняется, существует ровно одно решение, то есть, если решение существует, модульное обратное единственно[8].
Если имеет решение, оно обозначается часто следующим образом
однако это можно считать злоупотреблением[en], поскольку может неверно интерпретироваться как обычное обратное числа (которое, в отличие от модульного обратного, не является целым за исключением случаев, когда a равно 1 или -1). Обозначение было бы приемлемым, если бы a интерпретировался как обозначение для класса вычетов
, поскольку обратный элемент класса вычетов снова является классом вычетов с операцией умножения, определённой в следующем разделе.
Целые по модулю m[править | править код]
Отношение эквивалентности по модулю m разбивает множество целых чисел на m классов эквивалентности. Операции сложения и умножения можно определить на этих объектах следующим образом: для сложения или умножения классов эквивалентности сначала любым способом выбираются представители этих классов, затем осуществляется обычная операция над отобранными целыми числами и, наконец, результат операции лежит в классе вычетов, являющемся результатом операции над классами. В символической форме, с и
представляющими операции над классами вычетов, эти определения можно записать как
и
Эти операции вполне определены (что означает, что конечный результат не зависит от выбора представителей).
Классы вычетов по m с этими двумя операциями образуют кольцо, называемое кольцом целых чисел по модулю m. Имеется несколько обозначений, используемых для этих алгебраических объектов, наиболее часто используется или
, однако некоторые элементарные учебники и приложения используют упрощённое обозначение
, если не возникает противоречие с другими алгебраическими объектами.
Классы вычетов целых чисел по модулю m были традиционно известны как классы остатков по модулю m, что отражает факт, что все элементы класса эквивалентности имеют один и тот же остаток от деления на m. Любое множество из m целых, выбранных из разных классов вычетов по модулю m называется полной системой вычетов по модулю m[9]. Деление столбиком показывает, что множество целых чисел {0, 1, 2, …, m − 1} образуют полную систему вычетов по модулю m, известную как наименьшая система вычетов по модулю m. При работе с арифметическими задачами иногда удобнее работать с полной системой вычетов и использовать язык эквивалентности, в то время как в других случаях более удобен взгляд с точки зрения классов эквивалентности кольца [10].
Мультипликативная группа кольца вычетов[править | править код]
Не всякий элемент полной системы вычетов по модулю m имеет обратный элемент, например, нуль обратного не имеет. После удаления элементов полной системы вычетов, что не взаимно просты с m, оставшиеся элементы, которые называются приведённой системой вычетов, все имеют обратные. Число элементов в приведённой системе вычетов равно , где
есть функция Эйлера, то есть количество положительных целых чисел меньших m, которые взаимно просты с m.
В кольце с единицей общего вида не всякий элемент имеет обратный, а те, что имеют, называются обратимыми. Поскольку произведение обратимых элементов обратимо, обратимые элементы кольца образуют группу, группу обратимых элементов кольца, и эта группа часто обозначается как , если R является названием кольца. Группа обратимых элементов кольца целых чисел по модулю m называется мультипликативной группой целых по модулю m, и она изоморфна приведённой системе вычетов. В частности, её порядок (размер) равен
.
Когда m является простым, скажем p, то и все ненулевые элементы
имеют обратные, а тогда
является конечным полем. В этом случае мультипликативная группа целых чисел по модулю p образует циклическую группу порядка p − 1.
Пример[править | править код]
Для иллюстрации вышеприведённых определений рассмотрим пример чисел по модулю 10.
Два числа эквивалентны по 10 тогда и только тогда, когда их разность делится на 10, например
поскольку 10 делит 32 − 12 = 20,
поскольку 10 делит 111 − 1 = 110.
Некоторые из классов вычетов по этому модулю:
Линейное сравнение не имеет решений, поскольку целые, конгруэнтные 5 (то есть, входящие в
) все нечётные, в то время как 4x все чётные. Однако линейное сравнение
имеет два решения, а именно,
и
. НОД(4, 10) = 2 и 2 не делит 5, но делит 6.
Поскольку НОД(3, 10) = 1, линейное сравнение будет иметь решения, то есть, модульное обратное числа 3 по модулю 10 будет существовать. 7 удовлетворяет этому уравнению (21 − 1 = 20). Однако и другие целые удовлетворяют этому уравнению, например 17 и −3 (поскольку 3(17) − 1 = 50 и 3(−3) − 1 = −10). В частности, любое целое число из
будет удовлетворять уравнению, поскольку эти числа имеют вид 7 + 10r для некоторого r и ясно, что
делится на 10. Это уравнение имеет только один класс вычетов в качестве решений. Решение в этом случае может быть получено просто перебором возможных классов, но для получения решения для больших модулей нужны систематические алгоритмы, и они будут представлены в следующих разделах.
Произведение классов вычетов и
может быть получено путём выбора элемента из
, скажем 25, и элемента из
, скажем −2, и их произведение (25)(−2) = −50 находится в классе эквивалентности
. Таким образом,
. Сложение определяется аналогично. Десять классов вычетов вместе с этими операциями сложения и умножения классов вычетов образует кольцо целых чисел по модулю 10, то есть
.
Полной системой вычетов по модулю 10 может быть множество {10, −9, 2, 13, 24, −15, 26, 37, 8, 9}, где каждое целое лежит в своём классе вычетов по модулю 10. Минимальной системой вычетов по модулю 10 служит {0, 1, 2, …, 9}. Приведённой системой вычетов по модулю 10 может быть {1, 3, 7, 9}. Произведение любых двух классов вычетов, представленных этими числами, снова является один из этих четырёх классов. Из этого следует, что эти четыре класса вычетов образуют группу, в этом случае циклическую группу порядка 4, имеющую в качестве генератора 3 или 7. Представленные классы вычетов образуют группу обратимых элементов кольца . Эти классы вычетов в точности те, что имеют обратные по модулю.
Вычисление[править | править код]
Расширенный алгоритм Евклида[править | править код]
Модульное обратное для числа a по модулю m можно найти с помощью расширенного алгоритма Евклида.
Алгоритм Евклида определяет наибольший общий делитель (НОД) двух целых чисел, скажем a и m. Если a имеет обратное по модулю m число, этот НОД должен быть равен 1. Несколько последних равенств, получаемых в процессе работы алгоритма, могут быть решены для нахождения НОД. Затем, используя метод «обратной подстановки», может быть получено выражение, связывающее исходные параметры и НОД. Другими словами, могут быть найдены целые x и y, удовлетворяющие равенство Безу,
Перепишем это следующим образом
то есть,
и модульное обратное числа a вычислено. Более эффективной версией является расширенный алгоритм Евклида, который с помощью дополнительных равенств сокращает два прохода алгоритма (обратную подстановку можно понимать как прохождение алгоритма в обратном порядке) до одного.
В нотации O большое этот алгоритм работает за время в предположении, что
, и считается очень быстрым. Он обычно более эффективен чем альтернативный экспоненциальный алгоритм.
Использование теоремы Эйлера[править | править код]
В качестве альтернативы расширенному алгоритму Евклида для вычисления модульного обратного элемента можно рассматривать использование теоремы Эйлера[11].
Согласно теореме Эйлера, если a взаимно просто с m, то есть НОД(a, m) = 1, то
где — функция Эйлера. Это следует из факта, что a принадлежит мультипликативной группе
тогда и только тогда, когда a взаимно просто с m. Таким образом, модульное обратное можно найти напрямую:
В специальном случае, когда m простое, и модульное обратное задаётся равенством
Этот метод, как правило, медленнее расширенного алгоритма Евклида, но иногда используется, если реализация для модульного возведения в степень уже доступна. Недостатки этого метода:
Замечательное преимущество этой техники в том, что нет условных ветвлений, которые зависят от значения a, а потому значение a, которое может быть важным секретом в криптосистемах с открытым ключом, может быть защищено от атак по сторонним каналам. По этой причине стандартная реализация Curve25519 использует технику вычисления обратного элемента.
Вычисление нескольких обратных[править | править код]
Можно вычислить обратные для нескольких чисел по общему модулю m используя один проход алгоритма Евклида и три умножения на каждое дополнительное входное число[12]. Основной идеей является образование всех
, обращение его, а затем умножение на
для всех
, чтобы остался только
.
Алгоритм (вся арифметика осуществляется по модулю m):
- Вычисляем префиксные произведения
для всех
.
- Вычисляем
с помощью любого доступного алгоритма.
- Для i от n до 2 вычисляем
и
.
- Наконец,
.
Можно осуществить умножение в виде древесной структуры, а не линейной, чтобы обеспечить параллельность вычислений.
Приложения[править | править код]
Поиск модульного обратного имеет много приложений в алгоритмах, опирающихся на теорию модульной арифметики. Например, в криптографии использование модульной арифметики позволяет осуществлять некоторые операции быстрее и с меньшими требованиями к памяти, в то время как другие операции становится выполнить труднее[13]. Оба этих свойства могут использоваться во благо. В частности, в алгоритме RSA шифрование и обратный этому процесс сообщения делается с помощью пары чисел, обратных друг другу по некоторому тщательно выбранному модулю. Один из этих чисел делается открытым, и он может быть использован в быстрой процедуре шифрования, в то время как другое число используется в процедуре расшифровки и не разглашается. Определение скрытого ключа по открытому считается невыполнимой задачей, так как вычислительной мощности на её решение требуется больше, чем есть на Земле, что и защищает от несанкционированного доступа[14].
В качестве другого использования в другом контексте рассмотрим задачу точного деления в компьютерах, когда дан список нечётных чисел размером в компьютерное слово, каждое из которых делится на k, и нужно разделить их на k. Одно из решений следующее:
- Используем расширенный алгоритм Евклида для вычисления
, модульного обратного
, где w равно числу бит в слове. Это обратное существует, поскольку все числа нечётные, а рассматриваются вычеты по модулю, не имеющему нечётных делителей.
- Каждое число в списке умножаем на
и выбираем наименее значащие биты результата (то есть отбрасываем все биты за пределами компьютерного слова).
Во многих машинах, в частности тех, у которых нет аппаратной поддержки деления, деление является более медленной операцией, чем умножение, так что этот подход может повлечь существенное увеличение скорости. Первый шаг относительно медленный, но его нужно сделать всего один раз.
Модульные обратные числа используются для получения решения системы линейных сравнений, что гарантируется китайской теоремой об остатках.
Например, система
имеет общее решение, поскольку 5, 7 и 11 попарно взаимно просты. Решение даётся формулой
где
модульное обратное
,
модульное обратное
,
модульное обратное
.
Тогда,
и в приведённом виде
поскольку 385 является наименьшим общим кратным чисел 5, 7 и 11.
Модульное обратное фигурирует на видном месте в определении сумм Клоостермана.
См. также[править | править код]
- Инверсный конгруэнтный метод — алгоритм генерации псевдослучайных чисел, использующий обратные по модулю числа.
- Восстановление рационального числа по его модулю[en]
Примечания[править | править код]
- ↑ Rosen, 1993, с. 132.
- ↑ Schumacher, 1996, с. 88.
- ↑ Stinson, 1995, с. 124–128.
- ↑ Trappe, Washington, 2006, с. 164−169.
- ↑ Moriarty, K.; Kaliski, B.; Jonsson, J.; Rusch, A. PKCS #1: RSA Cryptography Specifications Version 2.2. Internet Engineering Task Force RFC 8017. Internet Engineering Task Force (2016). Дата обращения: 21 января 2017. Архивировано 12 декабря 2018 года.
- ↑ Other notations are often used, including [a] and [a]m.
- ↑ Ireland, Rosen, 1990, с. 32.
- ↑ Shoup, 2005, с. 15 Theorem 2.4.
- ↑ Rosen, 1993, с. 121.
- ↑ Ireland, Rosen, 1990, с. 31.
- ↑ Koshy, 2007, с. 346.
- ↑ Brent, Zimmermann, 2010, с. 67–68.
- ↑ Trappe, Washington, 2006, с. 167.
- ↑ Trappe, Washington, 2006, с. 165.
Литература[править | править код]
- Douglas R. Stinson. Cryptography / Theory and Practice. — CRC Press, 1995. — ISBN 0-8493-8521-0.
- Victor Shoup. A Computational Introduction to Number Theory and Algebra. — Cambridge University Press, 2005. — ISBN 9780521851541.
- Thomas Koshy. Elementary number theory with applications. — 2nd edition. — Academic Press, 2007. — ISBN 978-0-12-372487-8.
- Richard P. Brent, Paul Zimmermann. §2.5.1 Several inversions at once // Elementary number theory with applications. Modern Computer Arithmetic. — Cambridge University Press, 2010. — Т. 18. — (Cambridge Monographs on Computational and Applied Mathematics). — ISBN 978-0-521-19469-3.
- Kenneth Ireland, Michael Rosen. A Classical Introduction to Modern Number Theory. — 2nd. — Springer-Verlag, 1990. — ISBN 0-387-97329-X.
- К. Айерлэнд, М. Роузен. Классическое введение в современную теорию чисел / Перевод с английского С. П. Демушкина. — Москва: «Мир», 1987.
- Kenneth H. Rosen. Elementary Number Theory and its Applications. — 3rd. — Addison-Wesley, 1993. — ISBN 978-0-201-57889-8.
- Carol Schumacher. Chapter Zero: Fundamental Notions of Abstract Mathematics. — Addison-Wesley, 1996. — ISBN 0-201-82653-4.
- Wade Trappe, Lawrence C. Washington. Introduction to Cryptography with Coding Theory. — 2nd. — Prentice-Hall, 2006. — ISBN 978-0-13-186239-5.
Ссылки[править | править код]
- Weisstein, Eric W. Modular Inverse (англ.) на сайте Wolfram MathWorld.
- Геварра Васкез, Фернандо предлагает пример решения обратного по модулю с помощью Евклидова Алгоритма.
Калькулятор для вычисления обратного элемента по модулю ниже, теория под ним.
Обратный элемент в кольце по модулю
Обратным к числу a по модулю m называется такое число b, что:
,
Обратный элемент обозначают как .
Для нуля обратного элемента не существует никогда, для остальных же элементов обратный элемент может как существовать, так и нет.
Утверждается, что обратный элемент существует только для тех элементов a, которые взаимно просты с модулем m.
Для нахождения обратного элемента по модулю можно использовать Расширенный алгоритм Евклида.
Для того, чтобы показать это, рассмотрим следующее уравнение:
Это линейное диофантово уравнение с двумя переменными, см. Линейные диофантовы уравнения с двумя переменными. Посколько единица может делиться только на единицу, то уравнение имеет решение только если .
Решение можно найти с помощью расширенного алгоритма Евклида. При этом, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим:
Таким образом, найденное x и будет являться обратным к a.
Обратный по модулю
❓Инструкция
Калькулятор онлайн для вычисления обратного элемента по модулю в кольце. Алгоритм поддерживает работу с большими числами с некоторыми ограничениями.
Использование:
Заполняются два поля — число a и модуль m. Число a — число к которому ищем обратный, m — модуль, по которому ищем.
Калькулятор выдает обратный элемент после нажатия на кнопку «Вычислить».
Если установлена галочка «подробнее», то калькулятор помимо обратного элемента по модулю выдает некоторые этапы вычисления.
Ограничения:
Калькулятор поддерживает работу с большими целыми числами (в том числе отрицательными числами для числа a, и только положительными для модулю m) длиной не более 10 000 символов.
📖 Теория
Что значит по модулю?
Синонимом к данному выражению является выражение «остаток от деления«. То есть выражение «5 по модулю 3» эквивалентно выражению «остаток от деления 5 на 3». И в том и в другом случае подразумевается в ответе число 2, так как остаток от деления 5 на 3 = 2.
Стоить отметить тот факт, что по модулю m мы имеем числа от 0 до m — 1. Действительно, остаток от деления на m никогда не превысит m — 1.
Что такое обратное?
Напомним, что число, умноженное на его обратное, равно 1. Из базовой арифметики мы знаем, что:
Число, обратное к числу A, равно 1 / A, поскольку A * (1 / A) = 1 (например, значение, обратное к 5, равно 1/5).
Все действительные числа, кроме 0, имеют обратную
Умножение числа на обратное к A эквивалентно делению на A (например, 10/5 соответствует 10 * 1/5)
Что такое обратное по модулю?
В модульной арифметике у нас нет операции деления. Тем не менее, у нас есть модульные инверсии.
Модульная инверсия a (mod m) есть a-1
(a * a-1) ≡ 1 (mod m) или эквивалентно (a * a-1) mod m = 1
Только числа, взаимно простые с модулем m, имеют модульное обратное.
Говоря проще, обратным элементом к a по модулю m является такое число b, что остаток от деления (a * b) на модуль m равно единице (a * a-1) mod m = 1
Как найти модульный обратный
Наивный метод нахождения модульного обратного a ( по модулю m) является:
Шаг 1. Рассчитать a * b mod m для значений b от 0 до m — 1
Шаг 2. Модульная инверсия a mod m — это значение b, при котором a * b mod m = 1
Обратите внимание, что термин b mod m может иметь только целочисленное значение от 0 до m — 1, поэтому тестирование больших значений чем (m-1) для b является излишним.
Вы наверно уже догадались, что наивный метод является очень медленным. Перебор всех чисел от 0 до m-1 для большого модуля довольно-таки трудоемкая задача. Существует гораздо более быстрый метод нахождения инверсии a (mod m). Таковым является расширенный алгоритм Евклида, который реализован в данном калькуляторе.
Расширенный алгоритм Евклида
Представим наибольший общий делитель числа a и модуля m в виде ax + my. То есть НОД(a, m) = ax + my. Помним, что обратный элемент существует только тогда, когда a и m взаимно просты, то есть их НОД(a, m) = 1. Отсюда: ax + my = 1 — линейное диофантово уравнение второго порядка. Необходимо решить данное уравнение в целых числах и найти x, y.
Найденный коэффициент x будет являться обратным элементом к a по модулю m. Это следует оттуда, что, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим: ax = 1 (m).
Расширенный алгоритм Евклида, в отличие от классического, помимо наибольшего общего делителя позволяет найти также коэффициенты x, y.
Алгоритм:
Вход: a, m ≠ 0
Выход: d, x, y, такие что d = gcd(a, m) = ax + my
1. [Инициализация] (a0, a1) := (a, m); (x0, x1) := (1, 0); (y0; y1) := (0, 1).
2. [Основной цикл] Пока a1 ≠ 0 выполнять {q = QUO(a0, a1);
(a0, a1) := (a1, a0 — a1q); (x0, x1) := (x1, x0 — x1q); (y0, y1) := (y1, y0 — y1q);
QUO(a0, a1) — целая часть от деления a0 на a1
3. [Выход] Вернуть (d, x, y) = (a0, x0, y0)
Битовая сложность расширенного алгоритма Евклида равна O((log2(n))2) , где n = max (|a|, |m|)
Непонятен алгоритм? Ничего страшного, примеры ниже именно для этого и предназначены.
➕ Примеры
Пример для наивного метода.
Пусть a = 3, m = 7. То есть нам необходимо найти обратный элемент к 3 по модулю 7.
Шаг 1. Рассчитать a * b mod m для значений B от 0 до m-1. По очереди проверяем числа от 0 до 6.
3 * 0 ≡ 0 (mod 7) — не подходит
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <—— Обратное найдено.
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)
при b = 5 выполнилось условие, что a * b ≡ 1 (m). Следовательно, b = 5 является обратным элементом к 3 по модулю 7.
Пример на расширенный алгоритм Евклида.
Пусть аналогично предыдущему примеру имеем a = 3, m = 7. Также, требуется найти обратный элемент к 3 по модулю 7. Согласно алгоритму начинаем заполнять таблицу на каждом этапе цикла.
Итерация | q | a0 | a1 | x0 | x1 | y0 | y1 |
0 | — | 3 | 7 | 1 | 0 | 0 | 1 |
1 | 0 | 7 | 3 | 0 | 1 | 1 | 0 |
2 | 2 | 3 | 1 | 1 | -2 | 0 | 1 |
3 | 3 | 1 | 0 | -2 | 0 | 1 | -3 |
После 3-ей итерации получили a1 = 0, строго по алгоритму из раздела «Теория» заканчиваем работу алгоритма.
(d, x, y) = (a0, x0, y0)
(d, x, y) = (1, -2, 1), видим, что d = НОД(3, 7) = 1, следовательно числа 3 и 7 являются взаимно простыми, а значит обратный существует.
Делаем проверку:
3 * (-2) + 7 * 1 = 1
-6 + 7 = 1
1 = 1 — верно!
Обратным элементом к тройке по модулю 7 является x = -2. По модулю 7 число -2 равно 5. Получили, что x = 5 является обратным элементом к 3 по модулю 7.
Сайт переезжает. Большинство статей уже перенесено на новую версию.
Скоро добавим автоматические переходы, но пока обновленную версию этой статьи можно найти там.
Обратный элемент по модулю
Часто в задачах требуется посчитать что-то по простому модулю (чаще всего (10^9 + 7)). Это делают для того, чтобы участникам не приходилось использовать длинную арифметику, и они могли сосредоточиться на самой задаче.
Обычные арифметические операции выполняются не сильно сложнее — просто нужно брать модули и заботиться о переполнении. Например:
c = (a + b) % mod;
c = (mod + a - b) % mod;
c = a * b % mod;
Но вот с делением возникают проблемы — мы не можем просто взять и поделить. Пример: (frac{8}{2} = 4), но (frac{8 % 5 = 3}{2 % 5 = 2} neq 4).
Нужно найти некоторый элемент, который будет себя вести как (frac{1}{a} = a^{-1}), и вместо «деления» домножать на него. Назовем такой элемент обратным.
Способ 1: бинарное возведение в степень
Если модуль (p) простой, то решением будет (a^{-1} equiv a^{p-2}). Это следует из малой теоремы Ферма:
Теорема. (a^p equiv a pmod p) для всех (a), не делящихся на (p).
Доказательство. (для понимания несущественно, можно пропустить)
[
begin{aligned}
a^p &= (underbrace{1+1+ldots+1+1}_text{$a$ раз})^p
\ &= sum_{x_1+x_2+ldots+x_a = p} P(x_1, x_2, ldots, x_a) & text{(раскладываем по определению)}
\ &= sum_{x_1+x_2+ldots+x_a = p} frac{p!}{x_1! x_2! ldots x_a!} & text{(какие слагаемые не делятся на $p$?)}
\ &equiv P(p, 0, ldots, 0) + ldots + P(0, 0, ldots, p) & text{(все остальные не убьют $p$ в знаменателе)}
\ &= a
end{aligned}
]
Здесь (P(x_1, x_2, ldots, x_n) = frac{k}{prod (x_i!)}) это мультиномиальный коеффициент — количество раз, которое элемент (a_1^{x_1} a_2^{x_2} ldots a_n^{x_n}) появится при раскрытии скобки ((a_1 + a_2 + ldots + a_n)^k).
Теперь два раза «поделим» наш результат на (a).
[ a^p equiv a implies a^{p-1} equiv 1 implies a^{p-2} equiv a^{-1} ]
Получается, что (a^{p-2}) ведет себя как (a^{-1}), что нам по сути и нужно. Посчитать (a^{p-2}) можно за (O(log p)) бинарным возведением в степень.
Приведем код, который позволяет считает (C_n^k).
int t[maxn]; // факториалы, можно предподситать простым циклом
// бинарное возведение в степень
int bp (int a, int n) {
int res = 1;
while (n) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
// находит обратный элемент как a^(p-2)
int inv (int x) {
return bp(x, mod-2);
}
int c (int n, int k) {
return t[n] * inv(t[k]) % mod * inv(t[n-k]) % mod;
}
Способ 2: диофантово уравнение
Диофантовыми уравнениями называют такие штуки:
[ ax + by = 1 ]
Требуется решить их в целых числах, то есть (a) и (b) известны, и нужно найти такие целые (возможно, отрицательные) (x) и (y), чтобы равенство выполнялось. Решают такие вещи расширенным алгоритмом Евклида. TODO: описать, как он работает.
Подставим в качестве (a) и (b) соответственно (a) и (m)
[ ax + my = 1 ]
Одним из решений уравнения и будет (a^{-1}), потому что если взять уравнение по модулю (m), то получим
[ ax + by = 1 iff ax equiv 1 iff x equiv a^{-1} pmod m ]
Преимущества этого метода над возведением в степень:
- Если обратное существует, то оно найдется даже если модуль не простой. Способ с бинарным возведением тоже можно заставить работать с произвольным модулем, но это будет намного труднее.
- Алгоритм проще выполнять руками.
Сам автор почти всегда использует возведение в степень.
Почему (10^9+7)?
- Это выражение довольно легко вбивать (
1e9+7
). - Простое число.
- Достаточно большое.
int
не переполняется при сложении.long long
не переполняется при умножении.
Кстати, (10^9 + 9) обладает теми же свойствами. Иногда используют и его.
Предподсчёт обратных факториалов за линейное время
Пусть нам нужно зачем-то посчитать все те же (C_n^k), но для больших (n) и (k), поэтому асимптотика (O(n log m)) нас не устроит. Оказывается, мы можем сразу предподсчитать все обратные ко всем факториалам.
Если у нас уже написан inv
, то нам не жалко потратить (O(log m)) операций, посчитав (m!^{-1}).
После этого мы будем считать ((m-1)!^{-1}) как (m!^{-1} m = frac{1}{1 cdot 2 cdot ldots cdot (m-1)}).
int f[maxn];
f[0] = 1;
for (int i = 1; i < maxn; i++)
f[i] = i*f[i-1] % mod;
int r[maxn];
r[maxn-1] = inv(f[maxn-1])
for (int i = maxn-1; i >= 1; i--)
r[i-1] = r[i]*i % mod;
TODO: техника с сайта емакса.
Что такое обратное число?
Как вы помните, если некое число умножить на число, обратное ему, то получится 1. Из основ арифметики мы знаем следующее:
- Числом, обратным к числу A, называется такое число 1/A, что A * 1/A = 1 (то есть, к примеру, для числа 5 обратным будет 1/5).
- У каждого вещественного числа, кроме 0, есть обратное.
- Умножение на число, обратное A, эквивалентно делению на A (то есть, к примеру, 10/5 — это то же, что 10* 1/5).
Что такое обратное число по модулю?
В модульной арифметике нет операции деления, но есть обратные числа.
-
Число, обратное A (mod C), обозначается A^-1.
-
(A * A^-1) ≡ 1 (mod C) , или, что то же самое, (A * A^-1) mod C = 1.
-
Только у чисел, взаимно простых с C (то есть у тех, у которых нет с C общих простых делителей), есть обратные (mod C)
Как найти обратное число по модулю
Самый
простой метод
нахождения обратного числа к A (mod C) выглядит следующим образом:
Шаг 1. Вычисляем A * B mod C для всех B от 0 до C-1.
Шаг 2. Обратным числом для A mod C будет являться такое B, для которого A * B mod C = 1
Обратите внимание, что B mod C может принимать значения от 0 до C-1, поэтому нет смысла проверять числа, бо́льшие чем B.
Пример: A=3, C=7
Шаг 1. Вычисляем A * B mod C для значений B от 0 до C-1
3 * 5 ≡ 15 (mod 7) ≡
1
(mod 7) <—— ОБРАТНОЕ НАЙДЕНО!
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)
Шаг 2. Обратным значением для A mod C является такое B, при котором A * B mod C = 1
5 — это обратное значение для 3 mod 7, поскольку 5*3 mod 7 = 1.
Давайте рассмотрим другой пример, где обратного значения нет.
Пример: A=2, C=6
Шаг 1. Вычисляем A * B mod C для всех B от 0 до C-1**
Шаг 2. Обратным значением для A mod C является такое B, при котором A * B mod C = 1
Таких значений B, при которых A * B mod C = 1, не существует. Следовательно, у числа A нет обратного значения (mod 6).
Всё дело в том, что числа 2 и 6 не являются взаимно простыми (у них есть общий простой делитель 2).
Кажется, что этот метод слишком медленный…
Есть более быстрый способ нахождения обратного значения для A (mod C), который мы и обсудим в следующих статьях, посвящённых расширенному алгоритму Евклида.