Русская Википедия:Обратное по модулю число

Обратное по модулю целого Шаблон:Mvar — это такое целое число Шаблон:Mvar, что произведение Шаблон:Mvar сравнимо с 1 по модулю Шаблон:Mvar Шаблон:Sfn. В стандартных обозначениях модульной арифметики эта эквивалентность записывается как:

<math>ax \equiv 1 \pmod{m},</math>

что является сокращённым способом записи утверждения, что Шаблон:Mvar делит (без остатка) величину Шаблон:Math, или, выражаясь другим способом, остаток от деления Шаблон:Mvar на целое Шаблон:Mvar равен 1. Если Шаблон:Mvar имеет обратный по модулю Шаблон:Mvar, то имеется бесконечное количество решений этой эквивалентности, которые образуют класс вычетов для этого модуля. Более того, любое целое, которое эквивалентно Шаблон:Mvar (то есть из класса эквивалентности Шаблон:Mvar) будет иметь любой элемент класса эквивалентности Шаблон:Mvar в качестве обратного элемента. Используя обозначения <math>\overline{w}</math> для класса эквивалентности, содержащего <math>w</math>, утверждение выше может быть записано следующим образом: обратный элемент по модулю класса эквивалентности <math>\overline{a}</math> есть класс эквивалентности <math>\overline{x}</math>, такой что

<math>\overline{a}\cdot_{m} \overline{x} = \overline{1},</math>

где символ <math>\cdot_m </math> означает умножение классов эквивалентности по модулю Шаблон:Mvar Шаблон:Sfn. Такой вид записи представляет аналог обычной концепции обратного числа в множестве рациональных или вещественных чисел, если заменить числа классами эквивалентности и должным образом определения бинарных операций.

Фундаментальное использование этой операции — решение линейной эквивалентности вида:

<math>ax \equiv b \pmod{m}.</math>

Нахождение модульного обратного имеет практическое приложение в области криптографии, например, криптосистема с открытым ключом и алгоритм RSA Шаблон:Sfn Шаблон:Sfn Шаблон:R. Преимущество для реализации этих приложений в том, что существует очень быстрый алгоритм (расширенный алгоритм Евклида), который может быть использован для вычисления модульных обратных.

Модульная арифметика

Шаблон:Основная статья Говорят, что для данного положительного числа Шаблон:Mvar два целых числа Шаблон:Mvar и Шаблон:Mvar сравнимы по модулю Шаблон:Mvar, если Шаблон:Mvar делит их разность. Это бинарное отношение обозначается как

<math>a \equiv b \pmod{m}.</math>

Это является отношением эквивалентности на множестве целых чисел <math>\mathbb{Z}</math>, и классы эквивалентности называются классами вычетов по модулю Шаблон:Mvar. Пусть <math>\overline{a}</math> означает класс эквивалентности, содержащий целое число Шаблон:Mvar Шаблон:R, тогда

<math>\overline{a} = \{b \in \mathbb{Z} \mid a \equiv b \pmod{m} \}.</math>

Линейное сравнение — это сравнение по модулю вида

<math>ax \equiv b \pmod{m}.</math>

В отличие от линейных уравнений в целых числах, линейное сравнение может иметь ноль, одно или несколько решений. Если Шаблон:Mvar является решением линейного сравнения, то любой элемент из <math>\overline{x}</math> также является решением, так что, если говорится о количестве решений линейного сравнения, подразумевается количество различных классов эквивалентности, которые содержат эти решения.

Если Шаблон:Mvar является наибольшим общим делителем чисел Шаблон:Mvar и Шаблон:Mvar, то линейное сравнение <math>ax \equiv b \pmod{m}</math> имеет решения тогда и только тогда, когда Шаблон:Mvar делит Шаблон:Mvar. Если Шаблон:Mvar делит Шаблон:Mvar, то существует ровно Шаблон:Mvar решенийШаблон:Sfn.

Модульное обратное целого числа Шаблон:Mvar по модулю Шаблон:Mvar — это решение линейного сравнения

<math>ax \equiv 1 \pmod{m}.</math>

Ранее говорилось, что решение существует тогда и только тогда, когда наибольший общий делитель Шаблон:Mvar и Шаблон:Mvar равен 1, то есть Шаблон:Mvar и Шаблон:Mvar должны быть взаимно простыми числами. Более того, если это условие выполняется, существует ровно одно решение, то есть, если решение существует, модульное обратное единственноШаблон:Sfn.

Если <math>ax\equiv 1 \pmod{m}</math> имеет решение, оно обозначается часто следующим образом

<math>x \equiv a^{-1} \pmod{m},</math>

однако это можно считать Шаблон:Нп5, поскольку может неверно интерпретироваться как обычное обратное числа <math>a</math> (которое, в отличие от модульного обратного, не является целым за исключением случаев, когда Шаблон:Mvar равно 1 или -1). Обозначение было бы приемлемым, если бы Шаблон:Mvar интерпретировался как обозначение для класса вычетов <math>\overline{a}</math>, поскольку обратный элемент класса вычетов снова является классом вычетов с операцией умножения, определённой в следующем разделе.

Целые по модулю Шаблон:Mvar

Отношение эквивалентности по модулю Шаблон:Mvar разбивает множество целых чисел на Шаблон:Mvar классов эквивалентности. Операции сложения и умножения можно определить на этих объектах следующим образом: для сложения или умножения классов эквивалентности сначала любым способом выбираются представители этих классов, затем осуществляется обычная операция над отобранными целыми числами и, наконец, результат операции лежит в классе вычетов, являющемся результатом операции над классами. В символической форме, с <math>+_m</math> и <math>\cdot_m</math> представляющими операции над классами вычетов, эти определения можно записать как

<math>\overline{a} +_m \overline{b} = \overline{a + b}</math>

и

<math>\overline{a} \cdot_m \overline{b} = \overline{ab}.</math>

Эти операции вполне определены (что означает, что конечный результат не зависит от выбора представителей).

Классы вычетов по Шаблон:Mvar с этими двумя операциями образуют кольцо, называемое кольцом целых чисел по модулю Шаблон:Mvar. Имеется несколько обозначений, используемых для этих алгебраических объектов, наиболее часто используется <math>\mathbb{Z}/m\mathbb{Z}</math> или <math>\mathbb{Z}/m</math>, однако некоторые элементарные учебники и приложения используют упрощённое обозначение <math>\mathbb{Z}_m</math>, если не возникает противоречие с другими алгебраическими объектами.

Классы вычетов целых чисел по модулю Шаблон:Mvar были традиционно известны как классы остатков по модулю Шаблон:Mvar, что отражает факт, что все элементы класса эквивалентности имеют один и тот же остаток от деления на Шаблон:Mvar. Любое множество из Шаблон:Mvar целых, выбранных из разных классов вычетов по модулю Шаблон:Mvar называется [[Модульная арифметика|полной системой вычетов по модулю Шаблон:Mvar]]Шаблон:Sfn. Деление столбиком показывает, что множество целых чисел Шаблон:Mathобразуют полную систему вычетов по модулю Шаблон:Mvar, известную как [[Сравнение по модулю|наименьшая система вычетов по модулю Шаблон:Mvar]]. При работе с арифметическими задачами иногда удобнее работать с полной системой вычетов и использовать язык эквивалентности, в то время как в других случаях более удобен взгляд с точки зрения классов эквивалентности кольца <math>\mathbb{Z}/m\mathbb{Z}</math>Шаблон:Sfn.

Мультипликативная группа кольца вычетов

Шаблон:Основная статья Не всякий элемент полной системы вычетов по модулю Шаблон:Mvar имеет обратный элемент, например, нуль обратного не имеет. После удаления элементов полной системы вычетов, что не взаимно просты с Шаблон:Mvar, оставшиеся элементы, которые называются приведённой системой вычетов, все имеют обратные. Число элементов в приведённой системе вычетов равно <math>\phi(m)</math>, где <math>\phi</math> есть функция Эйлера, то есть количество положительных целых чисел меньших Шаблон:Mvar, которые взаимно просты с Шаблон:Mvar.

В кольце с единицей общего вида не всякий элемент имеет обратный, а те, что имеют, называются обратимыми. Поскольку произведение обратимых элементов обратимо, обратимые элементы кольца образуют группу, группу обратимых элементов кольца, и эта группа часто обозначается как <math>R^{\times}</math>, если Шаблон:Mvar является названием кольца. Группа обратимых элементов кольца целых чисел по модулю Шаблон:Mvar называется мультипликативной группой целых по модулю Шаблон:Mvar, и она изоморфна приведённой системе вычетов. В частности, её порядок (размер) равен <math>\phi(m)</math>.

Когда Шаблон:Mvar является простым, скажем Шаблон:Mvar, то <math>\phi(p) = p-1</math> и все ненулевые элементы <math>\mathbb{Z}/p\mathbb{Z}</math> имеют обратные, а тогда <math>\mathbb{Z}/p\mathbb{Z}</math> является конечным полем. В этом случае мультипликативная группа целых чисел по модулю Шаблон:Mvar образует циклическую группу порядка Шаблон:Math.

Пример

Для иллюстрации вышеприведённых определений рассмотрим пример чисел по модулю 10.

Два числа эквивалентны по 10 тогда и только тогда, когда их разность делится на 10, например

<math>32 \equiv 12 \pmod{10}</math> поскольку 10 делит 32 − 12 = 20,

<math>111 \equiv 1 \pmod{10}</math> поскольку 10 делит 111 − 1 = 110.

Некоторые из классов вычетов по этому модулю:

<math>\overline{0} = \{ \cdots, -20, -10, 0, 10, 20, \cdots \}</math>

<math>\overline{1} = \{ \cdots, -19, -9, 1, 11, 21, \cdots \}</math>

<math>\overline{5} = \{ \cdots, -15, -5, 5, 15, 25, \cdots \}</math>

<math>\overline{9} = \{ \cdots, -11, -1, 9, 19, 29, \cdots \}.</math>

Линейное сравнение <math>4x \equiv 5 \pmod{10}</math> не имеет решений, поскольку целые, конгруэнтные 5 (то есть, входящие в <math>\overline{5}</math>) все нечётные, в то время как Шаблон:Math все чётные. Однако линейное сравнение <math>4x \equiv 6 \pmod{10}</math> имеет два решения, а именно, <math>x=4</math> и <math>x=9</math>. НОД(4, 10) = 2 и 2 не делит 5, но делит 6.

Поскольку НОД(3, 10) = 1, линейное сравнение <math>3x\equiv 1 \pmod{10}</math> будет иметь решения, то есть, модульное обратное числа 3 по модулю 10 будет существовать. 7 удовлетворяет этому уравнению (21 − 1 = 20). Однако и другие целые удовлетворяют этому уравнению, например 17 и −3 (поскольку 3(17) − 1 = 50 и 3(−3) − 1 = −10). В частности, любое целое число из <math>\overline{7}</math> будет удовлетворять уравнению, поскольку эти числа имеют вид Шаблон:Math для некоторого Шаблон:Mvar и ясно, что

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

Произведение классов вычетов <math>\overline{5}</math> и <math>\overline{8}</math> может быть получено путём выбора элемента из <math>\overline{5}</math>, скажем 25, и элемента из <math>\overline{8}</math>, скажем −2, и их произведение (25)(−2) = −50 находится в классе эквивалентности <math>\overline{0}</math>. Таким образом, <math>\overline{5} \cdot_{10} \overline{8} = \overline{0}</math>. Сложение определяется аналогично. Десять классов вычетов вместе с этими операциями сложения и умножения классов вычетов образует кольцо целых чисел по модулю 10, то есть <math>\mathbb{Z}/10\mathbb{Z}</math>.

Полной системой вычетов по модулю 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. Представленные классы вычетов образуют группу обратимых элементов кольца <math>\mathbb{Z}/10\mathbb{Z}</math>. Эти классы вычетов в точности те, что имеют обратные по модулю.

Вычисление

Расширенный алгоритм Евклида

Шаблон:Основная статья Модульное обратное для числа Шаблон:Mvar по модулю Шаблон:Mvar можно найти с помощью расширенного алгоритма Евклида.

Алгоритм Евклида определяет наибольший общий делитель (НОД) двух целых чисел, скажем Шаблон:Mvar и Шаблон:Mvar. Если Шаблон:Mvar имеет обратное по модулю Шаблон:Mvar число, этот НОД должен быть равен 1. Несколько последних равенств, получаемых в процессе работы алгоритма, могут быть решены для нахождения НОД. Затем, используя метод «обратной подстановки», может быть получено выражение, связывающее исходные параметры и НОД. Другими словами, могут быть найдены целые Шаблон:Mvar и Шаблон:Mvar, удовлетворяющие равенство Безу,

Перепишем это следующим образом

то есть,

<math>ax \equiv 1 \pmod{m},</math>

и модульное обратное числа Шаблон:Mvar вычислено. Более эффективной версией является расширенный алгоритм Евклида, который с помощью дополнительных равенств сокращает два прохода алгоритма (обратную подстановку можно понимать как прохождение алгоритма в обратном порядке) до одного.

В нотации O большое этот алгоритм работает за время <math>O(\log(m)^2)</math> в предположении, что <math>|a| < m</math>, и считается очень быстрым. Он обычно более эффективен чем альтернативный экспоненциальный алгоритм.

Использование теоремы Эйлера

В качестве альтернативы расширенному алгоритму Евклида для вычисления модульного обратного элемента можно рассматривать использование теоремы ЭйлераШаблон:Sfn.

Согласно теореме Эйлера, если Шаблон:Mvar взаимно просто с Шаблон:Mvar, то есть НОД(Шаблон:Mvar, Шаблон:Mvar) = 1, то

<math>a^{\phi(m)} \equiv 1 \pmod{m},</math>

где <math>\phi</math> — функция Эйлера. Это следует из факта, что Шаблон:Mvar принадлежит мультипликативной группе <math>(\mathbb{Z}/m\mathbb{Z})^{\times}</math> тогда и только тогда, когда Шаблон:Mvar взаимно просто с Шаблон:Mvar. Таким образом, модульное обратное можно найти напрямую:

<math>a^{\phi(m)-1} \equiv a^{-1} \pmod{m}.</math>

В специальном случае, когда Шаблон:Mvar простое, <math>\phi (m) = m - 1</math> и модульное обратное задаётся равенством

<math>a^{-1} \equiv a^{m-2} \pmod{m}.</math>

Этот метод, как правило, медленнее расширенного алгоритма Евклида, но иногда используется, если реализация для модульного возведения в степень уже доступна. Недостатки этого метода:

Значение <math>\phi (m)</math> должно быть известно, а наиболее эффективный метод вычисления требует Шаблон:Mvar разложений. Разложение хорошо известно как задача, в которой вычисления занимают большую часть сложности решения. Однако вычислить <math>\phi (m)</math> можно непосредственно, если известно разложение на простые множители числа Шаблон:Mvar.
Относительно высокая стоимость возведения в степень. Хотя это можно реализовать более эффективно с помощью модульного возведения, при больших значениях Шаблон:Mvar наиболее эффективен метод алгоритма Монтгомери. Этот алгоритм сам по себе требует вычисления обратного по модулю Шаблон:Mvar. Без алгоритма Монтгомери стандартный бинарный алгоритм возведения, который требует деления по модулю Шаблон:Mvar на каждом шаге, является медленной операцией при большом Шаблон:Mvar.

Замечательное преимущество этой техники в том, что нет условных ветвлений, которые зависят от значения Шаблон:Mvar, а потому значение Шаблон:Mvar, которое может быть важным секретом в криптосистемах с открытым ключом, может быть защищено от атак по сторонним каналам. По этой причине стандартная реализация Curve25519 использует технику вычисления обратного элемента.

Вычисление нескольких обратных

Можно вычислить обратные для нескольких чисел <math>a_i</math> по общему модулю Шаблон:Mvar используя один проход алгоритма Евклида и три умножения на каждое дополнительное входное числоШаблон:Sfn. Основной идеей является образование всех <math>a_i</math>, обращение его, а затем умножение на <math>a_j</math> для всех <math>j\ne i</math>, чтобы остался только <math>a^{-1}_i</math>.

Алгоритм (вся арифметика осуществляется по модулю Шаблон:Mvar):

Вычисляем префиксные произведения <math display=inline>b_i = \prod_{j=1}^i a_j = a_i b_{i-1}</math> для всех <math>i \leqslant n</math>.
Вычисляем <math>b^{-1}_n</math> с помощью любого доступного алгоритма.
Для Шаблон:Mvar от Шаблон:Mvar до 2 вычисляем
- <math>a^{-1}_i =b^{-1}_ib_{i-1}</math> и
- <math>b^{-1}_{i-1} =b^{-1}_ia_i</math>.
Наконец, <math>a^{-1}_1=b^{-1}_1</math>.

Можно осуществить умножение в виде древесной структуры, а не линейной, чтобы обеспечить параллельность вычислений.

Приложения

Поиск модульного обратного имеет много приложений в алгоритмах, опирающихся на теорию модульной арифметики. Например, в криптографии использование модульной арифметики позволяет осуществлять некоторые операции быстрее и с меньшими требованиями к памяти, в то время как другие операции становится выполнить труднееШаблон:Sfn. Оба этих свойства могут использоваться во благо. В частности, в алгоритме RSA шифрование и обратный этому процесс сообщения делается с помощью пары чисел, обратных друг другу по некоторому тщательно выбранному модулю. Один из этих чисел делается открытым, и он может быть использован в быстрой процедуре шифрования, в то время как другое число используется в процедуре расшифровки и не разглашается. Определение скрытого ключа по открытому считается невыполнимой задачей, так как вычислительной мощности на её решение требуется больше, чем есть на Земле, что и защищает от несанкционированного доступаШаблон:Sfn.

В качестве другого использования в другом контексте рассмотрим задачу точного деления в компьютерах, когда дан список нечётных чисел размером в компьютерное слово, каждое из которых делится на Шаблон:Math, и нужно разделить их на Шаблон:Math. Одно из решений следующее:

Используем расширенный алгоритм Евклида для вычисления <math>k^{-1}</math>, модульного обратного <math>k \pmod{2^w}</math>, где Шаблон:Math равно числу бит в слове. Это обратное существует, поскольку все числа нечётные, а рассматриваются вычеты по модулю, не имеющему нечётных делителей.
Каждое число в списке умножаем на <math>k^{-1}</math> и выбираем наименее значащие биты результата (то есть отбрасываем все биты за пределами компьютерного слова).

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

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

Например, система

<math>\begin{cases}

X \equiv 4 \pmod{5} \\ X \equiv 4 \pmod{7} \\ X \equiv 6 \pmod{11} \\ \end{cases}</math> имеет общее решение, поскольку 5, 7 и 11 попарно взаимно просты. Решение даётся формулой

<math>X=t_1 (7 \times 11) \times 4+t_2 (5\times 11)\times 4+t_3 (5\times 7)\times 6</math>

где

<math>t_1= 3</math> модульное обратное <math>7\times11 \pmod{5}</math>,

<math>t_2=6</math> модульное обратное <math>5\times11 \pmod{7}</math>,

<math>t_3=6</math> модульное обратное <math>5\times7 \pmod{11}</math>.

Тогда,

<math>X=3\times(7\times 11) \times 4 + 6 \times (5 \times 11) \times 4 + 6 \times (5 \times 7) \times 6= 3504</math>

и в приведённом виде

<math>X\equiv 3504 \equiv 39 \pmod{385}</math>

поскольку 385 является наименьшим общим кратным чисел 5, 7 и 11.

Модульное обратное фигурирует на видном месте в определении сумм Клоостермана.

См. также

Инверсный конгруэнтный метод — алгоритм генерации псевдослучайных чисел, использующий обратные по модулю числа.
Шаблон:Нп5

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Книга
- Шаблон:Книга

Шаблон:Refend

Ссылки

Шаблон:MathWorld
Геварра Васкез, Фернандо предлагает пример решения обратного по модулю с помощью Евклидова Алгоритма.

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.