Эта статья входит в число добротных статей

Сравнение по модулю

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Сравне́ние по мо́дулю натурального числа m показывает, что два выбранных целых числа при делении на m дают один и тот же остаток. Целое число может иметь не больше, чем m остатков; это значит, что все целые числа можно разделить на m групп относительно m, каждая из которых отвечает определённому остатку от деления на m.

Мо́дульная арифме́тика, часто называемая модуля́рная арифметика[1][2] широко применяется в математике, информатике и криптографии [3].

История[править | править вики-текст]

Предпосылкой к созданию теории сравнений стало восстановление сочинений Диофанта, которые были выпущены в подлиннике и с латинским переводом, благодаря Баше де Мезириаку, в 1621. Их изучение привело Ферма́ к открытиям, которые по значению существенно опередили свое время. Например, в письме к Френиклю де Бессиrufr[4] 18 октября 1640 года он сообщил без доказательства теорему, впоследствии получившую название малой теоремы Ферма. В современной формулировке теорема утверждает, что если p — простое число и a — целое число, не делящееся на p, то

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

Первое доказательство этой теоремы принадлежит Лейбницу, причём он открыл указанную теорему независимо от Ферма́ не позднее 1683 года и сообщил об этом с приведением точного доказательства Бернулли. Кроме этого Лейбницем был предложен прообраз формулировки теоремы Вильсона.

Позже изучение вопросов, посвященных теории чисел и теории сравнений, было продолжено Эйлером, который ввел квадратичный закон взаимности и обобщил теорему Ферма, установив, что

a^{\varphi(n)}\equiv 1\pmod n,

где \varphi(n) — функция Эйлера.

Понятие и символьное обозначение сравнений было введено Гауссом, как важный инструмент для обоснования его арифметической теории, работа над которой была начата им в 1795 году. Гауссу не были известны труды его предшественников, поэтому результаты его работы, изложенные в первых главах его книги «Арифметические исследования» (1801), были в основном уже известны, однако методы, которые он использовал для доказательств, оказались абсолютно новыми, имеющими высшую важность для развития теории чисел. Используя эти методы Гаусс преобразовал все накопленные до него сведения, связанные с операциями сравнения по модулю, в стройную теорию, которая впервые была изложена в этой же книге. Кроме этого, он исследовал сравнения первой и второй степени, теорию квадратичных вычетов и связанный с ней квадратичный закон взаимности[5].

Определения[править | править вики-текст]

Если два целых числа a и b при делении на m дают одинаковые остатки, то они называются сравнимыми (или равноостаточными) по модулю числа m[6].

Сравнимость чисел a и b записывается в виде формулы (сравнения):

a\equiv b\pmod m.

Число m называется модулем сравнения.

Определение сравнимости чисел a и b по модулю m равносильно любому из следующих утверждений:

  1. Разность чисел a и b делится на m без остатка;
  2. Число a может быть представлено в виде a=b+km, где k — некоторое целое число[7].

Например, 32 и −10 сравнимы по модулю 7, так как оба числа при делении на 7 дают остаток 4:

32 = 7 \cdot 4 + 4; \quad -10 = 7 \cdot (-2) + 4.

Также, 32 и −10 сравнимы по модулю 7, так как их разность 42 делится на 7, и к тому же имеет место представление:

32 = -10 + 6 \cdot 7.

Свойства сравнимости по модулю[править | править вики-текст]

Для фиксированного натурального числа m отношение сравнимости по модулю m обладает следующими свойствами:

Таким образом, отношение сравнимости по модулю m является отношением эквивалентности на множестве целых чисел[8].

Кроме вышеперечисленных свойств, для сравнений справедливы следующие утверждения:

  • любые два целых числа сравнимы по модулю 1.
  • если числа a и b сравнимы по модулю m, и d является делителем m, то a и b сравнимы по модулю d.
Следствие:
Для того, чтобы числа a и b были сравнимы по модулю m, каноническое разложение на простые сомножители которого имеет вид
m = \prod_{i=1}^d p_i^{\alpha_i},

необходимо и достаточно, чтобы

a \equiv b \pmod {p_i^{\alpha_i}},\quad i = 1, 2, \dots, d[9].

Операции со сравнениями[править | править вики-текст]

Сравнения по одному и тому же модулю обладают многими свойствами обычных равенств. Например, их можно складывать, вычитать и перемножать: если числа a_1, a_2, ..., a_n и b_1, b_2, ..., b_n попарно сравнимы по модулю m, то их суммы a_1 + a_2 + ... + a_n и b_1 + b_2 + ... + b_n, а также произведения a_1 \cdot a_2 \cdot ... \cdot a_n и b_1 \cdot b_2 \cdot ... \cdot b_n тоже сравнимы по модулю m. При этом нельзя выполнять эти операции со сравнениями, если их модули не совпадают[9].

Отдельно, следует отметить, что к обеим частям сравнения можно прибавить одно и то же число, также можно перенести число из одно части сравнения в другую со сменой знака. Если числа a и b сравнимы по модулю m, то их степени a^k и b^k тоже сравнимы по модулю m при любом натуральном k[7].

K любой из частей сравнения можно прибавить целое число, кратное модуля, то есть, если числа a и b сравнимы по модулю некоторого числа m, то и a + t_1 сравнимо с b+t_2 по модулю m (t_1 и t_2 — произвольные целые числа) .Также обе части сравнения и модуль можно умножить на одно и то же число, то есть, если числа a и b сравнимы по модулю некоторого целого числа m, то и числа aq и bq сравнимы по модулю числа mq,где q — целое.

Сравнения, однако, нельзя, вообще говоря, делить друг на друга или на другие числа. Пример: 14 \equiv 20 \pmod 6, однако, сократив на 2, мы получаем ошибочное сравнение: 7 \equiv 10 \pmod 6. Правила сокращения для сравнений следующие.

  • Можно делить обе части сравнения на число, но только взаимно простое с модулем: если
 {ad} \equiv {bd} \pmod m и НОД{(d,m)=1}, то
a \equiv b \pmod  m.

Если, число d не взаимно просто с модулем, как было в примере, указанном выше, то сокращать на d нельзя.

  • Можно одновременно разделить обе части сравнения и модуль на их общий делитель:

если {ac} \equiv {bc} \pmod {mc}, то a \equiv b \pmod  m[9].

Связанные определения[править | править вики-текст]

Классы вычетов[править | править вики-текст]

Множество всех чисел, сравнимых с a по модулю m, называется классом вычетов a по модулю m, и обычно обозначается [a]_m или \bar a_m. Таким образом, сравнение a\equiv b\pmod{m} равносильно равенству классов вычетов [a]_m=[b]_m[10].

Любое число класса называется вычетом по модулю m. Пусть для определенности rостаток от деления любого из представителей выбранного класса на m, тогда любое число q из этого класса можно представить в виде q = mt + r, где tцелое. Вычет равный остатку r называется наименьшим неотрицательным вычетом, а вычет \rho, самый малый по абсолютной величине, называется абсолютно наименьшим вычетом.При r < \frac {m}{2}\ \rho=r, в противном случае \rho = r - m. Если m-чётное и r = \frac{m}{2}, то \rho = -\frac{m}{2}[11].

Поскольку сравнимость по модулю m является отношением эквивалентности на множестве целых чисел \mathbb{Z}, то классы вычетов по модулю m представляют собой классы эквивалентности; их количество равно m.

Множество всех классов вычетов по модулю m обозначается \mathbb{Z}_m или \mathbb{Z}/m\mathbb{Z}[12] или \mathbb{Z}/(m)[13].

Операции сложения и умножения на \mathbb{Z} индуцируют соответствующие операции на множестве \mathbb{Z}_m:

[a]_m+[b]_m=[a+b]_m
[a]_m\cdot [b]_m=[a\cdot b]_m

Относительно этих операций множество \mathbb{Z}_m является конечным кольцом, а для простого m — конечным полем[6].

Системы вычетов[править | править вики-текст]

Система вычетов позволяет осуществлять арифметические операции над конечным набором чисел, не выходя за его пределы. Полная система вычетов по модулю m ― любой набор из m попарно несравнимых по модулю m целых чисел. Обычно в качестве полной системы вычетов по модулю m берётся одно из двух множеств:

  • наименьшие неотрицательные вычеты, то есть числа:
0, 1, ... , m-1
  • или абсолютно наименьшие вычеты, состоящие из чисел
0,\pm1,\pm2,...,\pm\frac{m-1}{2},
в случае нечётного m, и чисел
0,\pm1,\pm2,...,\pm(\frac{m}{2}-1),\frac{m}{2}
в случае чётного m.

Максимальный набор попарно несравнимых по модулю m чисел, взаимно простых с m, называется приведённой системой вычетов по модулю m. Всякая приведённая система вычетов по модулю m содержит \varphi(m) элементов, где \varphi(\cdot) — функция Эйлера[11].

Например, для числа m=42. Полная система вычетов может быть представлена числами: 0,1,2,3,...,21,22,23,...,39,40,41 , а приведенная1,5,11,13,17,19,23,25,29,31,37,41.

Сравнения в кольце многочленов над полем[править | править вики-текст]

Рассматривается кольцо многочленов K[x] над полем K. Два многочлена g_1 и g_2, принадлежащие выбранному кольцу, называются сравнимыми по модулю многочлена f, если их разность g_1-g_2 делится на f без остатка. Сравнение обозначается так:

g_1\equiv g_2\pmod f.

Так же, как и в кольце целых чисел, такие сравнения можно складывать, вычитать и перемножать[14].

Решение сравнений[править | править вики-текст]

Сравнения первой степени[править | править вики-текст]

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

ax \equiv b\pmod {m}.

Решение такого сравнения начинается с вычисления d = НОД(a,m). При этом возможны 2 случая:

  • Если b не кратно d, то у сравнения нет решений.
  • Если b кратно d, то у сравнения существует единственное решение по модулю \frac{m}{d}, или, что то же самое, d решений по модулю m. В этом случае в результате сокращения исходного сравнения на d получается сравнение:
a_1 x \equiv b_1\pmod {m_1}
где a_1 = \frac{a}{d}, b_1 = \frac{b}{d} и m_1 = \frac{m}{d} являются целыми числами, причем a_1 и b_1 взаимно просты. Поэтому число a_1 можно обратить по модулю m_1, то есть найти такое число c, что c\cdot a_1\equiv 1\pmod{m_1} (другими словами, c \equiv a_1^{-1}\pmod{m_1}). Теперь решение находится умножением полученного сравнения на c:
x \equiv c a_1 x\equiv c b_1\equiv a_1^{-1} b_1\pmod {m_1}.

Практическое вычисление значения c можно осуществить разными способами: с помощью теоремы Эйлера, алгоритма Евклида, теории цепных дробей (см. алгоритм) и др. В частности, теорема Эйлера позволяет записать значение c в виде:

c \equiv a_1^{-1}\equiv a_1^{\varphi(m_1)-1}\pmod {m_1}[15].

Примеры[править | править вики-текст]

Пример 1. Для сравнения
4x\equiv 26\pmod {22}

имеем d=2, поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все 3 числа на 2:

2x \equiv 2\pmod {11}

Поскольку 2 взаимно просто с модулем 11, то его можно обратить по модулю 11 и найти

2^{-1}\equiv 6\pmod{11}.

Умножая сравнение на 6, получаем решение по модулю 11:

x\equiv 1\pmod {11},

эквивалентное совокупности двух решений по модулю 22:

x\equiv 1\pmod {22} и x\equiv 12\pmod {22}.
Пример 2. Дано сравнение
100 x \equiv 41\pmod {65537}. Отметим, что модуль 65537 — простое число.

Первый способ решения — воспользоваться соотношением Безу. С помощью алгоритма Евклида или программы, приведенной в статье о соотношении Безу, находим, что это соотношение для чисел 100 и 65537 имеет вид:

17695 \cdot 100 + (-27) \cdot 65537 = 1, или 17695 \cdot 100 \equiv 1 \pmod {65537}

Умножив обе части этого сравнения на 41, получим:

100 \cdot 725495 \equiv 41 \pmod {65537}

Отсюда следует, что 725495 есть решение исходного сравнения. Удобнее заменить его на сравнимое с ним 4588 (остаток от деления 725495 на 65537). Ответ: x \equiv 4588 \pmod {65537}.

Второй способ решения, более простой и быстрый, не требует построения соотношения Безу, но также эквивалентен алгоритму Евклида.

Шаг 1. Делим модуль на коэффициент при x с остатком: 65537=100 \cdot 655+37. Умножим обе части исходного сравнения на частное 655 и прибавим 37x; получим: ~65537x \equiv 26855+37x \pmod {65537}, но левая часть кратна 65537, то есть сравнима с нулём, откуда:

~37x \equiv -26855 \pmod {65537}

Мы получили при x коюффициент 37 вместо 100. На каждом следующем шаге уменьшаем аналогично, пока не получим единицу.

Шаг 2. Аналогично делим на новый коэффициент при x: 65537=37 \cdot 1771+10. Умножим обе части сравнения, полученного в предыдущем шаге, на частное 1771 и прибавим 10x; снова заменив левую часть на ноль, получим:

10x \equiv 47560205 \pmod {65537}

47560205 заменяем на его остаток при делении на 65537, равный 45880:

10x \equiv 45880 \pmod {65537}

Далее можно было бы сделать аналогично ещё 5 шагов, но проще разделить обе части сравнения на 10 и сразу получить результат: x \equiv 4588 \pmod {65537}.

Сравнения второй степени[править | править вики-текст]

Сравнения второй степени по простому модулю m имеет следующий общий вид:

c_0x^2+c_1x+c \equiv 0\pmod {m}.

Это выражение можно привести к виду:

(x+b)^2\equiv a\pmod {m}.,

а при замене z = x+ b упрощается максимально:

(z)^2\equiv a\pmod {m}..

Решение этого сравнения сводится к выяснению, является ли данное число квадратичным вычетом (с помощью квадратичного закона взаимности) и последующему вычислению квадратного корня по данному модулю[16]. Для вычисления квадратного корня из квадратичного вычета существует вероятностный метод Берлекэмпа.

Системы сравнений[править | править вики-текст]

Китайская теорема об остатках утверждает, что система сравнений с попарно взаимно простыми модулями m_1, m_2, \ldots, m_n:

\begin{cases}
x \equiv a_1 \pmod {m_1}\\
x \equiv a_2 \pmod {m_2}\\
  \ldots \\
x \equiv a_n \pmod {m_n}
\end{cases}

всегда разрешима, и её решение единственно по модулю m_1 \cdot m_2 \cdots m_n.

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

Применение[править | править вики-текст]

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

Например, сравнения часто применяются для вычисления контрольных сумм, используемых в идентификаторах. Так для определения ошибок при вводе международного номера банковского счета используется сравнение по модулю 97[17].

В криптографии сравнения можно встретить в системах с открытым ключом, использующих, например, алгоритм RSA или протокол Диффи — Хеллмана. Также, модульная арифметика обеспечивает конечные поля, над которыми затем строятся эллиптические кривые, и используется в различных протоколах с симметричным ключом (AES, IDEA)[18].

В химии последняя цифра в регистрационном номере CAS является значением контрольной суммы, которая вычисляется путём сложения последней цифры номера, умноженной на 1, второй справа цифры, умноженной на 2, третьей, умноженной на три и так далее до первой слева цифры, завершаясь вычислением остатка от деления на 10[19]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Вельшенбах М. Глава 5. Модульная математика: вычисление в классах вычетов. // Криптография на Си и С++ в действии.. — М.: «Триумф», 2004. — С. 81—95. — 464 с. — ISBN 5-89392-083-X.
  2. Материалы международной научной конференции “Модулярная арифметика”. Виртуальный компьютерный музей (2005). Проверено 31 июля 2010.
  3. Егоров А. А. Сравнения по модулю и арифметика остатков // Квант. — 1970. — № 5. — С. 28—33.
  4. Французский математик, член французской академии наук с 1666.
  5. Вилейтнер Г. Глава III. Теория чисел // История математики от Декарта до середины XIX / пер. с нем. под. ред. А. П. Юшкевича. — М.: Государственное издательство физико-математической литературы, 1960. — С. 69—84. — 467 с.
  6. 1 2 Степанов С. А. Глава 1. Основные понятия // Сравнения. — М.: «Знание», 1975. — С. 3—9. — 64 с.
  7. 1 2 Виноградов И. М. Основы теории чисел. — М.-Л.: Гос. изд. технико-теоретической литературы, 1952. — С. 41—45. — 180 с.
  8. Сизый С. В. §4. Теория сравнений // Лекции по теории чисел. — М.: ФИЗМАТЛИТ, 2008. — С. 88. — 192 с. — ISBN 978-5-9221-0741-9.
  9. 1 2 3 Сагалович, 2010, с. 25—29
  10. Бухштаб А. А. Глава 8. Классы // Теория чисел. — М.: «Просвещение», 1966. — С. 77—78. — 384 с.
  11. 1 2 Сагалович, 2010, с. 29—32
  12. Сизый С. В. §4. Теория сравнений // Лекции по теории чисел. — М.: ФИЗМАТЛИТ, 2008. — С. 87—88,91. — 192 с. — ISBN 978-5-9221-0741-9.
  13. Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х тт. — М.: Мир, 1998. — С. 27 (Пример 1.37). — 430 с. — ISBN 5-03-000065-8.
  14. Фадеев Д. К. Глава VII. Сравнение в кольце полиномов и расширения полей // Лекции по алгебре. — М.: «Наука», 1984. — С. 197—198. — 416 с.
  15. Сизый С. В. §4. Теория сравнений // Лекции по теории чисел. — М.: ФИЗМАТЛИТ, 2008. — С. 105—109. — 192 с. — ISBN 978-5-9221-0741-9.
  16. Бухштаб А. А. Глава 21. Сравнения 2-й степени по простому модулю, Глава 22. Сравнения второй степени по составному модулю // Теория чисел. — М.: «Просвещение», 1966. — С. 172—201. — 384 с.
  17. Harald Niederreiter, Arne Winterhof. Applied Number Theory. — «Springer», 2015. — С. 369. — 442 с. — ISBN 978-3-319-22321-6.
  18. Коблиц Н. Курс теории чисел и криптографии / пер. с англ. М. А. Михайловой и В. Е. Тараканова под ред. А. М. Зубкова. — М.: Научное изд-во ТВП, 2001. — С. 96, 105—109, 200—209. — 262 с. — ISBN 5-85484-012-X.
  19. Check Digit Verification of CAS Registry Numbers (англ.).

Литература[править | править вики-текст]